<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**](https://medium.com/coinmonks/ethereum-what-is-gas-and-why-do-we-need-it-88bcd7fc191d)
>
> 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>


---

