Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!olivea!genie!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell
From: rockwell@socrates.umd.edu (Raul Rockwell)
Newsgroups: comp.theory
Subject: Re: Question on halting problem
Message-ID: <ROCKWELL.91Apr25200531@socrates.socrates.umd.edu>
Date: 26 Apr 91 01:05:31 GMT
References: <Apr.25.08.44.05.1991.23782@athos.rutgers.edu>
Sender: rockwell@socrates.umd.edu (Raul Rockwell)
Followup-To: comp.theory
Organization: Traveller
Lines: 16
In-Reply-To: masticol@athos.rutgers.edu's message of 25 Apr 91 12: 44:06 GMT

Steve Masticola writes:
> 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.

Well I, for one, would rather describe such a program than write it:

(1) Find a problem which is unprovable, except by example.
(2) Write a program to find a solution by trial and error.  (Just plod
    through all possible solutions, one at a time).

Raul Rockwell