Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!rice!sabry
From: sabry@rice.edu (Amr Sabry)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <1991May6.162643.10756@rice.edu>
Date: 6 May 91 16:26:43 GMT
References: <333124@socrates.umd.edu> <R73812w164w@mantis.co.uk> <30040@dime.cs.umass.edu> <1991May4.192440.5527@sctc.com> <30095@dime.cs.umass.edu> <truesdel.673495042@sun418>
Sender: news@rice.edu (News)
Reply-To: sabry@rice.edu (Amr Sabry)
Organization: Rice University
Lines: 13
Originator: sabry@datura.rice.edu


In article <truesdel.673495042@sun418>, truesdel@nas.nasa.gov (David A. Truesdell) writes:
|> program reach the halting state" is inherently undecidable, even given
|> infinite time.  The physical limits of "actual computers" have no bearing on

I am not sure I agree that given infinite time the halting problem is still 
undecidable. The question does not make sense in this case as the 
distinction between recursive languages and r.e. languages goes away if you 
have infinite time. 

I should point out that infinite time is different than arbitrarily large time.

--Amr