Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mstan!sethb From: sethb@Morgan.COM (Seth Breidbart) Newsgroups: comp.theory Subject: Re: Question on halting problem Keywords: for 10 bonus points... Message-ID: <3131@ylum.Morgan.COM> Date: 29 Apr 91 22:36:52 GMT References: <1010@uqcspe.cs.uq.oz.au> Organization: Morgan Stanley, & Co., Inc. / New York City, NY Lines: 49 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. In a previous posting, I pointed out that any such program can be "decided", where "decided" has the usual meaning (="the correct answer is given"). Since the answer is either "halts" or "does not halt", then there is a trivial program to "decide". I can't necessarily specify the program, but I can give you two programs, and guarantee that one of them "decides". If "decide" is taken to mean "prove, in a formal system", then the answer changes. Goedel proved that in any sufficiently powerful formal system there are true but unprovable statements. Consider a program that searches for a proof or counterexample to one of these. If we prove it halts, then either the statement is false or it is provable; but we know that it's true and unprovable. If we prove that it doesn't halt, then we've proven the lack of a counterexample, therefore we've proven the statement, which we can't do (in that formal system). An interesting example of such an unprovable assertion is: "The complexity of the string xxxx...xxx is greater than the number of bits in it", where the string xxxx...xxx is longer than a description of the formal system, and random. See Chaitin's work for a proof that for any formal system, there is a maximal provable complexity (the complexity of a string is defined as the length of the shortest program that outputs that string), and that length corresponds to the size of a description of the formal system. Seth sethb@fid.morgan.com