S^A machine

S^A machine is designed by PSTF, which is a subset of a Minsky machine with 2 registers.

Definition

A S^A machine consists of 2 registers called A and B and the following 9 operations.

1. Increase the value of A by 1
2. Decrease the value of A by 1 if A>0 else do nothing
3. Swap the values of A and B
4. Apply all operations on A to B instead
5. Apply all operations on B back to A
6. If A is 0, jump to line x, where x is a constant
7. Transfer the value of A to the screen
8. Transfer the input value to A
9. Jump to line x, where x is a constant

As the definition shown, any S^A machine can be represented by these operations:

1 +
2 -
3 %
4 >
5 <
6 ?x
7 .
8 ,
9 !x

Computational Class

This model is Turing complete (specifically, it is equivalent to a 2‑counter Minsky machine, which has the same expressive power as a Turing machine).

Proof

• There are two main registers, A and B.
• Initially, all operations are done on A, and the two main operations are 'add' and 'subtract', both of which are basic operations supported by a Minsky machine.
• Operations on B can be done using the 'Convert' command. After running this command, all operations that were originally on A (add, subtract, in, and out) will switch to affect B.
• You might have noticed that there’s no mention of a 'zero check' in what was mentioned above, but that can also be done — just swap the values of A and B, and then A's value will be B's original value, so you can check through A whether B was originally 0.
• The input and output can be neglected.
• Q.E.D. The S^A machine is basically a two-register Minsky machine.
• Since a 2‑counter Minsky machine is known to be Turing complete (it can simulate a Turing machine, given unbounded counters), and all its instructions are directly implementable in this model, the model is Turing complete.

Note: This assumes the registers hold unbounded non‑negative integers, which is the standard assumption for counter machines.

Equivalent of Minsky Machine

Minsky   S^A
INC  A   +
DEC  A   -
JZ A,x   ?x
INC  B   >+<
DEC  B   >-<
JZ B,x   >?x<
JMP  x   !x

See Also

• Minsky machine