Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

Post Reply
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

The x86utm operating system was created so that every detail of the conventional halting problem counter example could be fully specified in C/x86.
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...

For any program f that might determine if programs halt, a "pathological" program g, called with some input, can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
This exact same relationship was created as H(P,P), shown below.

This is the overview of the method for proving that this analysis is correct:
(a) Verify that the execution trace of P by H is correct by comparing this execution trace to the ax86 source-code of P.

(b) Verify that this execution trace shows that P is stuck in infinitely nested simulation (a non-halting behavior).

This proof can only be understood only by those having sufficient technical competence in:
(a) software engineering (recognizing infinite recursion in C and x86 code)
(b) the x86 programming language
(c) the C programming language and
(d) the details of how C is translated into x86 by the Microsoft C compilers.

Code: Select all

#include <stdint.h> 
#define u32 uint32_t 

void P(u32 x) 
{ 
  if (H(x, x)) 
    HERE: goto HERE; 
  return; 
} 

int main() 
{ 
  Output("Input_Halts = ", H((u32)P, (u32)P)); 
} 

_P() 
[00001352](01)  55              push ebp 
[00001353](02)  8bec            mov ebp,esp 
[00001355](03)  8b4508          mov eax,[ebp+08] 
[00001358](01)  50              push eax 
[00001359](03)  8b4d08          mov ecx,[ebp+08] 
[0000135c](01)  51              push ecx 
[0000135d](05)  e840feffff      call 000011a2 // call H 
[00001362](03)  83c408          add esp,+08 
[00001365](02)  85c0            test eax,eax 
[00001367](02)  7402            jz 0000136b 
[00001369](02)  ebfe            jmp 00001369 
[0000136b](01)  5d              pop ebp 
[0000136c](01)  c3              ret 
Size in bytes:(0027) [0000136c] 

_main() 
[00001372](01)  55              push ebp 
[00001373](02)  8bec            mov ebp,esp 
[00001375](05)  6852130000      push 00001352 // push P 
[0000137a](05)  6852130000      push 00001352 // push P 
[0000137f](05)  e81efeffff      call 000011a2 // call H 
[00001384](03)  83c408          add esp,+08 
[00001387](01)  50              push eax 
[00001388](05)  6823040000      push 00000423 // "Input_Halts = " 
[0000138d](05)  e8e0f0ffff      call 00000472 // call Output 
[00001392](03)  83c408          add esp,+08 
[00001395](02)  33c0            xor eax,eax 
[00001397](01)  5d              pop ebp 
[00001398](01)  c3              ret 
Size in bytes:(0039) [00001398] 

    machine   stack     stack     machine    assembly 
    address   address   data      code       language 
    ========  ========  ========  =========  ============= 
...[00001372][0010229e][00000000] 55         push ebp 
...[00001373][0010229e][00000000] 8bec       mov ebp,esp 
...[00001375][0010229a][00001352] 6852130000 push 00001352 // push P 
...[0000137a][00102296][00001352] 6852130000 push 00001352 // push P 
...[0000137f][00102292][00001384] e81efeffff call 000011a2 // call H 

Begin Local Halt Decider Simulation   Execution Trace Stored at:212352 
...[00001352][0021233e][00212342] 55         push ebp      // enter P 
...[00001353][0021233e][00212342] 8bec       mov ebp,esp 
...[00001355][0021233e][00212342] 8b4508     mov eax,[ebp+08] 
...[00001358][0021233a][00001352] 50         push eax      // push P 
...[00001359][0021233a][00001352] 8b4d08     mov ecx,[ebp+08] 
...[0000135c][00212336][00001352] 51         push ecx      // push P 
...[0000135d][00212332][00001362] e840feffff call 000011a2 // call H 
...[00001352][0025cd66][0025cd6a] 55         push ebp      // enter P 
...[00001353][0025cd66][0025cd6a] 8bec       mov ebp,esp 
...[00001355][0025cd66][0025cd6a] 8b4508     mov eax,[ebp+08] 
...[00001358][0025cd62][00001352] 50         push eax      // push P 
...[00001359][0025cd62][00001352] 8b4d08     mov ecx,[ebp+08] 
...[0000135c][0025cd5e][00001352] 51         push ecx      // push P 
...[0000135d][0025cd5a][00001362] e840feffff call 000011a2 // call H 
Local Halt Decider: Infinite Recursion Detected Simulation Stopped 
H sees that P is calling the same function from the same machine address with identical parameters, twice in sequence. This is the infinite recursion (infinitely nested simulation) non-halting behavior pattern.

Code: Select all

