On 8/14/2021 11:35 AM, wij wrote:
> On Sunday, 15 August 2021 at 00:16:20 UTC+8, olcott wrote:
>> On 8/14/2021 11:05 AM, wij wrote:
>>> On Saturday, 14 August 2021 at 23:18:03 UTC+8, olcott wrote:
>>>> This exact same analysis always applies to the input to H(P,P) no matter
>>>> how it is called including this example:
>>>>
>>>> int main()
>>>> {
>>>> P((u32)P);
>>>> }
>>>>
>>>> the Turing machine halting problem. Simply stated, the problem
>>>> is: given the description of a Turing machine M and an input w,
>>>> does M, when started in the initial configuration q0w, perform a
>>>> computation that eventually halts? (Linz:1990:317).
>>>>
>>>> In computability theory, the halting problem is the problem of
>>>> determining, from a description of an arbitrary computer program
>>>> and an input, whether the program will finish running, or continue
>>>> to run forever. https://en.wikipedia.org/wiki/Halting_problem
>>>>
>>>> Because the halting problem only requires that the (at least partial)
>>>> halt decider decide its input correctly the fact that the direct
>>>> invocation of P(P) is not an input to H, means that it is not relevant
>>>> to the halting problem.
>>>
>>> I do not know English well, but I (almost every programmer) am sure the halting
>>> problem means a program H decides whether P(input) will halt or not.
>>> If the quoted texts is read to you differently, it is the problem of that texts.
>>> Submit message to the authors.
>>>
>> The quoted texts are accurate. The (at least partial) halt decider must
>> only correctly decide the halt status of its input. Computations that
>> are not inputs to the halt decider do not pertain to the halting problem.
>
> Obviously the quoted text means differently to you and almost all programmers in
> the world. You are addressing your own interpretation. This is OK, but the
> interpretation is meaningless.

"the description of a Turing machine M" does not mean Turing machine M.
If people interpret this to mean Turing machine M they are wrong.

>>> If the direct invocation of P(P) is not relevant to the halting problem, then
>>> H can do whatever you like, therefore, meaningless if not garbage.
>>>
>> The halting problem is only concerned with an at least partial halt
>> decider correctly deciding whether or not its input halts, thus it can
>> do whatever its wants as long as it does decide the correct halt status
>> of its input.
>>
>
> int H2(Prog P) {
> return 0;
> }
> What is the difference of your H with H2?
> H2 can also correctly (at least partial) answer the halting problem, and can
> be verified.
>

My H has intelligence and can be verified to derive a halt status that
corresponds to every halting computation and can be verified to derive a
halt status that corresponds to that halt status of every input that it
determines never halts.

H is always correct for all:
(a) halting computations.
(b) computations that it decides never halt.

