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


Groups > comp.software-eng > #2789 > unrolled thread

The key basis of the refutation of the halting problem proofs

Started byolcott <NoOne@NoWhere.com>
First post2021-06-05 21:39 -0500
Last post2021-06-06 14:36 -0500
Articles 5 — 2 participants

Back to article view | Back to comp.software-eng


Contents

  The key basis of the refutation of the halting problem proofs olcott <NoOne@NoWhere.com> - 2021-06-05 21:39 -0500
    Re: The key basis of the refutation of the halting problem proofs Mr Flibble <flibble@reddwarf.jmc> - 2021-06-06 18:24 +0100
      Re: The key basis of the refutation of the halting problem proofs olcott <NoOne@NoWhere.com> - 2021-06-06 14:14 -0500
        Re: The key basis of the refutation of the halting problem proofs Mr Flibble <flibble@reddwarf.jmc> - 2021-06-06 20:32 +0100
          Re: The key basis of the refutation of the halting problem proofs olcott <NoOne@NoWhere.com> - 2021-06-06 14:36 -0500

#2789 — The key basis of the refutation of the halting problem proofs

Fromolcott <NoOne@NoWhere.com>
Date2021-06-05 21:39 -0500
SubjectThe key basis of the refutation of the halting problem proofs
Message-ID<z6udnZYotcDUqCH9nZ2dnUU7-ffNnZ2d@giganews.com>
When a simulating halt decider must abort the simulation of its input to 
prevent the infinite execution of this input, this input is correctly 
decided as not halting even though it has been forced to halt and thus 
halts.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 


// Simplified Linz Ĥ (Linz:1990:319)
void H_Hat(u32 P) {
   u32 Input_Halts = H(P, P);
   if (Input_Halts)
     HERE: goto HERE;
}

int main() {
   H_Hat((u32)H_Hat);
}

Because the input to H() on the first line of H_Hat() must be aborted to 
prevent its infinite execution this input is correctly decided as 
non-halting.

_H_Hat()
[00000af8](01)  55              push ebp
[00000af9](02)  8bec            mov ebp,esp
[00000afb](01)  51              push ecx
[00000afc](03)  8b4508          mov eax,[ebp+08]
[00000aff](01)  50              push eax
[00000b00](03)  8b4d08          mov ecx,[ebp+08]
[00000b03](01)  51              push ecx
[00000b04](05)  e81ffeffff      call 00000928
[00000b09](03)  83c408          add esp,+08
[00000b0c](03)  8945fc          mov [ebp-04],eax
[00000b0f](04)  837dfc00        cmp dword [ebp-04],+00
[00000b13](02)  7402            jz 00000b17
[00000b15](02)  ebfe            jmp 00000b15
[00000b17](02)  8be5            mov esp,ebp
[00000b19](01)  5d              pop ebp
[00000b1a](01)  c3              ret
Size in bytes:(0035) [00000b1a]

_main()
[00000b28](01)  55              push ebp
[00000b29](02)  8bec            mov ebp,esp
[00000b2b](05)  68f80a0000      push 00000af8
[00000b30](05)  e8c3ffffff      call 00000af8
[00000b35](03)  83c404          add esp,+04
[00000b38](02)  33c0            xor eax,eax
[00000b3a](01)  5d              pop ebp
[00000b3b](01)  c3              ret
Size in bytes:(0020) [00000b3b]

===============================
...[00000b28][001014cf][00000000](01)  55              push ebp
...[00000b29][001014cf][00000000](02)  8bec            mov ebp,esp
...[00000b2b][001014cb][00000af8](05)  68f80a0000      push 00000af8
...[00000b30][001014c7][00000b35](05)  e8c3ffffff      call 00000af8
...[00000af8][001014c3][001014cf](01)  55              push ebp
...[00000af9][001014c3][001014cf](02)  8bec            mov ebp,esp
...[00000afb][001014bf][00000000](01)  51              push ecx
...[00000afc][001014bf][00000000](03)  8b4508          mov eax,[ebp+08]
...[00000aff][001014bb][00000af8](01)  50              push eax
...[00000b00][001014bb][00000af8](03)  8b4d08          mov ecx,[ebp+08]
...[00000b03][001014b7][00000af8](01)  51              push ecx
...[00000b04][001014b3][00000b09](05)  e81ffeffff      call 00000928
Begin Local Halt Decider Simulation at Machine Address:af8
...[00000af8][0021156f][00211573](01)  55              push ebp
...[00000af9][0021156f][00211573](02)  8bec            mov ebp,esp
...[00000afb][0021156b][0020153f](01)  51              push ecx
...[00000afc][0021156b][0020153f](03)  8b4508          mov eax,[ebp+08]
...[00000aff][00211567][00000af8](01)  50              push eax
...[00000b00][00211567][00000af8](03)  8b4d08          mov ecx,[ebp+08]
...[00000b03][00211563][00000af8](01)  51              push ecx
...[00000b04][0021155f][00000b09](05)  e81ffeffff      call 00000928
...[00000af8][0025bf97][0025bf9b](01)  55              push ebp
...[00000af9][0025bf97][0025bf9b](02)  8bec            mov ebp,esp
...[00000afb][0025bf93][0024bf67](01)  51              push ecx
...[00000afc][0025bf93][0024bf67](03)  8b4508          mov eax,[ebp+08]
...[00000aff][0025bf8f][00000af8](01)  50              push eax
...[00000b00][0025bf8f][00000af8](03)  8b4d08          mov ecx,[ebp+08]
...[00000b03][0025bf8b][00000af8](01)  51              push ecx
...[00000b04][0025bf87][00000b09](05)  e81ffeffff      call 00000928
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
...[00000b09][001014bf][00000000](03)  83c408          add esp,+08
...[00000b0c][001014bf][00000000](03)  8945fc          mov [ebp-04],eax
...[00000b0f][001014bf][00000000](04)  837dfc00        cmp dword 
[ebp-04],+00
...[00000b13][001014bf][00000000](02)  7402            jz 00000b17
...[00000b17][001014c3][001014cf](02)  8be5            mov esp,ebp
...[00000b19][001014c7][00000b35](01)  5d              pop ebp
...[00000b1a][001014cb][00000af8](01)  c3              ret
...[00000b35][001014cf][00000000](03)  83c404          add esp,+04
...[00000b38][001014cf][00000000](02)  33c0            xor eax,eax
...[00000b3a][001014d3][00100000](01)  5d              pop ebp
...[00000b3b][001014d7][00000098](01)  c3              ret
Number_of_User_Instructions(39)
Number of Instructions Executed(26459)

