776
Modeling Arithmetic, Computation, and Languages
By the way Z is constructed, if Z acting on s Z halts, it is because Y acting on
(s Z , s Z ) halts, and that happens because X acting on (s Z , s Z ) halts with a 0 on the
tape; but if this happens, it implies that Z begun on s Z fails to halt! Therefore,
Z on s Z halts S Z on s Z fails to halt
(1)
This implication is very strange; let’s see what happens if Z on s Z does not
halt. By the way Z is constructed, if Z acting on s Z does not halt, neither does Y acting on (s Z , s Z ). Now Y acting on (s Z , s Z ) fails to halt exactly when X acting on (s Z , s Z )
halts with a 1 on the tape; but this result implies that Z begun on s Z halts! Therefore
Z on s Z fails to halt S Z on s Z halts
(2)
Together, implications (1) and (2) provide an airtight contradiction, so our assumption that the halting problem is solvable is incorrect. End of Proof.
The proof of the unsolvability of the halting problem depends on two ideas.
One is that of encoding a Turing machine into a string description, and the other
is that of having a machine look at and act on its own description. Notice also that
neither (1) nor (2) alone in the proof is sufficient to prove the result. Both are needed to contradict the original assumption of the solvability of the halting problem.
We have previously encountered another proof of this nature, where the
observation that makes the proof work is self-contradictory. You might want to
review here the proof of Cantor’s theorem in Chapter 5.
Computational Complexity
As a model of computation, the Turing machine has provided us with a way to
prove the existence of unsolvable (uncomputable) problems. Not only does the
Turing machine help us find the limits of computability, but it can also help us
classify problems that are computable—that have an algorithm for their solution—by the amount of work required to carry out the algorithm.
Finding the amount of work required to carry out an algorithm sounds like analysis of algorithms. We have analyzed a number of real algorithms in this book and
classified them as Θ(log n), Θ(n), Θ(n
2
), or what have you. By the Church–Turing
thesis, any algorithm can be expressed in Turing machine form. In this form, the
amount of work is the number of Turing machine steps (one per clock pulse) required
before the Turing machine halts. (We assume here that we are considering only tasks
that “have answers” so that the Turing machine halts on all appropriate input.)
Turing machine computations are quite inefficient. Therefore if algorithms A
and A′ both solve the same problem, but A is expressed as a description of a Turing
machine and A′ as pseudocode for instructions in a high-level programming language, then comparing the number of operations each algorithm performs is rather
meaningless. Therefore we will assume that all algorithms are expressed in Turing
machine form so that we can readily compare the efficiency of different algorithms.
Rather than discuss whether a Turing machine algorithm is Θ(n) or Θ(n
2
),
let us simply note whether it is a polynomial-time algorithm. (Only quite trivial
algorithms can be better than polynomial time, because it takes a Turing machine n steps just to examine its tape.) Problems for which no polynomial-time
algorithms exist are called intractable. Such problems may be solvable, but only
by inefficient algorithms.
Modeling Arithmetic, Computation, and Languages
By the way Z is constructed, if Z acting on s Z halts, it is because Y acting on
(s Z , s Z ) halts, and that happens because X acting on (s Z , s Z ) halts with a 0 on the
tape; but if this happens, it implies that Z begun on s Z fails to halt! Therefore,
Z on s Z halts S Z on s Z fails to halt
(1)
This implication is very strange; let’s see what happens if Z on s Z does not
halt. By the way Z is constructed, if Z acting on s Z does not halt, neither does Y acting on (s Z , s Z ). Now Y acting on (s Z , s Z ) fails to halt exactly when X acting on (s Z , s Z )
halts with a 1 on the tape; but this result implies that Z begun on s Z halts! Therefore
Z on s Z fails to halt S Z on s Z halts
(2)
Together, implications (1) and (2) provide an airtight contradiction, so our assumption that the halting problem is solvable is incorrect. End of Proof.
The proof of the unsolvability of the halting problem depends on two ideas.
One is that of encoding a Turing machine into a string description, and the other
is that of having a machine look at and act on its own description. Notice also that
neither (1) nor (2) alone in the proof is sufficient to prove the result. Both are needed to contradict the original assumption of the solvability of the halting problem.
We have previously encountered another proof of this nature, where the
observation that makes the proof work is self-contradictory. You might want to
review here the proof of Cantor’s theorem in Chapter 5.
Computational Complexity
As a model of computation, the Turing machine has provided us with a way to
prove the existence of unsolvable (uncomputable) problems. Not only does the
Turing machine help us find the limits of computability, but it can also help us
classify problems that are computable—that have an algorithm for their solution—by the amount of work required to carry out the algorithm.
Finding the amount of work required to carry out an algorithm sounds like analysis of algorithms. We have analyzed a number of real algorithms in this book and
classified them as Θ(log n), Θ(n), Θ(n
2
), or what have you. By the Church–Turing
thesis, any algorithm can be expressed in Turing machine form. In this form, the
amount of work is the number of Turing machine steps (one per clock pulse) required
before the Turing machine halts. (We assume here that we are considering only tasks
that “have answers” so that the Turing machine halts on all appropriate input.)
Turing machine computations are quite inefficient. Therefore if algorithms A
and A′ both solve the same problem, but A is expressed as a description of a Turing
machine and A′ as pseudocode for instructions in a high-level programming language, then comparing the number of operations each algorithm performs is rather
meaningless. Therefore we will assume that all algorithms are expressed in Turing
machine form so that we can readily compare the efficiency of different algorithms.
Rather than discuss whether a Turing machine algorithm is Θ(n) or Θ(n
2
),
let us simply note whether it is a polynomial-time algorithm. (Only quite trivial
algorithms can be better than polynomial time, because it takes a Turing machine n steps just to examine its tape.) Problems for which no polynomial-time
algorithms exist are called intractable. Such problems may be solvable, but only
by inefficient algorithms.