On 2021-08-03 18:42, olcott wrote:
> On 8/3/2021 5:35 PM, André G. Isaak wrote:
>> On 2021-08-03 15:50, olcott wrote:
>>> On 8/3/2021 4:26 PM, André G. Isaak wrote:
>>>> On 2021-08-03 15:03, olcott wrote:
>>>>> On 8/3/2021 3:56 PM, André G. Isaak wrote:
>>>>>> On 2021-08-03 14:47, olcott wrote:
>>>>>>> On 8/3/2021 3:08 PM, André G. Isaak wrote:
>>>>>>>> On 2021-08-03 13:26, olcott wrote:
>>>>>>>>> On 8/3/2021 12:11 PM, André G. Isaak wrote:
>>>>>>>>>> On 2021-08-03 09:21, olcott wrote:
>>>>>>>>>>> On 8/3/2021 9:33 AM, Malcolm McLean wrote:
>>>>>>>>>>>> On Tuesday, 3 August 2021 at 14:00:28 UTC+1, olcott wrote:
>>>>>>>>>>>>> On 8/3/2021 12:29 AM, Malcolm McLean wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> You're trying to claim that H_Hat<H_Hat> doens't really
>>>>>>>>>>>>>> halt because
>>>>>>>>>>>>>> the recursion of H instances is terminated by H.
>>>>>>>>>>>>> No I have never been saying that. I am claiming that the
>>>>>>>>>>>>> input to H(P,P)
>>>>>>>>>>>>> never halts whether or not H terminates its simulation of
>>>>>>>>>>>>> this input.
>>>>>>>>>>>>>
>>>>>>>>>>>> We agree that P(P) halts.
>>>>>>>>>>>> So now you're drawing a distinction between P(P) and "the
>>>>>>>>>>>> input to H(P,P)".
>>>>>>>>>>>> ThIs is nonsense..
>>>>>>>>>>>
>>>>>>>>>>> Try and find any error in (a)(b)(c)(d) on page 6
>>>>>>>>>>>
>>>>>>>>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> The error, which has been pointed out repeatedly, is in your (b).
>>>>>>>>>>
>>>>>>>>>> You claim "there are no control flow instructions in the
>>>>>>>>>> execution trace that would escape the infinite recursion", but
>>>>>>>>>> there *are* flow control instructions. But your trace is
>>>>>>>>>> incomplete and skips over the call to B82 where these flow
>>>>>>>>>> control instructions reside.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Whether H aborts its simulation of P or not P never reaches its
>>>>>>>>> final state.
>>>>>>>>
>>>>>>>> But H's simulation of P is *not* a computation.
>>>>>>>>
>>>>>>>
>>>>>>> Sure it is.
>>>>>>> The pure simulation of a computation on its input is
>>>>>>> computationally equivalent to the direct execution of this same
>>>>>>> computation on its input.
>>>>>>
>>>>>> No. It isn't. A computation is a free-standing, self-contained
>>>>>> piece of code. When you run H(P, P) the computation P(P) isn't
>>>>>> being computed. It's being evaluated. H(P, P) is the only
>>>>>> computation being run in this case.
>>>>>>
>>>>>
>>>>> So you don't understand how UTMs work.
>>>>
>>>> I'm well aware of how UTMs work. I am also aware that an x86
>>>> simulator is not the same thing as a UTM.
>>>>
>>>
>>> It is equivalent. In any case my exactly same reasoning directly
>>> applies to the Linz proof.
>>
>> No, it isn't equivalent. A UTM takes a description of a *Turing
>> Machine* as its input. A description of an x86 program is not a Turing
>> Machine. How can two computations which take entirely distinct inputs
>> be equivalent?
>>
>
> Apparently you don't understand computational equivalence either.
>
>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>>> if M applied to wM halts, and
>>>
>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>> if M applied to wM does not halt
>>>
>>> When Ĥ is applied to its own Turing Machine description ⟨Ĥ⟩ the
>>> embedded halt decider at Ĥ.qx correctly decides that its input ⟨Ĥ⟩ ⟨Ĥ⟩
>
> Specifies a computation that halts.
>
>>> never halts.
>>
>> Inputs neither halt nor don't halt. Only computations halt. >
>> And Ĥ.qx isn't an 'embedded halt decider'. It is a state.
>>
>
> Linz stipulates that it <is> Turing machine H.

No he doesn't. Maybe you should learn what his notation actually means.
The copy of H includes all of the states from Ĥ.q0 through Ĥ.qx, not
just Ĥ.qx.

