- Forward


The Halting Problem
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Introduction
Back SMYC Forward
  • The Question:
    • Is it possible to write a program that will determine if a program will always terminate in a finite number of steps?
  • The Answer:
    • Alan Turing showed, in the 1930s, that the answer is no.
A (Semi-) Formal Treatment
Back SMYC Forward
  • Notation:
    • \(\mathcal{A}\) denotes the set of all algorithms
    • \(\mathcal{D}\) denotes the set of all data (where each element \(D \in \mathcal{D}\) denotes the inputs to an algorithm)
  • Theorem:
    • There is no algorithm, \(H\), that will determine whether every algorithm, \(A \in \mathcal{A}\), will halt in a finite number of steps for every data set, \(D \in \mathcal{D}\).
Proof (by contradiction)
Back SMYC Forward
  1. Assume, to the contrary, that we have an algorithm, \(H\), that terminates in a finite number of steps for all \(A \in \mathcal{A}\) and \(D \in \mathcal{D}\) and returns \(T\) if \(A \in \mathcal{A}\) halts for all \(D \in \mathcal{D}\) and \(F\) otherwise.
  2. Now, observe that since an algorithm, \(A\), is just a sequence of characters it can be thought of as data. That is, \(\mathcal{A} \subsetset \mathcal{D}\).
    3. Expand
  3. Given this, we know that \(H(A, A)\) will correctly return either \(T\) or \(F\) in a finite number of steps.
    4. Expand
  4. Now, we construct the following algorithm, \(G\):
              algorithm G(A)
          {
              if   (H(A, A))
              {
                  while (true);  // Loop forever
              }
              else
              {
                  return true;
              }
          }
    5. Expand
  5. Now consider \(G(G)\); there are two possible outcomes. In the one case, \(G(G)\), terminates in a finite number of steps which means that \(H(G,G)\) must have returned \(F\) (which is incorrect). In the other case, \(G(G)\) loops forever which means that \(H(G,G)\) must have returned \(T\) (which is incorrect).
    6. Expand
  6. Hence, we have a contradiction (i.e., \(H\) was assumed to produce the correct result in a finite number of steps but does not).
    7. Expand
There's Always More to Learn
Back -