Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!pacbell.com!pacbell!osc!jgk From: jgk@osc.COM (Joe Keane) Newsgroups: comp.theory Subject: Re: Question on halting problem Summary: No. Keywords: recursive Message-ID: <4760@osc.COM> Date: 30 Apr 91 17:23:48 GMT References: <18974@crdgw1.crd.ge.com> Reply-To: jgk@osc.UUCP (Joe Keane) Organization: Versant Object Technology, Menlo Park, CA Lines: 34 In article masticol@athos.rutgers.edu (Steve Masticola) writes: >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) This doesn't make sense, although it is a common mistake. Given a program which takes no input, either it halts or it doesn't. In either case, the program is trivially decidable. A common example of such a program is one which halts if and only if there's a counter-example to Fermat's last theorem. While we don't know at present whether or not it will halt, it's still considered decidable. Now if say we take the exponent as input, then maybe it's undecidable, but i doubt it. For a function to be undecidable, it must have some input parameter which changes the behavior of the program in some complicated way. We can be more specific than `complicated' and say that the way it changes the behavior can't be determined in all cases by any given algorithm. A good example of an undecidable program is a Turing machine simulator. Assume it reads some description of a Turing machine from its input, and then runs the machine and halts if it does. If the simulator is itself a Turing machine, then we have the case of a universal Turing machine. -- Joe Keane, amateur mathematician jgk@osc.com (...!uunet!stratus!osc!jgk)