Does H(P,P) correctly determine the halt status of the halting problem's pathological input?

[PeteOlcott]

I rewrote this question so that a software engineer of ordinary skill can easily verify that the simulated P does call H in what is essentially infinite recursion. This simplification is the result of an extensive review (23 emails) by a leading computer scientist over the weekend.

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

The following H and P have the above specified pathological relationship to each other.

typedef void (*ptr)();
int H(ptr p, ptr i);

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

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

Simulating halt decider H detects that its simulated input is essentially calling H in infinite recursion. H aborts its simulation on this basis and rejects this input as non-halting.

Once this halt deciding principle is accepted
A halt decider must compute the mapping from its inputs to an accept or reject state on the basis of the actual behavior that is actually specified by these inputs.

Then (by logical necessity) this is understood to implement that
Every simulating halt decider that correctly simulates its input until it correctly predicts that this simulated input would never terminate normally, correctly rejects this input as non-halting.

The execution trace of function P() simulated by function H() shows:
(1) Function H() is called from P().
(2) With the same parameters to H().
(3) With no instructions in P() that could possibly escape this infinitely recursive simulation.

This proves that H(P,P) correctly predicts that its correctly simulated input would never terminate normally.

[Skepdick]

I rewrote this question so that a software engineer of ordinary skill can easily verify that the simulated P does call H in what is essentially infinite recursion. This simplification is the result of an extensive review (23 emails) by a leading computer scientist over the weekend.

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

The following H and P have the above specified pathological relationship to each other.

typedef void (*ptr)();
int H(ptr p, ptr i);

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

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

Pete,

How many times must it be explained to you? Your type definition for the H function is wrong.
The way you translated the English specification of the halting problem into C is wrong.

Please read, re-read, re-re-re-re-re-re read (a million times over) until you understand what this sentence means:

program P can pass its own source and its input to H

The inputs to H (as specified in the halting problem) are NOT pointers! The input to H is source code. PLAIN TEXT!

This is the type-signature of H!

Code: Select all

int H(char [] program_source, char[] program_input);

Passing a pointer to a function is not the same thing as a passing source code (PLAIN TEXT!) to a function!

You have to pass this exact string as an input to H!

void P(ptr x)\n{\nif (H(x, x))\nHERE: goto HERE;\nreturn;\n}

[Skepdick]

Your code doesn't compile. Because H is UNDEFINED.

Are you going to give us the source code for H already or what? It's not like this is the first or 10th time I am asking.

Code: Select all

➜  ~ cat halting-decider.c
typedef void (*ptr)();
int H(ptr p, ptr i);

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

int main()
{
 H(P, P);
}

Code: Select all

➜  ~ gcc halting-decider.c
Undefined symbols for architecture x86_64:
  "_H", referenced from:
      _P in halting-decider-8ec4f5.o
      _main in halting-decider-8ec4f5.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

[Skepdick]

This simplification is the result of an extensive review (23 emails) by a leading computer scientist over the weekend.

You mean all the people on comp.ai.philosophy who are telling you the exact same thing I am telling you?

All of those people are basically calling you an idiot. Because you are an idiot.

[wtf]

You mean all the people on comp.ai.philosophy who are telling you the exact same thing I am telling you?

Wow the old Usenet, still around out there. Like coming across a hula hoop in the attic.

[PeteOlcott]

It is very obviously the case that

typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider

void P(ptr x)
{
int Halt_Status = H(x, x);
if (Halt_Status)
HERE: goto HERE;
return;
}

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

When simulating halt decider H(P,P) simulates its input we can see that:
(1) Function H() is called from P().
(2) With the same arguments to H().
(3) With no instructions in P preceding its invocation of H(P,P).

The above shows that the simulated P cannot possibly terminate normally. Because H can see the same (1)(2)(3) that we see H aborts its simulation of P and rejects P as non-halting.

The above shows that the simulated P cannot possibly terminate normally.
H(P,P) simulates its input then P calls H(P,P) to simulate itself again.
H can see that this otherwise infinitely nested simulation would never end.
Because H can see the same (1)(2)(3) that we see H aborts its simulation of P
and rejects P as non-halting.

H has a pointer to the machine code as its input that it simulates using a world class x86 emulator. This is equivalent to passing a pointer to the finite string C source-code to H and H simulating this input with a C language interpreter. The end result its the same.

[Skepdick]

It is very obviously the case that
...

When simulating halt decider H(P,P) simulates its input we can see that:
(1) Function H() is called from P().

It's very obvious that you are lying.

P can never call H, because H is undefined.

Don't argue with me - argue with the compiler/linker.

➜ ~ gcc halt-decider.c
Undefined symbols for architecture x86_64:
"_H", referenced from:
_P in halt-decider-e9bb58.o
_main in halt-decider-e9bb58.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

What you are hiding from us; and from yourself is that your program has a runtime dependency on H.
Untill you tell your linker which dynamic library contains the implementation of H that code will never compile.
Until you specify the dynamic library containing H that code will never link; or execute.

Because your dynamic linker and your runtime have no idea what H is.

[PeteOlcott]

It is very obviously the case that
...

When simulating halt decider H(P,P) simulates its input we can see that:
(1) Function H() is called from P().

It's obvious that you are lying.

P can never call H, because H is undefined.
If it's not defined - it's not callable.

Don't argue with me - argue with the compiler/linker.

That I have not yet published the 50 pages of source-code for the x86utm
operating system or the 10 pages of source-code for my halt decider does
not mean that they do not exist.

Any fully competent software engineer can easily validate that H(P,P)
correctly determines that its correctly simulated input cannot possibly
terminate normally without any need to see the source-code for H.
H simply examines the same (1)(2)(3) criteria that we can see and rejects
its input on this basis.

[Skepdick]

That I have not yet published the 50 pages of source-code for the x86utm
operating system or the 10 pages of source-code for my halt decider does
not mean that they do not exist.

That's precisely what it means.

"H is undefined"
"Symbol H not found"
"H does not exist"

Those phraseses are synonymous.

Don't argue with me - argue with the compiler/linker.

Code: Select all

➜  ~ gcc halt-decider.c
Undefined symbols for architecture x86_64:
  "_H", referenced from:
      _P in halt-decider-e72906.o
      _main in halt-decider-e72906.o
ld: symbol(s) not found for architecture x86_64

Any fully competent software engineer...

You are too incompetent to determine necessary competence.

I am sure potential employers have already told you that?

without any need to see the source-code for H.

there is every need to see the source code, or the object code, or the library, or the executable containing H

because...

H simply examines the same (1)(2)(3) criteria that we can see and rejects
its input on this basis.

I don't need you to tell me what H does. I need you to give me H so that I can simulate/emulate it and see what it does.

N.B N.B N.B N.B I don't want to call your copy of H. I want execute/run/evaluate/simulate/emulate my copy of H for myself!.

I want to do to H the exact same thing you are doing for P! I want to evaluate/reduce H!

When I execute my own copy of H (which, according to you "correctly determines" that P doesn't halt)... THEN P halts.