Path: 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

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