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)