Article View: comp.lang.misc
Article #3770Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
From: David Gudeman
Date: Mon, 06 May 1991 19:07
Date: Mon, 06 May 1991 19:07
15 lines
936 bytes
936 bytes
In article <truesdel.673495042@sun418> David A. Truesdell writes: ]...the question "will this ]program reach the halting state" is inherently undecidable, even given ]infinite time. I suppose you mean "an arbitrarily large time", not "inifinite time". The halting problem _can_ be solved given infinite time. You run the TM in question; if it halts within an infinite time the the answer is "yes" and if it doesn't halt within an infinite time the answer is "no". -- David Gudeman gudeman@cs.arizona.edu noao!arizona!gudeman
Technical Details
Message-ID:
<2799@optima.cs.arizona.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!asuvax!noao!arizona!gudemanShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!asuvax!noao!arizona!gudeman From: gudeman@cs.arizona.edu (David Gudeman) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <2799@optima.cs.arizona.edu> Date: 6 May 91 19:07:07 GMT Sender: news@cs.arizona.edu Lines: 15