>>>>>> And your H *doesn't* perform a pure simulation of its input, so we
>>>>>> can't even talk about the simulation as being 'computationally
>>>>>> equivalent' to some computation.
>>>>>>
>>>>>
>>>>> The fact that the first seven instructions of P keep repeating
>>>>> while H is in pure simulation mode proves that H is doing pure
>>>>> simulation mode correctly.
>>>>
>>>> The problem is that your 'pure simulation mode' is a cheat.
>>>>
>>>
>>> That the execution trace of the simulation of P precisely corresponds
>>> to its source-code proves beyond all possible doubt that the pure
>>> simulation of P by H is correct. There is no way to wiggle out of this.
>>
>> No. It doesn't 'precisely correspond' to its source code because your
>> trace *omits* a big chunk of code.
>>
>
> *What details of this paragraph do you feel are incorrect (and why)*
>
> Because H only acts as a pure simulator of its input until after its
> halt status decision has been made it has no behavior that can possibly
> effect the behavior of its input. Because of this H screens out its own
> address range in every execution trace that it examines. This is why we
> never see any instructions of H in any execution trace after an input
> calls H.

The copy of H inside P is *not* the 'address range' of the Halt Decider.
It is part of P.

Rewrite your P as an actual *computation*. It isn't one as you've
written it. It therefore is *not* the H_Hat of Linz.

To accomplish this you minimally need to compile and link both H and P
separately to produce two complete *self-contained* executables. You
can't have both contained in the same executable.

I strongly suspect that your H is also not a computation, but since
you've never supplied the code for it I can't be sure.

>>>> Your H and P *need* to be independent, self-contained programs. They
>>>> need to both be compiled and linked separately resulting in two
>>>> different executables. This means that the copy of H contained in P
>>>> will be *distinct* from program H. It will be at an entirely
>>>> different address and any code inside H which tells it to ignore its
>>>> 'own code' will not result in it ignoring the H contained in P.
>>>>
>>>> That also means that any change in the "mode" in which the main H
>>>> runs *cannot* have any effect on what the H contained in P does.
>>>>
>>>> Your 'pure simulation mode' is only valid as a test if it applies
>>>> *only* to the behaviour of H, and not to the behaviour of the H
>>>> contained inside P.
>>>>
>>>> If you change what the H inside P does, you are then talking about
>>>> an *entirely different* computation which has no bearing on the
>>>> halting behaviour of P.
>>>>
>>>> You can't evaluate whether P halts by considering what some modified
>>>> version of P does, which is in effect what you are doing.
>>>>
>>>> André
>>>>
>>>
>>> That the execution trace of the simulation of P precisely corresponds
>>> to its source-code proves beyond all possible doubt that the pure
>>> simulation of P by H is correct. There is no way to wiggle out of this.
>>
>> No. It doesn't 'precisely correspond' to its source code because your
>> trace *omits* a big chunk of code.
>>
>
> *What details of this paragraph do you feel are incorrect (and why)*
>
> Because H only acts as a pure simulator of its input until after its
> halt status decision has been made it has no behavior that can possibly
> effect the behavior of its input. Because of this H screens out its own
> address range in every execution trace that it examines. This is why we
> never see any instructions of H in any execution trace after an input
> calls H.
>
>> Come back and post a complete trace once you've actually set up your H
>> and P *properly*. i.e. as two *separate* programs which have been
>> compiled and linked two form two separate, *complete* executables
>> where P does not call any code contained in H. If there is code in
>> common, it must be *duplicated* so that each executable contains its
>> own copy of this code.
>>
>> There is no point discussing your implementation where your H and P
>> are contained in a single executable. That's not how 'TM equivalents'
>> work, nor is it how the Linz Proof constructs H_Hat, and no
>> conclusions which you draw from such a mangled implementation can
>> possibly shed any light on the halting problem.
>>
>
> So when your reasoning fails to show that my H is incorrect you change
> the subject. It is true that the input to H(P,P) never halts therefore
> H(P,P)==0 is correct.
>
>> If you don't grasp why what you are doing is illegitimate, then I
>> suggest you go and actually learn what the term 'computation' means.
>
> The standard formal definition of computation, repeated in all the major
> textbooks, derives from these early ideas. Computation is defined as the
> execution sequences of halting Turing machines (or their equivalents).
> An execution sequence is the sequence of total configurations of the
> machine, including states of memory and control unit.

A computation is entirely *self-contained*. Your P is not. It calls H as
an external function call.

To be a computation, P must contain *all* of the code which it relies
on. It needs its own copy of H which is distinct from your halt decider.

André

--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.