-- 
Copyright 2021 Pete Olcott

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

[toc] | [next] | [standalone]


#2790

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-06-06 18:24 +0100
Message-ID<20210606182454.000075ce@reddwarf.jmc>
In reply to#2789
On Sat, 5 Jun 2021 21:39:16 -0500
olcott <NoOne@NoWhere.com> wrote:

> When a simulating halt decider must abort the simulation of its input
> to prevent the infinite execution of this input, this input is
> correctly decided as not halting even though it has been forced to
> halt and thus halts.
> 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
 
Except you are unable to decide when to abort the simulation unless you
also analyse branching logic predicated on arbitrary program input.
Until you achieve this you have not refuted anything of substance.

/Flibble

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


#2791

Fromolcott <NoOne@NoWhere.com>
Date2021-06-06 14:14 -0500
Message-ID<4KednXaWWJzpgyD9nZ2dnUU7-N2dnZ2d@giganews.com>
In reply to#2790
On 6/6/2021 12:24 PM, Mr Flibble wrote:
> On Sat, 5 Jun 2021 21:39:16 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> When a simulating halt decider must abort the simulation of its input
>> to prevent the infinite execution of this input, this input is
>> correctly decided as not halting even though it has been forced to
>> halt and thus halts.
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>   
> Except you are unable to decide when to abort the simulation unless you
> also analyse branching logic predicated on arbitrary program input.
> Until you achieve this you have not refuted anything of substance.
> 
> /Flibble
> 

When you say this you are making sure to not even glance at what I said 
on page 2.

-- 
Copyright 2021 Pete Olcott

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

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


#2792

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-06-06 20:32 +0100
Message-ID<20210606203207.00003f41@reddwarf.jmc>
In reply to#2791
On Sun, 6 Jun 2021 14:14:05 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 6/6/2021 12:24 PM, Mr Flibble wrote:
> > On Sat, 5 Jun 2021 21:39:16 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> > 
> >> When a simulating halt decider must abort the simulation of its
> >> input to prevent the infinite execution of this input, this input
> >> is correctly decided as not halting even though it has been forced
> >> to halt and thus halts.
> >>
> >> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> >   
> > Except you are unable to decide when to abort the simulation unless
> > you also analyse branching logic predicated on arbitrary program
> > input. Until you achieve this you have not refuted anything of
> > substance.
> > 
> > /Flibble
> > 
> 
> When you say this you are making sure to not even glance at what I
> said on page 2.
 
If I did that it would have the same effect as me reading the words
written in crayon on the walls of a padded cell by its previous
occupant.

I repeat: until you solve the problem of analysing branching logic
predicated on arbitrary program input you have not refuted anything of
substance.

Your "simulator" is based on emulating Intel x86 CPU is it not? Are
you aware that, like with most CPUs, an 80x86 allows memory to be
mapped to I/O devices rather than just RAM so a MOV instruction may be
reading/writing from/to a device? Device I/O is also considered program
"input" and can effectively be considered random in nature for the
purposes of this discussion, i.e. another form of "arbitrary program
input".

/Flibble

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


#2793

Fromolcott <NoOne@NoWhere.com>
Date2021-06-06 14:36 -0500
Message-ID<u8GdnSz8AtBMviD9nZ2dnUU7-S-dnZ2d@giganews.com>
In reply to#2792
On 6/6/2021 2:32 PM, Mr Flibble wrote:
> On Sun, 6 Jun 2021 14:14:05 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 6/6/2021 12:24 PM, Mr Flibble wrote:
>>> On Sat, 5 Jun 2021 21:39:16 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> When a simulating halt decider must abort the simulation of its
>>>> input to prevent the infinite execution of this input, this input
>>>> is correctly decided as not halting even though it has been forced
>>>> to halt and thus halts.
>>>>
>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>>    
>>> Except you are unable to decide when to abort the simulation unless
>>> you also analyse branching logic predicated on arbitrary program
>>> input. Until you achieve this you have not refuted anything of
>>> substance.
>>>
>>> /Flibble
>>>
>>
>> When you say this you are making sure to not even glance at what I
>> said on page 2.
>   
> If I did that it would have the same effect as me reading the words
> written in crayon on the walls of a padded cell by its previous
> occupant.
> 
> I repeat: until you solve the problem of analysing branching logic
> predicated on arbitrary program input you have not refuted anything of
> substance.
> 
> Your "simulator" is based on emulating Intel x86 CPU is it not? Are
> you aware that, like with most CPUs, an 80x86 allows memory to be
> mapped to I/O devices rather than just RAM so a MOV instruction may be
> reading/writing from/to a device? Device I/O is also considered program
> "input" and can effectively be considered random in nature for the
> purposes of this discussion, i.e. another form of "arbitrary program
> input".
> 
> /Flibble
> 

On page 2 I directly apply the computer science insights to the actual 
Linz proof, nitwit.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [standalone]


Back to top | Article view | comp.software-eng


csiph-web