Q''

Introduction

Q'' is a very simple Turing-complete programming language based on just three instructions. It is similar to, but simpler than, the 4-instruction P'' and 8-instruction BF.

Architecture

There are two tapes, like in Wang's W-machine, namely the program tape and data tape. The program tape is cyclic, and the data tape is infinite and unbounded, similar to the tape for a Turing machine. Both tapes are divided into locations, which each store a symbol. In the program tape, there are 3 admissible symbols, namely 'Q', '(' and ')'. These correspond to the three instructions. On the data tape, there are only two symbols, '0' and '1'.

The program tape is only read in one direction; this contrasts with other programming languages, where jumps can cause the reading head to backtrack. The reading head proceeds along in an orderly fashion, reading the instructions sequentially.

Instruction set

The 3 instructions are the symbols 'Q', '(' and ')'. 'Q' has the same purpose as the lambda in P''; the machine inverts the symbol on the data tape, then moves left one location. The left parenthesis, '(', moves the RW head right one location on the data tape, then (if the value on the tape is '1'), operation jumps to the corresponding ')'. Finally, the ')' symbol is just a marker, and has no further use.

Useful strings

Using these three symbols may seem restrictive at first. However, it is possible to assemble them into short, useful sequences, like so:

Proof of Turing-completeness

Using the above substrings, it is possible emulate a Universal Turing Machine. First, we select a suitable Universal Turing Machine with 2 symbols and m states. Then, the state can be represented by n bits, where n >= log(m)/log(2). We divide the data tape into modules of n + 3 bits, like so:

a b c d₁ d₂ ... d_n

The machine begins on 'a', with the state stored in 'd₁' ... 'd_n'. In each module, the equivalent symbol for the Turing tape is stored in 'c'. Using a nested binary tree of Q(B)Q(A) statements, 2⁽ⁿ⁺¹⁾-1 in total, the program executes a substring based on the values of 'c' and 'd', storing the next symbol in 'b', the direction to move in 'a' (0 = right, 1 = left), and the next state into the next module.

The program now copies the contents of 'b' into 'c'. Then, the program executes the following string:

Q()Q(()() ()() ()() ... ()()) Q()Q Q()Q Q()Q ... Q()Q

This moves the machine right n+3 cells if 'a' contains a '0', and left n+3 cells if 'a' contains a '1'. The program then repeats, performing one iteration of the Turing-machine rules per cycle.

Implementation

Due to its simplistic nature, it requires far fewer components to implement than a more complex programming language, such as Z80 machine code. The most difficult instruction to implement, '(', would require a register to count the number of parentheses, incrementing the register for each extra '(' encountered, and decrementing when a ')' is encountered. The routine exits when the register contains a zero and a ')' is encountered. The other operations are much simpler to implement, and could be performed in nanoseconds.

The cyclic unidirectional program tape is reminiscent of a loop of prokaryotic DNA. Since there are four base pairs, and only three instructions, an extra 'halt' instruction could be included. This system would be easy to implement using a biological nanocomputer, unlike a conventional von Neumann processor. The data tape is slightly more difficult, as it must be able to move bidirectionally. This could be accomplished by two Stepper motors in a mechanical implementation, or ATPase motors in a biochemical machine. As for the register, it could be replaced with another tape, with a marker on one location.