Newsgroups: comp.theory Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!m.cs.uiuc.edu!gillies From: gillies@m.cs.uiuc.edu (Don Gillies) Subject: Re: Question on halting problem Message-ID: <1991Apr26.135918.8607@m.cs.uiuc.edu> Keywords: for 10 bonus points... Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL References: Date: Fri, 26 Apr 91 13:59:18 GMT Lines: 16 masticol@athos.rutgers.edu (Steve Masticola) writes: >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. --