Definition:Halting Problem

Definition

Can a Turing machine $A$ be programmed to determine whether Turing machine $B$ will halt?

Also see

• Results about the halting problem can be found here.

Historical Note

Alan Turing proved that no such Turing machine can exist.

Hence he demonstrated the existence of undecidable problems in mathematics.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): halting problem
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): halting problem