Complexity Explorer Santa Few Institute

1) It is possible to write a computer program that will check the code of any program and correctly report whether that program can ever enter an infinite loop.

False - The construction that we used to show the Halting problem was undecidable only used a simple infinite loop.

 

2) A conguration of a Turing machine consists of the state of its controller, the location of the tape head, and the contents of the tape (that is, all the information needed to determine how the machine will act going forward). Does the following algorithm solve the halting problem? On input (A; x), the algorithm simulates A on input x. If the simulation ever encounters the same conguration twice, it outputs NO. Otherwise, if the simulation eventually nds that A(x) halts, it outputs YES.

No - It is possible for a Turing machine to not halt in ways other than entering the same configuration twice, and hence entering an infinite loop. For example, it might write 1s onto the tape while moving right at every step (such a machine never halts, but is never in the same configuration more than once).

 

3) Some day someone could solve the halting problem.

False - We gave a mathematical proof that there is no algorithm which always halts and correctly solves the halting problem. This is what is usually meant by "solve the halting problem.''

 

4) Although the Halting Problem for Turing machines is uncomputable, there are general-purpose programming languages where the Halting Problem for that language is computable.

False - Any general purpose programming language will be expressive enough to simulate Turing machines, hence, by the Church--Turing thesis, will be equivalent in computational power to Turing machines, so the halting problem for that language will be uncomputable as well.

 

5) There is an algorithm to automate mathematical theorem-proving, which, when given a mathematical statement $S$ as input (in some formal mathematical language, such as first-order logic, in a finite number of steps will output a proof of S or a proof that S is false.

False - If there were such an algorithm, it could be used to solve the halting problem. See homework question 2.