A pair of C functions are defined such that D has the halting problem
proofs pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on (b) Cannot possibly terminate normally
then it is understood that D is correctly determined to be non-halting.
We can know that D correctly simulated by H must have different behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship between D and H changes the behavior of D relative to H.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating (unless aborted)*
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*Termination Analyzer H is Not Fooled by Pathological Input D* https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be non- halting.
We can know that D correctly simulated by H must have different behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a "pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function
to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
*Termination Analyzer H is Not Fooled by Pathological Input D* https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be non- halting.
We can know that D correctly simulated by H must have different behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a "pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function
to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be non-
halting.
We can know that D correctly simulated by H must have different behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship
between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function
to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly
terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in
main() then the actual D that H is actually simulating will crash from
stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and
return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be non-
halting.
We can know that D correctly simulated by H must have different behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship
between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function
to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly
terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in
main() then the actual D that H is actually simulating will crash from
stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and
return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
On 8/27/2023 10:00 AM, olcott wrote:
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be non- >>> halting.
We can know that D correctly simulated by H must have different behavior >>> than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship
between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function
to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly
terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in
main() then the actual D that H is actually simulating will crash from
stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and
return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
(5) Of the infinite set of every possible H where D is correctly
simulated by H there are only a THREE categories of possible
behaviors for H: (1)(a), (1)(b) and (2)
(1) Abort its simulation of D after a finite number of steps:
(a) Return 0 indicating that D correctly simulated by H cannot
possibly terminate normally.
(b) Return 1 indicating that D correctly simulated by H will
terminate normally.
(2) Never abort its simulation of D.
Anyone having a sufficient knowledge of C can correctly determine which
of these options are incorrect on the basis of the source-code of D.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
On 8/27/2023 12:13 PM, olcott wrote:
On 8/27/2023 10:00 AM, olcott wrote:
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H. >>>> When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be
non-
halting.
We can know that D correctly simulated by H must have different
behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship >>>> between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what >>>> H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function >>>> to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06. >>>>
H correctly determines that D correctly simulated by H cannot possibly >>>> terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in
main() then the actual D that H is actually simulating will crash from
stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and
return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
(5) Of the infinite set of every possible H where D is correctly
simulated by H there are only a THREE categories of possible
behaviors for H: (1)(a), (1)(b) and (2)
(1) Abort its simulation of D after a finite number of steps:
(a) Return 0 indicating that D correctly simulated by H cannot
possibly terminate normally.
(b) Return 1 indicating that D correctly simulated by H will
terminate normally.
(2) Never abort its simulation of D.
Anyone having a sufficient knowledge of C can correctly determine which
of these options are incorrect on the basis of the source-code of D.
When a termination analyzer is required to provide the halt status or an input that deliberately contradicts whatever Boolean value that this termination analyzer returns the halting problem merely mirrors the Liar Paradox.
The Liar Paradox cannot be correctly resolved to a value of True or
False only because it is semantically unsound because it is self- contradictory.
Thus the inability of a termination analyzer to provide a correct
Boolean return value is analogous to a CAD system's inability to
correctly draw a square circle. Thus this interpretation of the halting problem is merely an artificial contrivance with no actual merit.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
On 8/27/2023 10:00 AM, olcott wrote:
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be non- >>> halting.
We can know that D correctly simulated by H must have different behavior >>> than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship
between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function
to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06.
H correctly determines that D correctly simulated by H cannot possibly
terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in
main() then the actual D that H is actually simulating will crash from
stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and
return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
(5) Of the infinite set of every possible H where D is correctly
simulated by H there are only a THREE categories of possible
behaviors for H: (1)(a), (1)(b) and (2)
(1) Abort its simulation of D after a finite number of steps:
(a) Return 0 indicating that D correctly simulated by H cannot
possibly terminate normally.
(b) Return 1 indicating that D correctly simulated by H will
terminate normally.
(2) Never abort its simulation of D.
Anyone having a sufficient knowledge of C can correctly determine which
of these options are incorrect on the basis of the source-code of D.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
On 8/27/2023 12:13 PM, olcott wrote:
On 8/27/2023 10:00 AM, olcott wrote:
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem
proof's pathological relationship to simulating termination analyzer H. >>>> When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be
non-
halting.
We can know that D correctly simulated by H must have different
behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship >>>> between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what >>>> H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function >>>> to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06. >>>>
H correctly determines that D correctly simulated by H cannot possibly >>>> terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in
main() then the actual D that H is actually simulating will crash from
stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and
return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
(5) Of the infinite set of every possible H where D is correctly
simulated by H there are only a THREE categories of possible
behaviors for H: (1)(a), (1)(b) and (2)
(1) Abort its simulation of D after a finite number of steps:
(a) Return 0 indicating that D correctly simulated by H cannot
possibly terminate normally.
(b) Return 1 indicating that D correctly simulated by H will
terminate normally.
(2) Never abort its simulation of D.
Anyone having a sufficient knowledge of C can correctly determine which
of these options are incorrect on the basis of the source-code of D.
When a termination analyzer is required to provide the halt status or an input that deliberately contradicts whatever Boolean value that this termination analyzer returns the halting problem merely mirrors the Liar Paradox.
The Liar Paradox cannot be correctly resolved to a value of True or
False only because it is semantically unsound because it is self- contradictory.
Thus the inability of a termination analyzer to provide a correct
Boolean return value is analogous to a CAD system's inability to
correctly draw a square circle. Thus this interpretation of the halting problem is merely an artificial contrivance with no actual merit.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
On 8/27/2023 2:31 PM, olcott wrote:
On 8/27/2023 12:13 PM, olcott wrote:
On 8/27/2023 10:00 AM, olcott wrote:
On 8/25/2023 1:48 PM, olcott wrote:
A pair of C functions are defined such that D has the halting problem >>>>> proof's pathological relationship to simulating termination
analyzer H.
When it is understood that D correctly simulated by H (a) Is the
behavior that H must report on and (b) Cannot possibly terminate
normally then it is understood that D is correctly determined to be
non-
halting.
We can know that D correctly simulated by H must have different
behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown below) exactly how the pathological relationship >>>>> between D and H changes the behavior of D relative to H.
For any program H that might determine whether programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what
H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
"A decision problem is a yes-or-no question on an infinite set of
inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
Can D correctly simulated by H terminate normally?
The x86utm operating system: https://github.com/plolcott/x86utm
is based on an open source x86 emulator. x86utm enables one C function >>>>> to execute another C function in debug step mode.
// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input >>>>> 03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }
*Execution Trace*
Line 14: main() invokes H(D,D);
*keeps repeating* (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D) >>>>>
*Simulation invariant*
D correctly simulated by H cannot possibly reach past its own line 06. >>>>>
H correctly determines that D correctly simulated by H cannot possibly >>>>> terminate normally on the basis that H recognizes a dynamic behavior >>>>> pattern equivalent to infinite recursion. H returns 0 this basis.
*ADDENDUM*
(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.
*THIS IS THE PART THAT EVERYONE LIES ABOUT*
(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.
(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.
(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition >>>>> This means that the behavior of non-inputs is not allowed to be
considered.
If H ignores reality (not a good idea) and [as most of my reviewers
believe] makes pretend that it is simulating D(D) directly executed in >>>> main() then the actual D that H is actually simulating will crash from >>>> stack overflow because H will never stop simulating D.
This conclusively proves that D is correct to abort its simulation and >>>> return 0 indicating that D correctly simulated by H cannot possibly
terminate normally.
(5) Of the infinite set of every possible H where D is correctly
simulated by H there are only a THREE categories of possible
behaviors for H: (1)(a), (1)(b) and (2)
(1) Abort its simulation of D after a finite number of steps:
(a) Return 0 indicating that D correctly simulated by H cannot
possibly terminate normally.
(b) Return 1 indicating that D correctly simulated by H will
terminate normally.
(2) Never abort its simulation of D.
Anyone having a sufficient knowledge of C can correctly determine which
of these options are incorrect on the basis of the source-code of D.
When a termination analyzer is required to provide the halt status or an
input that deliberately contradicts whatever Boolean value that this
termination analyzer returns the halting problem merely mirrors the Liar
Paradox.
The Liar Paradox cannot be correctly resolved to a value of True or
False only because it is semantically unsound because it is self-
contradictory.
Thus the inability of a termination analyzer to provide a correct
Boolean return value is analogous to a CAD system's inability to
correctly draw a square circle. Thus this interpretation of the halting
problem is merely an artificial contrivance with no actual merit.
This is "undecidable" in the same way that finding an
N such that N > 5 and N < 2 is "undecidable".
When a termination analyzer must return a Boolean value that provides
the halt status of and D does the opposite of whatever Boolean value
that H returns the halting problem is a mere ruse and not any legitimate decision problem at all.
This only happens when we expect H to determine the halt status of a non-input.
int sum(int x, int y)
{
return x + y;
}
When for forbid H to report on not inputs this is the same as
forbidding sum(3,4) to report on the sum of 5 + 7.
When for forbid H to report on not inputs then the halting problem counter-example is decidable by a simulating termination analyzer.
*Termination Analyzer H is Not Fooled by Pathological Input D*
https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 366 |
Nodes: | 16 (2 / 14) |
Uptime: | 16:02:25 |
Calls: | 7,812 |
Files: | 12,927 |
Messages: | 5,766,129 |