Path: utzoo!utgpu!news-server.csri.toronto.edu!hub.toronto.edu!thomson Newsgroups: comp.theory From: thomson@hub.toronto.edu (Brian Thomson) Subject: Re: Question on halting problem Message-ID: <1991Apr25.222534.29570@jarvis.csri.toronto.edu> Keywords: for 10 bonus points... Organization: University of Toronto References: Date: 26 Apr 91 02:25:34 GMT Lines: 28 In article masticol@athos.rutgers.edu (Steve Masticola) writes: > >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. You are changing the rules in mid-stream. Why do you require that the program not read any input? The original problem did not have this constraint. -- Brian Thomson, CSRI Univ. of Toronto utcsri!uthub!thomson, thomson@hub.toronto.edu