Can D simulated by H terminate normally?

Joined
Jun 12, 2023
Messages
3
Reaction score
0
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.

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   D(D);
15 }

Execution Trace
Line 14: main() invokes 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.

Is it dead obvious to everyone here when examining the execution
trace of lines 14 and 06 above that D correctly simulated by H cannot
possibly terminate normally by reaching its own line 09?
 
Last edited:
Joined
Sep 21, 2022
Messages
122
Reaction score
15
"It is not a new idea." Where have you seem this before?
I was refering to the halting idea. Which pops up in almost every book with the word Turing in it.
Complicating things by talking about simulation and virtual registers, that I have not seen before.
 
Joined
Jun 12, 2023
Messages
3
Reaction score
0
I was refering to the halting idea. Which pops up in almost every book with the word Turing in it.
Complicating things by talking about simulation and virtual registers, that I have not seen before.
The key new aspect of the idea is that termination analyzer H
I was refering to the halting idea. Which pops up in almost every book with the word Turing in it.
Complicating things by talking about simulation and virtual registers, that I have not seen before.
The key new aspect of the idea seems to be that termination analyzer H can correctly determine that an input defined with a pathological relationship to H must be aborted to prevent the infinite execution of H. This could be used to prevent denial of service (DOS) attacks.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,057
Latest member
KetoBeezACVGummies

Latest Threads

Top