<p><strong>Termination Analyzer H is Not Fooled by Pathological Input D</strong></p>
<p>When the halting problem is construed as requiring a correct yes/no answer to a contradictory question it cannot be solved.</p>
<p>Any input D defined to do the opposite of whatever Boolean value that its termination analyzer H returns is a contradictory input relative to H.</p>
<p>When H returns 1 for inputs that it determines do halt and returns 0 for inputs that either do not halt or do the opposite of whatever Boolean value that H returns then these pathological inputs are no longer contradictory and become decidable.</p>
<p><strong>Can D correctly simulated by H terminate normally?</strong><br>
The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H simulates D it creates a separate process context for D with its own memory, stack and virtual registers. H is able to simulate D simulating itself, thus the only limit to recursive simulations is RAM.</p>
<pre><code>// 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 }
</code></pre>
<p><strong>Execution Trace</strong><br>
Line 14: main() invokes H(D,D);</p>
<p><strong>keeps repeating (unless aborted)</strong><br>
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)</p>
<p><strong>Simulation invariant:</strong><br>
D correctly simulated by H cannot possibly reach its own line 09.</p>
<p>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.</p>
<p><strong>H outputs:<br> &quot;H: Infinitely Recursive Simulation Detected Simulation Stopped&quot;</strong> indicating that D has defined a pathological relationship to H.</p>
<p><strong>The x86utm operating system</strong> (includes several termination analyzers) <a href="https://github.com/plolcott/x86utm" rel="nofollow noreferrer">https://github.com/plolcott/x86utm</a></p>
<p><strong>It compiles with the 2017 version of the Community Edition</strong> <a href="https://visualstudio.microsoft.com/thank-you-downloading-visual-studio/?sku=Community&amp;rel=15" rel="nofollow noreferrer">https://visualstudio.microsoft.com/thank-you-downloading-visual-studio/?sku=Community&amp;rel=15</a></p>

CC BY-SA 4.0
2023-06-22T20:04:46.920Z
2023-06-22T21:20:13.793Z
2023-06-22T21:20:13.793Z
polcott
<p>2024-08-04 update<br>
When we define an input that does the opposite of whatever value that its halt decider reports there is a way for the halting decidability decider to report correctly.</p>
<pre><code>int DD() 
{
  int Halt_Status = HHH(DD); 
  if (Halt_Status) 
    HERE: goto HERE; 
  return Halt_Status; 
} 

int main()
{
  HHH(DD); 
}
</code></pre>
<p><strong>Do you understand that this is correct?</strong></p>
<p>HHH returns false indicating that it cannot correctly determine that its input halts. True would mean that its input halts. In this case HHH is a correct halting decidability decider.</p>
<p>====================
Redefining the notion of a halt decider: (a) Returns true when it correctly determines that its input halts (b) false for everything else including:</p>
<p>(1) Non-halting<br>
(2) Not a TM description<br>
(3) Epistemological antinomy<br>
The counter-example input that was intentionally defined to do the opposite of whatever Boolean value that its corresponding halt decider returns.</p>
<p><strong>Then a correct and consistent halt decider can be defined.</strong></p>
<p>Do you understand that this is correct?</p>
<p><strong>The Tarski Undefinability Theorem is refuted this same way:</strong><br>
LP = &quot;This sentence is not true.&quot;<br>
Boolean True(English, LP) is false meaning not true.<br>
Boolean True(English, ~LP) is false meaning not true.<br></p>
<h1>Question prior to update</h1>
<p>Can you see that termination analyzer H does correctly thwart denial of service attacks from inputs that match the halting problem's pathological input template?</p>
<p>When termination analyzer H is intended to prevent denial of service (DOS) attacks is presented with an input D that has been defined to have a pathological relationship to this termination analyzer, it correctly aborts the simulation of this input that would have otherwise caused H to never terminate until system resources have been exhausted, crashing the system.</p>
<blockquote>
<p><a href="https://medium.com/coinmonks/ethereum-what-is-gas-and-why-do-we-need-it-88bcd7fc191d" rel="nofollow noreferrer"><strong>How pathological inputs are currently
handled</strong></a></p>
<p>If a set of instructions ( in the smart contract) is executed on the
Ethereum Virtual Machine, it cannot predict how long these will run
for, at the beginning. If a set of instructions run forever, they can
freeze this blockchain and use up all the resources. This is similar to
a DoS (Denial of Service) attack. Each computation on the Ethereum
Virtual Machine requires some predetermined amount of gas (which one
has to buy with real money).</p>
</blockquote>
<p><strong>Can D correctly simulated by H terminate normally?</strong></p>
<p>The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H simulates D it creates a separate process context for D with its own memory, stack and virtual registers. H is able to simulate D simulating itself, thus the only limit to recursive simulations is RAM.</p>
<pre><code>// 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 }
</code></pre>
<p><strong>Execution Trace</strong><br>
Line 14: main() invokes H(D,D);</p>
<p><strong>keeps repeating</strong> (unless aborted)<br>
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)</p>
<p><strong>Simulation invariant:</strong><br>
D correctly simulated by H cannot possibly reach its own line 09.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-15T17:13:02.510Z
A termination analyzer is an ordinary computer program that is supposed to determine whether or not its input program will ever stop running or gets stuck in infinite execution. When a program input has been specifically defined to confuse a termination analyzer it is correct to determine that the program behavior is malevolent. Prior to my work nothing could be done about inputs having a pathological relationship to their termination analyzer. Prior to my work Rice's theorem prevented this pathological relationship from being recognized. The pathological relationship is when an input program
polcott
<program-analysis><correctness>
Defining a correct halting decidability decider
polcott
# Defining a correct halting decidability decider

