Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!ncar!gatech!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: Date: 28 Apr 91 09:14:45 GMT References: <1991Apr26.135918.8607@m.cs.uiuc.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 29 In-Reply-To: gillies@m.cs.uiuc.edu's message of 26 Apr 91 13: 59:18 GMT Don Gillies > Steve Masticola >| >|Give the source code for a sequential program (in the language of your >|choice) such that: >|* It is undecidable whether the program terminates. > We pitiful humans are unable to build turing machines; nobody has > ever constructed a computer that was more than a DFA, and nobody > ever will (since all computers have a fixed amount of memory). > So in a practical sense, no such program exists. I've been wondering if someone would bring this up. However, it is not true that all computers have a fixed amount of memory. A number of machines have been designed such that you can add memory even while the computer is running. Also, note that a program can be suspended temporarily and loaded onto a bigger and better machine without actually terminating the program. So it seems to me you could continue a computation until some disaster strikes and wrecks your system. Disaster is a rather odd method of terminating execution: in this sense all programs can be considered to halt. However this says nothing about the computation, and instead is a statement about the implementation of the platform (or perhaps about the physical universe). Raul Rockwell