Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site mmintl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.philosophy,net.ai
Subject: Re: A Halting followup
Message-ID: <1039@mmintl.UUCP>
Date: Wed, 15-Jan-86 14:35:46 EST
Article-I.D.: mmintl.1039
Posted: Wed Jan 15 14:35:46 1986
Date-Received: Sun, 19-Jan-86 04:20:23 EST
References: <2190@aecom.UUCP>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Distribution: net
Organization: Multimate International, E. Hartford, CT
Lines: 30
Xref: watmath net.philosophy:3822 net.ai:3189

In article <2190@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes:
>In the name of fair play, here is the oppositions comments.
>
>Your assertion that humans can decide the halting problem
>doen't stand up under inspection.  Consider a program
>that looks for counter-examples to Fermat's Last Theorem.
>Mathematicians have trying to prove for many years that
>such program will never halt.
>
>Rich
>
>
>Supposing the procedure halt initiated a background process which
>periodically monitored the progress of the procedures, testing 
>for a consistent pattern of execution and checking the stack for
>possible recursion. 
>
>This is incredibly simplified, but isn't this basically what the
>human mind would do in the same situation?

Yes, you can do this.  But this will not detect all possible infinite
loops.  Any possible test for a consistent pattern of execution will
either detect such a pattern for a program which does eventually halt,
or fail to detect such a pattern for program which does not halt.
Think about the Fermat problem.  This program goes through a fairly
simple pattern of execution.  But the exit condition is tricky -- is the
condition ever satisfied, or not?  Hard to tell.  *Very* hard to tell.

Frank Adams                           ihpn4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108