>> In every configuration H does correctly decide that its input (P,P)
>> never halts. This can be verified beyond all possible doubt by the x86
>> execution trace of the simulation of P(P) shown below.
>>>> The P(P) of main() only halts because H(P,P) correctly decides that its
>>>> input never halts. This cause-and-effect relationship between the
>>>> simulated P and the executed P proves that the simulated P and the
>>>> executed P are distinctly different computations.
>>>>
>>>> Because they are different computations the fact that the executed P
>>>> halts does not contradict the fact that the simulated P never halts.
>>>>
>>>> While H remains in pure simulation mode simulating the input to H(P,P)
>>>> this simulated input never halts thus conclusively proving that H
>>>> decides this input correctly.
>>>>
>>>> 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.
>>>>
>>>> *Halting computation* is any computation that eventually reaches its own
>>>> final state. This criteria divides computations that halt from those
>>>> that merely stop running because their simulation was aborted.
>>>>
>>>> A Turing machine is said to halt whenever it reaches a configuration
>>>> for which δ is not defined; this is possible because δ is a partial
>>>> function. In fact, we will assume that no transitions are defined for
>>>> any final state, so the Turing machine will halt whenever it enters a
>>>> final state. (Linz:1990:234)
>>>>
>>>> // Simplified Linz Ĥ (Linz:1990:319)
>>>> // Strachey(1965) CPL translated to C
>>>> void P(u32 x)
>>>> {
>>>> if (H(x, x))
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>> Output("Input_Halts = ", H((u32)P, (u32)P));
>>>> }
>>>>
>>>> _P()
>>>> [00000c36](01) 55 push ebp
>>>> [00000c37](02) 8bec mov ebp,esp
>>>> [00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
>>>> [00000c3c](01) 50 push eax
>>>> [00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
>>>> [00000c40](01) 51 push ecx
>>>> [00000c41](05) e820fdffff call 00000966 // call H
>>>> [00000c46](03) 83c408 add esp,+08
>>>> [00000c49](02) 85c0 test eax,eax
>>>> [00000c4b](02) 7402 jz 00000c4f
>>>> [00000c4d](02) ebfe jmp 00000c4d
>>>> [00000c4f](01) 5d pop ebp
>>>> [00000c50](01) c3 ret
>>>> Size in bytes:(0027) [00000c50]
>>>>
>>>> _main()
>>>> [00000c56](01) 55 push ebp
>>>> [00000c57](02) 8bec mov ebp,esp
>>>> [00000c59](05) 68360c0000 push 00000c36 // push P
>>>> [00000c5e](05) 68360c0000 push 00000c36 // push P
>>>> [00000c63](05) e8fefcffff call 00000966 // call H(P,P)
>>>> [00000c68](03) 83c408 add esp,+08
>>>> [00000c6b](01) 50 push eax
>>>> [00000c6c](05) 6857030000 push 00000357
>>>> [00000c71](05) e810f7ffff call 00000386
>>>> [00000c76](03) 83c408 add esp,+08
>>>> [00000c79](02) 33c0 xor eax,eax
>>>> [00000c7b](01) 5d pop ebp
>>>> [00000c7c](01) c3 ret
>>>> Size in bytes:(0039) [00000c7c]
>>>>
>>>> machine stack stack machine assembly
>>>> address address data code language
>>>> ======== ======== ======== ========= =============
>>>> [00000c56][0010172a][00000000] 55 push ebp
>>>> [00000c57][0010172a][00000000] 8bec mov ebp,esp
>>>> [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P
>>>> [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P
>>>> [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)
>>>>
>>>> Begin Local Halt Decider Simulation at Machine Address:c36
>>>> [00000c36][002117ca][002117ce] 55 push ebp
>>>> [00000c37][002117ca][002117ce] 8bec mov ebp,esp
>>>> [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
>>>> [00000c3c][002117c6][00000c36] 50 push eax // push P
>>>> [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
>>>> [00000c40][002117c2][00000c36] 51 push ecx // push P
>>>> [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)
>>>>
>>>> We can see that the first seven lines of P repeat. P calls H(P,P) that
>>>> simulates P(P) that calls H(P,P) in a cycle the never stops unless H
>>>> stops simulating its input. When H does stop simulating its input P
>>>> never reaches its final state of [00000c50] therefore never halts even
>>>> though it stops running.
>>>>
>>>> [00000c36][0025c1f2][0025c1f6] 55 push ebp
>>>> [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
>>>> [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
>>>> [00000c3c][0025c1ee][00000c36] 50 push eax // push P
>>>> [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
>>>> [00000c40][0025c1ea][00000c36] 51 push ecx // push P
>>>> [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
>>>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>>>>
>>>> [00000c68][0010172a][00000000] 83c408 add esp,+08
>>>> [00000c6b][00101726][00000000] 50 push eax
>>>> [00000c6c][00101722][00000357] 6857030000 push 00000357
>>>> [00000c71][00101722][00000357] e810f7ffff call 00000386
>>>> Input_Halts = 0
>>>> [00000c76][0010172a][00000000] 83c408 add esp,+08
>>>> [00000c79][0010172a][00000000] 33c0 xor eax,eax
>>>> [00000c7b][0010172e][00100000] 5d pop ebp
>>>> [00000c7c][00101732][00000068] c3 ret
>>>> Number_of_User_Instructions(27)
>>>> Number of Instructions Executed(23721)
>>>>
>>>> *Strachey, C 1965* An impossible program The Computer Journal, Volume
>>>> 7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313
>>>>
>>>> *Linz, Peter 1990* An Introduction to Formal Languages and Automata.
>>>> Lexington/Toronto: D. C. Heath and Company.
>>>>
>>>> --
>>>> Copyright 2021 Pete Olcott
>>>>
>>>> "Great spirits have always encountered violent opposition from mediocre
>>>> minds." Einstein
>>
>>
>> --
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein

--
Copyright 2021 Pete Olcott

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