Re: Solution to one instance of the Halting Problem [2017-03-14 inception date of simulating halt decider]

[olcott]

On 3/14/2017 9:05 AM, peteolcott wrote:
> https://simple.wikipedia.org/wiki/Halting_problem
>
> def P(F, I):
> if Simulate-Execute(F, I) // runs forever:
> return True;
> else:
> return False;
>
> def Q(F):
> return P(F, F); // works the same way as Linz because makes copy here
>
> def R(F):
> if Q(F):
> return True; //terminate
> else:
> while True: continue; //loop forever
>
> For simplicity we will assume that this whole process is executed inside a computer language interpreter, thus source-code can be directly executed.
>
> In conventional Turing Machine terminology this would be called a Universal Turing Machine and it would be executing a Turing Machine Description.
>
> We assume that the above program is stored in a string variable named R.
>
> We execute R with itself as input using the following interpreter command:
> Execute(R, R) // Executes the string named R with input R
>
> To make sure that P does not get stuck in an infinite loop P invokes Simulate-Execute(F, I) so that it can watch the execution trace of its input (F, I).
>
> This execution trace (shown below) shows the infinitely recursive structure of R. We successively rename inputs to P to make it clear that the evaluation sequence never ends…
>
> Simulate-Execute(R,R) --->Q(F) --->P( F, F) P examines (F, I)
> Simulate-Execute(F,I) --->Q(I) --->P( I, I) P examines (F1, I1)
> Simulate-Execute(F1,I1) --->Q(I1) --->P(I1, I1) P examines (F2, I2)
> Simulate-Execute(F2,I2) --->Q(I2) --->P(I2, I2) P examines (F3, I3)
> Simulate-Execute(F3,I3) --->Q(I3) --->P(I3, I3) P examines (F4, I4)
>
> In the above example P.Simulate-Execute(F, I) could detect through the simulated execution trace shown above that P(F, I) would not halt on its input. Because of this P(F, I) returns True which causes R to terminate with the correct halting decision.
>

--
Copyright 2023 Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

[Richard Damon]

Except that runnign R(R) directly itself will also call
Simulate-Execute(R,R) which will return the 0 to it, and it will halt,
thus showig that R(R) IS a Halting Operation.

Simulate-Execute has just made the mistake that it assumes that it won't
abort the simulations and return a 0 when it actually does.

And thus is in error.

This is your ancient error.