Re: Refuting the {Linz, Sipser, Kozen} HP Proofs (Halt decider details)

[olcott]

On 12/18/2020 2:19 PM, Kaz Kylheku wrote:
> On 2020-12-18, olcott <No...@NoWhere.com> wrote:
>> On 12/18/2020 1:12 PM, Kaz Kylheku wrote:
>>> On 2020-12-18, olcott <No...@NoWhere.com> wrote:
>>>> On 12/18/2020 12:02 PM, Kaz Kylheku wrote:
>>>>> On 2020-12-17, olcott <No...@NoWhere.com> wrote:
>>>>>>> Your approach would require the multiple invocations of that UTM to be
>>>>>>> diddled by an interfering process into incorrectly producing different
>>>>>>> results.
>>>>>>>
>>>>>>
>>>>>> It is only the equivalent of UTM Halts simulating UTM H_Hat simulating
>>>>>> UTM Halts simulating UTM H_Hat... that is cut off from simulating UTM
>>>>>> Halts again by the first instance of Halts().
>>>>>
>>>>> What you're missing is that each Halts *invocation* is a new TM that
>>>>> must start in a completely blank state, with no information other than
>>>>> what is provided in its arguments.
>>>>>
>>>>
>>>> Yes, except that the preceding simulations in the simulation hierarchy
>>>> are no longer a blank slate.
>>>
>>> Except that it is so in the proofs that you're trying to refute.
>>>
>>> In the proof, each call to Halts(A, B) is an absolutely blank slate
>>
>> Yes that is the case, the rest seems to be too many details for you to
>> comprehend.
>>
>> You do not seem to be able to comprehend that within any emulation
>> hierarchy the pinnacle of this hierarchy is going to have the longest
>> execution trace of the instructions that were emulated within this
>> hierarchy at any point in the execution of the elements in this hierarchy.
>
> Oh, I understand it perfectly. What is supposed to be infinite recursion
> is chopped off at three levels, and so the first level is not the same
> as the third, because it is deeper.
>
> Problem is, this interference is coming from a global machine, and
> information from that machine is leaking into the program, changing its
> behavior in ways that are not allowed inside the proof.

It took me until now to empirically refute this claim with fully
operational code. Halts() does not need any global data it only needs
the local sequence of machine addresses that it simulates according to
this basic model of a halt decider:

bool Halts(u32 P, u32 I)
{
static u32* local_execution_trace_list;
bool Halted = false;
bool Aborted = false;
while (!Halted && !Aborted)
{
// EIP points to the next instruction to be simulated
PushBack(local_execution_trace_list, EIP);
Halted = DebugStep(P, I);
if (!Halted)
Aborted = Needs_To_Be_Aborted(local_execution_trace_list);
}
return !Aborted;
}

> In the proof, infinity does not end arbitrarily at three, so that very
> discrepancy casts a doubt on what you're doing. In the proof, if
> Halts(X, Y) itself calls Halts(X, Y), those calls are not
> distinguishable. Each one contains the same depth: infinity.
>
> In a honest simulation, if an infinite loop or infinitre recursion are
> identified by the machine, the machine must report that and just stop
> everything. It cannot be that the Halts function successfully returns a
> value because of such a condition. If such a behavior is observed, it
> can only be because the global machine leaked information into Halts.
>
>> I have the full 220 page execution trace of every line of user code and
>> operating system code that is executed in the whole process thus
>> empirical proof of this point.
>
>
>> Since you can't see this you are getting confused.
>
> Rather, perhaps since you CAN see that, you're using all those reams of
> output to make yourself more confused.
>


--
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein