Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!rutgers!aramis.rutgers.edu!athos.rutgers.edu!masticol From: masticol@athos.rutgers.edu (Steve Masticola) Newsgroups: comp.theory,dcs.csgss Subject: Question on halting problem Keywords: for 10 bonus points... Message-ID: Date: 25 Apr 91 12:44:06 GMT Followup-To: comp.theory Organization: Rutgers Univ., New Brunswick, N.J. Lines: 20 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)