(Asked by: username_0 on 2023-06-13)

2024-08-04 update
When we define an input that does the opposite of whatever value that its halt decider reports there is a way for the halting decidability decider to report correctly.
int DD() 
{
  int Halt_Status = HHH(DD); 
  if (Halt_Status) 
    HERE: goto HERE; 
  return Halt_Status; 
} 

int main()
{
  HHH(DD); 
}

Do you understand that this is correct?
HHH returns false indicating that it cannot correctly determine that its input halts. True would mean that its input halts. In this case HHH is a correct halting decidability decider.
====================
Redefining the notion of a halt decider: (a) Returns true when it correctly determines that its input halts (b) false for everything else including:
(1) Non-halting
(2) Not a TM description
(3) Epistemological antinomy
The counter-example input that was intentionally defined to do the opposite of whatever Boolean value that its corresponding halt decider returns.
Then a correct and consistent halt decider can be defined.
Do you understand that this is correct?
The Tarski Undefinability Theorem is refuted this same way:
LP = "This sentence is not true."
Boolean True(English, LP) is false meaning not true.
Boolean True(English, ~LP) is false meaning not true.
Question prior to update
Can you see that termination analyzer H does correctly thwart denial of service attacks from inputs that match the halting problem's pathological input template?
When termination analyzer H is intended to prevent denial of service (DOS) attacks is presented with an input D that has been defined to have a pathological relationship to this termination analyzer, it correctly aborts the simulation of this input that would have otherwise caused H to never terminate until system resources have been exhausted, crashing the system.

How pathological inputs are currently
handled
If a set of instructions ( in the smart contract) is executed on the
Ethereum Virtual Machine, it cannot predict how long these will run
for, at the beginning. If a set of instructions run forever, they can
freeze this blockchain and use up all the resources. This is similar to
a DoS (Denial of Service) attack. Each computation on the Ethereum
Virtual Machine requires some predetermined amount of gas (which one
has to buy with real money).

Can D correctly simulated by H terminate normally?
The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H simulates D it creates a separate process context for D with its own memory, stack and virtual registers. H is able to simulate D simulating itself, thus the only limit to recursive simulations is RAM.
// 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 its own line 09.
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.

**Tags:** program-analysis, correctness

> **Comments:**
> **username_0**: A termination analyzer is an ordinary computer program that is supposed to determine whether or not its input program will ever stop running or gets stuck in infinite execution. When a program input has been specifically defined to confuse a termination analyzer it is correct to determine that the program behavior is malevolent. Prior to my work nothing could be done about inputs having a pathological relationship to their termination analyzer. Prior to my work Rice's theorem prevented this pathological relationship from being recognized. The pathological relationship is when an input program  

---

## 1 answers

### Answer by username_0 on 2023-06-22. Score: 0 | Accepted answer

Termination Analyzer H is Not Fooled by Pathological Input D
When the halting problem is construed as requiring a correct yes/no answer to a contradictory question it cannot be solved.
Any input D defined to do the opposite of whatever Boolean value that its termination analyzer H returns is a contradictory input relative to H.
When H returns 1 for inputs that it determines do halt and returns 0 for inputs that either do not halt or do the opposite of whatever Boolean value that H returns then these pathological inputs are no longer contradictory and become decidable.
Can D correctly simulated by H terminate normally?
The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H simulates D it creates a separate process context for D with its own memory, stack and virtual registers. H is able to simulate D simulating itself, thus the only limit to recursive simulations is RAM.
// 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 its own line 09.
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 outputs: "H: Infinitely Recursive Simulation Detected Simulation Stopped" indicating that D has defined a pathological relationship to H.
The x86utm operating system (includes several termination analyzers) https://github.com/plolcott/x86utm
It compiles with the 2017 version of the Community Edition https://visualstudio.microsoft.com/thank-you-downloading-visual-studio/?sku=Community&rel=15


---

