Re: Halting Problem Solved! Film at 11! (Was Re: definitions)

Article View: comp.lang.misc

Article #3769

#3769

From: Amr Sabry
Date: Mon, 06 May 1991 16:26

13 lines
1205 bytes

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

Technical Details

Message-ID: <1991May6.162643.10756@rice.edu>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!rice!sabry

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>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!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

Reply to Parent Message