[dcs.csgss] Question on halting problem

masticol@athos.rutgers.edu (Steve Masticola) (04/25/91)

Turing's proof of the undecidability of the halting problem is based
on assuming that an algorithm to decide halting existed, and then
proving from that a contradiction. This brings up my point: Is it
possible to define an algorithm s.t. its termination is undecidable?
(Since I like to play with computers more than I like to play with
theories, I'll phrase the question in terms of a "program" rather than
an "algorithm".)

For 10 points:

Give the source code for a sequential program (in the language of your
choice) such that:

* The program compiles correctly and executes without errors;
* The program does not read any input or respond to any external
  signals;
* It is undecidable whether the program terminates.

- Steve (masticol@cs.rutgers.edu)