Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!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: <3109@ylum.Morgan.COM> Date: 25 Apr 91 16:08:23 GMT References: Organization: Morgan Stanley, & Co., Inc. / New York City, NY Lines: 33 In article masticol@athos.rutgers.edu (Steve Masticola) writes: : > Is it >possible to define an algorithm s.t. its termination is undecidable? > >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. This clearly cannot be done. For any program that does not read input, consider the following two programs: Program 1: Print "The program halts." Program 2: Print "The program does not halt." One of those two correctly "decides" whether the given program halts. If you're asking whether there is a program that we don't know the termination behavior of, consider a program that searches for counterexamples to Fermat's Last Theorem (or your favorite open conjecture). Seth sethb@fid.morgan.com