berger@aecom.UUCP (Micha Berger) (01/14/86)
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? -- Carl C. Hewitt
franka@mmintl.UUCP (Frank Adams) (01/15/86)
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
drew@ukma.UUCP (Andrew Lawson) (01/17/86)
In article <2190@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes: >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? > > -- Carl C. Hewitt This is roughly the same as saying that you can examine the digits after the decimal in a number to see whether the expansion terminates. If a patern of repetition is found, the expansion is infinite. So, consider irrational numbers . . . -- Drew Lawson "Parts is parts."