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

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

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 »

The input to H(P,P) would never reach its final state (the definition of halting) no matter how long H kept simulating it, thus H is correct to reject this input as non-halting.
Skepdick
Posts: 14362
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: Tue May 17, 2022 1:12 am The input to H(P,P) would never reach its final state (the definition of halting) no matter how long H kept simulating it, thus H is correct to reject this input as non-halting.
Which is precisely why you can't solve this problem for H(H, H).

If you terminate H as non-halting for itself, then is it halting or non-halting?
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: Tue May 17, 2022 1:21 am
PeteOlcott wrote: Tue May 17, 2022 1:12 am The input to H(P,P) would never reach its final state (the definition of halting) no matter how long H kept simulating it, thus H is correct to reject this input as non-halting.
Which is precisely why you can't solve this problem for H(H, H).

If you terminate H as non-halting for itself, then is it halting or non-halting?
As long as I have refuted the conventional HP proof pattern I have refuted all of the conventional proofs.
Skepdick
Posts: 14362
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: Tue May 17, 2022 1:30 am As long as I have refuted the conventional HP proof pattern I have refuted all of the conventional proofs.
No, you haven't.

If H terminates its own execution because it detected itself as being stuck in an infinite loop then H is not stuck in an infinite loop.

It can't be stuck in an infinite loop BECAUSE IT TERMINATED ITS OWN EXECUTION
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: Tue May 17, 2022 1:34 am
PeteOlcott wrote: Tue May 17, 2022 1:30 am As long as I have refuted the conventional HP proof pattern I have refuted all of the conventional proofs.
No, you haven't.

If H terminates its own execution because it detected itself as being stuck in an infinite loop then H is not stuck in an infinite loop.

It can't be stuck in an infinite loop BECAUSE IT TERMINATED ITS OWN EXECUTION
H detects that its input would never reach its own final state, thus H correctly rejects (P,P)
Skepdick
Posts: 14362
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: Tue May 17, 2022 2:36 am H detects that its input would never reach its own final state, thus H correctly rejects (P,P)
Precisely! You are a liar!

By definition IF H can solve the halting problem for P then P is a less powerful model of computation than H.

You have "solved" a weaker form of the argument. That's called a strawman.
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: Tue May 17, 2022 10:57 am
PeteOlcott wrote: Tue May 17, 2022 2:36 am H detects that its input would never reach its own final state, thus H correctly rejects (P,P)
Precisely! You are a liar!

By definition IF H can solve the halting problem for P then P is a less powerful model of computation than H.

You have "solved" a weaker form of the argument. That's called a strawman.
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
This is that code:

Code: Select all

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

int main() 
{ 
  Output("Input_Halts = ", H((u32)P, (u32)P)); 
}
Skepdick
Posts: 14362
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: Tue May 17, 2022 4:09 pm
Skepdick wrote: Tue May 17, 2022 10:57 am
PeteOlcott wrote: Tue May 17, 2022 2:36 am H detects that its input would never reach its own final state, thus H correctly rejects (P,P)
Precisely! You are a liar!

By definition IF H can solve the halting problem for P then P is a less powerful model of computation than H.

You have "solved" a weaker form of the argument. That's called a strawman.
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
This is that code:

Code: Select all

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

int main() 
{ 
  Output("Input_Halts = ", H((u32)P, (u32)P)); 
}
No, it isn't. You seem to be struggling with basic English comprehension.

The type-signature of your H is wrong.

Nowhere in the example above are you passing the source code for P to H.
You are passing a reference of P to H.

This is closer to what you are looking for:

Code: Select all

int main()
{
  char program[] = "void P(char x[]){ if(H(x,x)) HERE: goto HERE; return; }"
  Output("Input_Halts = ", H(program, program));
}
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: Tue May 17, 2022 4:53 pm
PeteOlcott wrote: Tue May 17, 2022 4:09 pm
Skepdick wrote: Tue May 17, 2022 10:57 am
Precisely! You are a liar!

By definition IF H can solve the halting problem for P then P is a less powerful model of computation than H.

You have "solved" a weaker form of the argument. That's called a strawman.
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
This is that code:

Code: Select all

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

int main() 
{ 
  Output("Input_Halts = ", H((u32)P, (u32)P)); 
}
No, it isn't. You seem to be struggling with basic English comprehension.

The type-signature of your H is wrong.

Nowhere in the example above are you passing the source code for P to H.
You are passing a reference of P to H.

This is closer to what you are looking for:

Code: Select all

int main()
{
  char program[] = "void P(char x[]){ if(H(x,x)) HERE: goto HERE; return; }"
  Output("Input_Halts = ", H(program, program));
}
Passing a literal string of x86 machine language of P is equivalent to passing the source code of P.

The advantage of the machine code is that it already has been translated into a directed graph of all control flow.
Skepdick
Posts: 14362
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: Tue May 17, 2022 5:14 pm Passing a literal string of x86 machine language of P is equivalent to passing the source code of P.
You are not passing a literal string of x86 machine language! You are passing a reference to a memory address!
You are passing an entry point into P in memory - an executable addres space!

Seriously. https://stackoverflow.com/questions/373 ... g-by-value

Make H work like this...

Contents of main.c

Code: Select all

#include <stdio.h>

int main(){
    FILE *file = fopen("p.c", "r");
    char program[512];
    while (fgets(program, 512, file))
    fclose(file);
    Output("Input_Halts = ", H(program, program));
}
Contents of p.c

Code: Select all

void P(char x[]) { if (H(x, x)) HERE: goto HERE; return; }
Compile main.c and run it.
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 »

It is an easily verified fact that the input to H(P,P) specifies a non-halting sequence of configurations.

Code: Select all

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

int main() 
{ 
  Output("Input_Halts = ", H((u32)P, (u32)P)); 
}
It is the case that the above code matches the following code pattern:
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
Therefore I have correctly refuted the conventional HP proofs.
Skepdick
Posts: 14362
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: Tue May 17, 2022 5:35 pm It is the case that the above code matches the following code pattern
No.

It.
Does.
Not.
For any program H that might determine if programs halt, a "pathological"
program P, called with some input, can pass its own source
You are not passing any source code to H!

Pleasae learn the bloody difference between source code and bytecode.

https://en.wikipedia.org/wiki/Bytecode
https://en.wikipedia.org/wiki/Source_code
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 »

It does not have to be source-code. In only has to specify the actual behavior of the actual input.

A literal string of x86 machine code does this better than source-code because source-code is ambiguous.
Skepdick
Posts: 14362
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: Tue May 17, 2022 5:56 pm It does not have to be source-code. In only has to specify the actual behavior of the actual input.
Can you fucking read?
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
Which part of that sentence is confusing you?
PeteOlcott wrote: Tue May 17, 2022 5:56 pm source-code is ambiguous.
That is PRECISELY the fucking point.

You have to write a program which navigates its own ambiguity! You have to write a self-interpreting interpreter.
And apparently writing a self-interpreting interpreter is hard because of this thing called the normalization barrier - there is no such thing as normal/canonical form.

http://compilers.cs.ucla.edu/popl16/popl16-full.pdf
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 »

You simply do not have enough sufficiently relevant technical background to correctly review my work.

This work has already been very extensively reviewed with thousands of reviews and none of the reviews brought up the issue that you raised about source-code versus x86 machine language.
Post Reply