Unconventional termination analyzer H correctly reports
the halt status of the halting problem's counter-example
input.
00 int H(ptr x, ptr x) // ptr is pointer to int function
01 int D(ptr x)
02 {
03 int Halt_Status = H(x, x);
04 if (Halt_Status)
05 HERE: goto HERE;
06 return Halt_Status;
07 }
08
09 int main()
10 {
11 H(D,D);
12 }
*A simulator is the conventional meaning of an x86 emulator or a UTM* Unconventional termination analyzer is exactly the conventional term-of-the-art {termination analyzer} except that it need not halt.
*D simulated by H where H can*
(a) Watch all of the state changes of its input.
(b) Analyze these state changes.
(c) Correctly determine that its input (and itself) would never halt.
(d) Continue to report that its input would never halt by
transitioning to a special non-final state indicating this.
*All the while remaining a pure simulator with extra features*
This H is neither a halt decider nor a conventional {termination
analyzer}. It is an unconventional {termination analyzer} that
correctly reports the halt status of its pathological input.
This exact same reasoning applies to the Peter Linz halting problem
proof where embedded_H is an unconventional {termination analyzer}.
When Peter Linz Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
*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: | 307 |
Nodes: | 16 (2 / 14) |
Uptime: | 36:19:07 |
Calls: | 6,910 |
Calls today: | 4 |
Files: | 12,376 |
Messages: | 5,428,695 |
Posted today: | 2 |