Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!dimacs.rutgers.edu!aramis.rutgers.edu!paul.rutgers.edu!kumarv From: kumarv@paul.rutgers.edu (kumar vadaparty) Newsgroups: comp.theory Subject: Re: Question on halting problem Keywords: for 10 bonus points... Message-ID: Date: 26 Apr 91 15:50:59 GMT References: Organization: Rutgers Univ., New Brunswick, N.J. Lines: 42 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? Sorry, but I am a bit confused. Typically, problems are undecidable. By problem they mean determining the membership of an object in a collection of objects satisfying a specific property (syntactic or semantic). Hence I am kind of confused about the meaning of "algorithm termination being undecidable". > 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. Again, you may have to re-phrase your problem. For something to be undecidable, we need a collection S and a question, "how hard is it to determine the membership of an arbitrary object in S?" One way, I can think of is: relax the second condition and say the program takes input. Then you may ask as follows: Give a program P of your choice language such that if S denotes the set of inputs on which the program P halts, then the problem of determining whether an arbitrary input belongs to this set S is undecidable (i.e. the set S is non-recursive). By making P to be a universal turing machine (with standard encodings), it is not difficult to show that the halting problem reduces to S and hence S is not recursive. > - Steve (masticol@cs.rutgers.edu) kumar. --