...[00001384][0010229e][00000000] 83c408     add esp,+08 
...[00001387][0010229a][00000000] 50         push eax 
...[00001388][00102296][00000423] 6823040000 push 00000423 // "Input_Halts = " 
---[0000138d][00102296][00000423] e8e0f0ffff call 00000472 // call Output 
Input_Halts = 0 
...[00001392][0010229e][00000000] 83c408     add esp,+08 
...[00001395][0010229e][00000000] 33c0       xor eax,eax 
...[00001397][001022a2][00100000] 5d         pop ebp 
...[00001398][001022a6][00000004] c3         ret 
Number of Instructions Executed(15892) lines = 237 pages 
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publicatio ... ulation_V5
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Wed May 11, 2022 6:57 pm The x86utm operating system was created so that every detail of the conventional halting problem counter example could be fully specified in C/x86.
That can't possibly be true. You are working with a particular model of computation married to the X86 instruction set. There's nothing universal about it.

The reason you don't understand the problem is because you continue to work at low levels of abstraction and you continue to trip up over the leaky abstractions between the assembler, the compiler and the syntax of your programming language.

The reason you don't understand the problem is because you are not using a programs which can treat other programs as data - you are only doing numeric computation using integers in C. Your programming language is not even capable of expressing symbolic computations. Heck there are no such things as symbols in C.

https://www.cs.cmu.edu/Groups/AI/html/c ... ode27.html

Use a homoiconic (self-interpreting!) computational model. Use LISP. Then your instruction-set will be about as close to the Lambda calculus as you can get without giving up your computer for pen and paper.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Thu May 12, 2022 9:44 am
PeteOlcott wrote: Wed May 11, 2022 6:57 pm The x86utm operating system was created so that every detail of the conventional halting problem counter example could be fully specified in C/x86.
That can't possibly be true. You are working with a particular model of computation married to the X86 instruction set. There's nothing universal about it.

The reason you don't understand the problem is because you continue to work at low levels of abstraction and you continue to trip up over the leaky abstractions between the assembler, the compiler and the syntax of your programming language.

The reason you don't understand the problem is because you are not using a programs which can treat other programs as data - you are only doing numeric computation using integers in C. Your programming language is not even capable of expressing symbolic computations. Heck there are no such things as symbols in C.
You simply are not competent to review my work as is proven that you can only make vague claims about it.
"you are not using a programs which can treat other programs as data"
It is a fact that H uses the finite strings of the machine code of P that is input to its interpreter.
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Thu May 12, 2022 4:41 pm You simply are not competent to review my work as is proven that you can only make vague claims about it.
"you are not using a programs which can treat other programs as data"
It is a fact that H uses the finite strings of the machine code of P that is input to its interpreter.
Why is it that you keep talking about this elusive function H yet you never seem to show it to us?
Why is it that you don't underrstand that the model of computation you are using (X86 assembly) is a push-down automaton. https://en.wikipedia.org/wiki/Pushdown_automaton

It's not as powerful as a Turing machine.

And lastly...Why is it that you don't seem to understand the difference between an interpreter and a self-interpreter?
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Thu May 12, 2022 5:38 pm
PeteOlcott wrote: Thu May 12, 2022 4:41 pm You simply are not competent to review my work as is proven that you can only make vague claims about it.
"you are not using a programs which can treat other programs as data"
It is a fact that H uses the finite strings of the machine code of P that is input to its interpreter.
Why is it that you keep talking about this elusive function H yet you never seem to show it to us?
Why is it that you don't underrstand that the model of computation you are using (X86 assembly) is a push-down automaton. https://en.wikipedia.org/wiki/Pushdown_automaton

It's not as powerful as a Turing machine.

And lastly...Why is it that you don't seem to understand the difference between an interpreter and a self-interpreter?
"Why is it that you keep talking about this elusive function H yet you never seem to show it to us?"
Because anyone that is technically competent can easily verify that H(P,P) does simulate its input correctly and this simulated input proves that it specifies infinitely nested simulation.

The C programming language <is> equivalent to TM computations for every computation that can be completed in the memory that is available.

It was quite difficult to be able to correctly specified unlimited recursive simulations, and because it is correctly working now that proves that I understand it.
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Thu May 12, 2022 6:22 pm "Why is it that you keep talking about this elusive function H yet you never seem to show it to us?"
Because anyone that is technically competent can easily verify that H(P,P) does simulate its input correctly and this simulated input proves that it specifies infinitely nested simulation.

The C programming language <is> equivalent to TM computations for every computation that can be completed in the memory that is available.

It was quite difficult to be able to correctly specified unlimited recursive simulations, and because it is correctly working now that proves that I understand it.
What or where is H?

Show it to me.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Thu May 12, 2022 6:32 pm
PeteOlcott wrote: Thu May 12, 2022 6:22 pm "Why is it that you keep talking about this elusive function H yet you never seem to show it to us?"
Because anyone that is technically competent can easily verify that H(P,P) does simulate its input correctly and this simulated input proves that it specifies infinitely nested simulation.

The C programming language <is> equivalent to TM computations for every computation that can be completed in the memory that is available.

It was quite difficult to be able to correctly specified unlimited recursive simulations, and because it is correctly working now that proves that I understand it.
What or where is H?

