Meta Minsky Machine

Meta Minsky Machine (MMM) is a hyperarithmetic language which allows for it to ask about its own halting. Specifically, it allows for paradoxical programs if their simulation structure is not well-founded.

Specification

There are three registers: A, B, and C. The machine also has a state, so really we can think of this like a HLSM. The command format is as followed:

(number indicating current state) (action) (register and new states)

Specifically, here are the actions, letting W/X/Y/Z be state numbers and K being one of the three registers.

W inc K X // If at state W, increment register K and transition to state X
W dec K X // If at state W, decrement register K and transition to state X. If K is already zero, halt and output register C.
W test K X Y // If at state W, then check register K. If K=0, go to state X, otherwise go to state Y
W oracle X Y Z // Create a simulation to go to state X. Run the simulation. If it halts, we go to state Y, otherwise we go to state Z.

The initial values are A=B=0 and C=input, with starting at State=1. The output if the machine halts comes from register C.

Paradoxical Programs

Consider the "simulation tree" of this Meta Minsky Machine. We can imagine a node being a child of a parent if that node is spawned as a simulation from the parent. Some programs have simulation trees where some nodes have infinitely many children or infinitely many programs spawned as simulations: that is completely okay. However, some programs have trees infinite in height i.e. not well-founded. In this case, we can get paradoxical programs that halt if and only if they do not halt.

In that scenario, if we run the program destroy the universe.

Computational Class

Obviously Minsky Machines are Turing complete, and moreover we can build a universal Minsky Machine within a Minsky machine. Same with the Meta Minsky Machine but we have an oracle testing halting of any Meta Minsky Machine program or state.

Thus, the computational class has to be hyperarithmetic. This language is very similar to Oracle.