D/Q

D/Q is an extension to DQ, which is turing complete, and has less stacks than TDQ. It uses only two stacks. It was made to fix the problem of ℕDQ, while not increasing the stack count. Alike ℕDQ the commands run as ordered in the program.

Memory

D/Q has two stack, and a pointer that points to one of them. The symbols 1 and 2 can be on these stacks.

Commands

D/Q uses the following commands:

Command	Meaning
$	Go to the stack no currently pointed to.
!	If this command has been ran an even number of times, push 2 else 1. Note that when looping, its only counted as one "run".
Q	Pop top of current stack and discard it.
D	Pop top of stack, copy it, and push one copy to each of the two stacks.
[p|q]n	run q and jump to right after n'th(1 indexed) . if the stack has length 1 or less. If q has already been ran, then the jump is "inevitable". Else run p until the top of the stack is not equal to the one when the conditional was performed, in which this structure is left. Note that "empty stack" counts as a symbol change. The check for symbol equality is only checked at the start of the loop body, not in the middle. If no n is provided, no jump is performed with the conditional.
.	do nothing.

Computational class

D/Q is turing complete, by translation from Short Minsky Machine Notation:

start program as: !!!Q
℘c2 -> .[DQ]$[[DQ]$Q|[DQ]$]c
℘c1 -> .[DQ][Q$[DQ]$|$[DQ]$]c
℘2 -> .!!Q
℘1 -> .!Q[DQ]!$![DQ]$Q!Q
℘x -> .$[|$]c

Compilation From DQ

The following works as a translation from (deterministic) DQ:

1 -> !!Q
Q -> Q
D -> D$DQ$