Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!ucbvax!kim!albert
From: albert@kim.BERKELEY.EDU (Anthony &)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <11570@ucbvax.BERKELEY.EDU>
Date: Mon, 27-Jan-86 13:36:01 EST
Article-I.D.: ucbvax.11570
Posted: Mon Jan 27 13:36:01 1986
Date-Received: Wed, 29-Jan-86 04:07:47 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: albert@kim.UUCP (Anthony Albert)
Distribution: net
Organization: University of California, Berkeley
Lines: 28
Xref: watmath net.ai:3225 net.philosophy:3969

In article <14830@rochester.UUCP> hari@rochester.UUCP (Narayanan Hari Narayanan) writes:
>Frank Adams writes in a recent posting:
>
>> If by "infinite loop" you mean "repeats the same set of machine states",
>> then detecting infinite loops is like detecting halting.
>> One can readily build a
>> Turing machine which will analyze another Turing machine with input,
>> and "return" true if the machine goes into an infinite loop, false if it
>> halts, and fail to halt if it performs any other kind of unterminating
>> computation.
>
>I don't think so.  ...
>It should be intutively obvious too..How would one TM check if the TM that it
>is analyzing goes into an infinite loop(repeats some machine states infinitely)?
>.by simulating that machine and looking out for repeating states. 
>This is possible as the number of states of any TM is finite. 
>But WHEN should the TM conclude that a particular state of the other TM is 
>repeating infinitely? When it repeats a million times? But then it may stop 
>repeating after a million and two times!
>
The point is that an infinite loop is detected when the machine repeats a
state ONCE; it is not necessary to see it repeat infinitely. This is because
the state of a Turing Machine includes the control information. As soon as a
previous state returns, the machine is destined to repeat all the states
generated since the last time that state was encountered.
				Anthony Albert
				..!ucbkim!albert
				albert@ucbkim.berkeley.edu