Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site utcs.uucp
Path: utzoo!utcs!flaps
From: flaps@utcs.uucp (Alan J Rosenthal)
Newsgroups: net.ai
Subject: Re: A halting problem
Message-ID: <1051@utcs.uucp>
Date: Sat, 11-Jan-86 14:54:14 EST
Article-I.D.: utcs.1051
Posted: Sat Jan 11 14:54:14 1986
Date-Received: Sat, 11-Jan-86 15:00:40 EST
References: <2175@aecom.UUCP>
Reply-To: flaps@utcs.UUCP (Alan J Rosenthal)
Distribution: net
Organization: University of Toronto
Lines: 24
Summary: 


It is not true that people can always detect infinite loops.  Similarly it
is not true that computers can never detect infinite loops.  For example,
assuming C here, suppose you write a program:
	main ()
	{	while (1) ; }

This is an infinite loop.  But you could easily write a program which
examined another program and checked if it was IDENTICAL to the above
program, and if it was, outputted "infinite loop", if it was different
outputted "not sure".  You see that this program would sometimes return the
truth.  This is sort of a partial halting algorithm.

You could make a much more sophisticated algorithm which simulated the input
program for a short while, and if it terminated in that time, outputs
"terminates", and if it is ever executing the same step with the same values
for all variables, outputs "infinite loop", and if neither of these happens
within 10 cpu seconds, outputs "not sure".

A sufficiently sophisticated partial halting algorithm would match people's
abilities in this regard.

Alan J Rosenthal
{linus|decvax}!utzoo!utcs!flaps, {ihnp4|allegra}!cbosgd!utcs!flaps