Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #36568 > unrolled thread

Simulating halt decider H correctly decides halt status of pathological inputs (V2)

Back to article view | Back to comp.theory

Contents

  Simulating halt decider H correctly decides halt status of pathological inputs (V2) olcott <NoOne@NoWhere.com> - 2021-07-17 16:07 -0500
    Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 03:39 +0100
      Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) olcott <NoOne@NoWhere.com> - 2021-07-19 09:50 -0500
        Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:35 +0100
          Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) olcott <NoOne@NoWhere.com> - 2021-07-20 09:11 -0500
            Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 11:32 -0700
            Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100

#36568 — Simulating halt decider H correctly decides halt status of pathological inputs (V2)

// 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

[toc] | [next] | [standalone]

#36579

olcott <NoOne@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
wrong (according to everyone /but/ you).

> *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?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36640

On 7/17/2021 9:39 PM, Ben Bacarisse wrote:
> olcott <NoOne@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
> 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?
> 


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#36671

olcott <NoOne@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...

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

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36701

On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
> olcott <NoOne@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...
> 
> 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));
}

_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)



-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#36717

On 7/20/21 7:11 AM, olcott wrote:
> On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
>> olcott <NoOne@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...
>>
>> 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.
> 

Slight error that is important, the Halt Decider needs to correctly
decide that Halting Status of the ACTUAL machine that the input represents.

The input is the 'representation' of the machine.

What the machine ACTUALLY does when run NOT as a simulation is Halt.

The basic trace is

Main calls P(P)
P calls H(P,P)
H starts up a simulation of P(P), which it sees that calling H(P,P)
which eventually hits the state that H decides (incorrectly) implies
infinite execution, then H stops its simulation of P(P) returns to its
calling P, and that returns to main which end the execution as a halting
computation.

H decided incorrectly because it didn't take into account that the copy
of H it was simulating will eventually do the same thing (if the
simulation was continued longer) and thus the P that it was simulating
would eventually come to a halt despite the fact that H thought otherwise.

You logical error is that when YOU try to argue about what will happen,
you change not just the particular instance you are trying to reason
about, but the global definition of H, including the copys of H that are
embedded into the Machine P that is going to be simulated, and this
changes the problem being looked at.

[toc] | [prev] | [next] | [standalone]

#36745

olcott <NoOne@NoWhere.com> writes:

> On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
>> olcott <NoOne@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...
>> 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.

H(P, I) is required to correctly determine whether P(I) halts or not.
P(P) halts (according to you).  H(P, P) == 0 (according to you).  That
is wrong.

> 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.

You don't dispute about the two key facts (because they come from you):
P(P) halts and H(P, P) == 0.  Waffle all you like, but unless you
retract one or both of these, then H is wrong about the one case you
care about.

> Simulating partial halt decider H correctly decides that P(P) never
> halts

P(P) halts (according to you).  H incorrectly decides it does not.

-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.theory

csiph-web