info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Simulating halt decider H correctly decides halt status of pathological inputs (V2)
1 view
Skip to first unread message
olcott
Jul 17, 2021, 5:07:23 PM7/17/21
to
// Based on: Strachey(1965) "An impossible program"
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", P((u32)P);
}
*Conventional Halt Deciding Axiom*
When the pure simulation of the machine description ⟨P⟩ of a machine P
on its input I never halts we know that P(I) never halts. // based on
UTM(⟨P⟩,I) ≡ P(I)
*Stipulated Definition of Halting*
An input to a halt decider is defined to halt if and only if this input
stops running while simulating halt decider H remains a pure simulator
of this input.
*Pathological Input* to a halt decider is defined as any input that was
defined to do the opposite of whatever its corresponding halt decider
decides.
The stipulative definition of a halting computation is equivalent to the
conventional definition of a halting computation:
(a) Every Turing Machine Description M that halts on its input I is an
element of the set of halting computations.
(b) Every element of the set of halting computations is a member of the
set of computations having the Stipulative_Halts() property.
The Stipulated Definition of Halting does provide the means to correctly
decide the halting status of Pathological Inputs.
When the computation: int main() { P(P); } stops running this provides
no evidence what-so-ever that H(P,P)==0 is not true because the
computation H(P,P)==0 meets the stipulative definition of a non-halting
computation.
When we stipulate that a cat is any animal having DNA that exactly
matches cat DNA then when this cat barks or even gives birth to puppies
we know that it is definitely a cat by definition.
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", P((u32)P);
}
*Conventional Halt Deciding Axiom*
When the pure simulation of the machine description ⟨P⟩ of a machine P
on its input I never halts we know that P(I) never halts. // based on
UTM(⟨P⟩,I) ≡ P(I)
*Stipulated Definition of Halting*
An input to a halt decider is defined to halt if and only if this input
stops running while simulating halt decider H remains a pure simulator
of this input.
*Pathological Input* to a halt decider is defined as any input that was
defined to do the opposite of whatever its corresponding halt decider
decides.
The stipulative definition of a halting computation is equivalent to the
conventional definition of a halting computation:
(a) Every Turing Machine Description M that halts on its input I is an
element of the set of halting computations.
(b) Every element of the set of halting computations is a member of the
set of computations having the Stipulative_Halts() property.
The Stipulated Definition of Halting does provide the means to correctly
decide the halting status of Pathological Inputs.
When the computation: int main() { P(P); } stops running this provides
no evidence what-so-ever that H(P,P)==0 is not true because the
computation H(P,P)==0 meets the stipulative definition of a non-halting
computation.
When we stipulate that a cat is any animal having DNA that exactly
matches cat DNA then when this cat barks or even gives birth to puppies
we know that it is definitely a cat by definition.
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott
Jul 19, 2021, 10:50:40 AM7/19/21
to
On 7/17/2021 9:39 PM, Ben Bacarisse wrote:
> wrong (according to everyone /but/ you).
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
P((u32)P);
}
The fact is that the above computation never ever halts unless some H
aborts some P thus proving beyond all possible doubt that H[0] does
correctly decide that P[2] (zero based addressing) never halts.
>
>> *Stipulated Definition of Halting*
>> An input to a halt decider is defined to halt if and only if this
>> input stops running while simulating halt decider H remains a pure
>> simulator of this input.
>
> Why do you think anyone else cares about this silly definition?
> olcott <No...@NoWhere.com> writes:
>
>> // Based on: Strachey(1965) "An impossible program"
>> // https://doi.org/10.1093/comjnl/7.4.313
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> Output("Input_Halts = ", P((u32)P);
>> }
>
> P(P) halts (according to you). H(P,P) == 0 (according to you). This is
>
>> // Based on: Strachey(1965) "An impossible program"
>> // https://doi.org/10.1093/comjnl/7.4.313
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> Output("Input_Halts = ", P((u32)P);
>> }
>
> wrong (according to everyone /but/ you).
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
}
The fact is that the above computation never ever halts unless some H
aborts some P thus proving beyond all possible doubt that H[0] does
correctly decide that P[2] (zero based addressing) never halts.
>
>> *Stipulated Definition of Halting*
>> An input to a halt decider is defined to halt if and only if this
>> input stops running while simulating halt decider H remains a pure
>> simulator of this input.
>
olcott
Jul 20, 2021, 10:11:44 AM7/20/21
to
On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> P((u32)P);
>> }
>>
>> The fact is that the above computation never ever halts unless...
> olcott <No...@NoWhere.com> writes:
>
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> P((u32)P);
>> }
>>
>
> The fact is that P(P) halts (according to you). H(P,P) == 0 (according
> to you). That is wrong. You know it's wrong:
>
> Me: Every computation that halts, for whatever reason, is a halting
> computation.
>
> You: OK
>
The halt decider is only required to correctly decide the halt status of
its input. Anyone the knows the x86 language well enough (apparently not
you) can see that the code of P provides no escape from its infinitely
nested simulation.
That you continue to assert that I am wrong entirely on the basis of
your ignorance of the x86 language is quite foolish.
Simulating partial halt decider H correctly decides that P(P) never
halts (V0)
// Strachey(1965) "An impossible program"
// CPL translated to C
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
}
_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
[00000c5e](05) 68360c0000 push 00000c36
[00000c63](05) e8fefcffff call 00000966
[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
[00000c5e][00101722][00000c36] 68360c0000 push 00000c36
[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
[00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][002117c2][00000c36] 51 push ecx
[00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)
[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
[00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][0025c1ea][00000c36] 51 push ecx
[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)
0 new messages