Show it to me.
H is so enormously more complex than the proof that I already provided that my reviewers would be hopelessly lost for years trying to understand it. If you can't understand the simple proof that I already provided then giving you material that is 1000-fold more complex can't possibly help.
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Thu May 12, 2022 6:57 pm H is so enormously more complex than the proof that I already provided that my reviewers would be hopelessly lost for years trying to understand it. If you can't understand the simple proof that I already provided then giving you material that is 1000-fold more complex can't possibly help.
You haven't shown a proof.

You have solved a particular case of non-halting behavior by constructing a program powerful enough to solve it.
This is so mundane i can't fathom why you might spend 15000 hours on it.

A more powerful computer can solve the halting problem for less powerful computers. We know this.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Thu May 12, 2022 7:01 pm
PeteOlcott wrote: Thu May 12, 2022 6:57 pm H is so enormously more complex than the proof that I already provided that my reviewers would be hopelessly lost for years trying to understand it. If you can't understand the simple proof that I already provided then giving you material that is 1000-fold more complex can't possibly help.
You haven't shown a proof.

You have solved a particular case of non-halting behavior by constructing a program powerful enough to solve it.
This is so mundane i can't fathom why you might spend 15000 hours on it.

A more powerful computer can solve the halting problem for less powerful computers. We know this.
I have shown all of the detail of exactly how this impossible input is correctly decided:
For any program H that might determine if programs halt, a "pathological"
program P, called with some input, can pass its own source and its input to
H and then specifically do the opposite of what H predicts P will do. No H
can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Thu May 12, 2022 8:25 pm I have shown all of the detail of exactly how this impossible input is correctly decided
Idiot. You have solved a particular case. You haven't solved a general case.

You have solves H(P,P) for a particular P. You haven't solved H(P, P) for every P.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Thu May 12, 2022 8:55 pm
PeteOlcott wrote: Thu May 12, 2022 8:25 pm I have shown all of the detail of exactly how this impossible input is correctly decided
Idiot. You have solved a particular case. You haven't solved a general case.

You have solves H(P,P) for a particular P. You haven't solved H(P, P) for every P.
Skepdick wrote: Thu May 12, 2022 8:55 pm
PeteOlcott wrote: Thu May 12, 2022 8:25 pm I have shown all of the detail of exactly how this impossible input is correctly decided
Idiot. You have solved a particular case. You haven't solved a general case.

You have solves H(P,P) for a particular P. You haven't solved H(P, P) for every P.
I have solved the particular case that all the halting problem proofs are based on, thus refuting all of these proofs.
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Thu May 12, 2022 9:05 pm I have solved the particular case that all the halting problem proofs are based on, thus refuting all of these proofs.
None of the proofs are based on a particular case, you dickhead.

You are misinterpreting the general for the particular.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Thu May 12, 2022 9:38 pm
PeteOlcott wrote: Thu May 12, 2022 9:05 pm I have solved the particular case that all the halting problem proofs are based on, thus refuting all of these proofs.
None of the proofs are based on a particular case, you dickhead.

You are misinterpreting the general for the particular.
This is the case that they are all based on:
For any program H that might determine if programs halt, a "pathological"
program P, called with some input, can pass its own source and its input to
H and then specifically do the opposite of what H predicts P will do. No H
can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by Skepdick »

PeteOlcott wrote: Thu May 12, 2022 10:30 pm
Skepdick wrote: Thu May 12, 2022 9:38 pm
PeteOlcott wrote: Thu May 12, 2022 9:05 pm I have solved the particular case that all the halting problem proofs are based on, thus refuting all of these proofs.
None of the proofs are based on a particular case, you dickhead.

You are misinterpreting the general for the particular.
This is the case that they are all based on:
For any program H that might determine if programs halt, a "pathological"
program P, called with some input, can pass its own source and its input to
H and then specifically do the opposite of what H predicts P will do. No H
can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
Do you understand the word "ANY"? In the sentence "For ANY program H".

This is the precise order of events.

1. Produce H (which you haven't done) which always returns an answer (yes or no) for ANY program P which takes ANY input I.

The type-signature of your program is like so:

Code: Select all

bool halting_decider(char program[], char input[])
{
      //Magic goes here.
      // return 1 if program(input) halts
      // return 0 if program(input) doesn't halt
}

2. ... I am not going to tell you absolutely anything about 2 until you produce H.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Post by PeteOlcott »

Skepdick wrote: Fri May 13, 2022 5:08 am
Do you understand the word "ANY"? In the sentence "For ANY program H".

This is the precise order of events.

1. Produce H (which you haven't done) which always returns an answer (yes or no) for ANY program P which takes ANY input I.

The type-signature of your program is like so:
All that I have to do to refute all of the conventional Halting problem proofs is defeat this one case:
For any program H that might determine if programs halt, a "pathological" program P, called with some input, can pass its own source and its input to H and then specifically do the opposite of what H predicts P will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
Post Reply