Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
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.
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
Which is precisely why you can't solve this problem for H(H, H).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.
If you terminate H as non-halting for itself, then is it halting or non-halting?
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
As long as I have refuted the conventional HP proof pattern I have refuted all of the conventional proofs.Skepdick wrote: ↑Tue May 17, 2022 1:21 amWhich is precisely why you can't solve this problem for H(H, H).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.
If you terminate H as non-halting for itself, then is it halting or non-halting?
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
No, you haven't.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.
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
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
H detects that its input would never reach its own final state, thus H correctly rejects (P,P)Skepdick wrote: ↑Tue May 17, 2022 1:34 amNo, you haven't.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.
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
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
Precisely! You are a liar!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)
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.
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
Skepdick wrote: ↑Tue May 17, 2022 10:57 amPrecisely! You are a liar!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)
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.
This is that code: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
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));
}
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
No, it isn't. You seem to be struggling with basic English comprehension.PeteOlcott wrote: ↑Tue May 17, 2022 4:09 pmSkepdick wrote: ↑Tue May 17, 2022 10:57 amPrecisely! You are a liar!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)
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.This is that code: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
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)); }
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));
}
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
Passing a literal string of x86 machine language of P is equivalent to passing the source code of P.Skepdick wrote: ↑Tue May 17, 2022 4:53 pmNo, it isn't. You seem to be struggling with basic English comprehension.PeteOlcott wrote: ↑Tue May 17, 2022 4:09 pmThis is that code: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
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)); }
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)); }
The advantage of the machine code is that it already has been translated into a directed graph of all control flow.
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
You are not passing a literal string of x86 machine language! You are passing a reference to a memory address!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 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));
}
Code: Select all
void P(char x[]) { if (H(x, x)) HERE: goto HERE; return; }
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
It is an easily verified fact that the input to H(P,P) specifies a non-halting sequence of configurations.
It is the case that the above code matches the following code pattern:
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));
}
Therefore I have correctly refuted the conventional HP proofs.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
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
No.PeteOlcott wrote: ↑Tue May 17, 2022 5:35 pm It is the case that the above code matches the following code pattern
It.
Does.
Not.
You are not passing any source code to H!For any program H that might determine if programs halt, a "pathological"
program P, called with some input, can pass its own source
Pleasae learn the bloody difference between source code and bytecode.
https://en.wikipedia.org/wiki/Bytecode
https://en.wikipedia.org/wiki/Source_code
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
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.
A literal string of x86 machine code does this better than source-code because source-code is ambiguous.
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
Can you fucking read?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.
Which part of that sentence is confusing you?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
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
-
- Posts: 1514
- Joined: Mon Jul 25, 2016 6:55 pm
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
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.
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.