Rrr
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Ttulka |
| Appeared in | 2023 |
| Memory system | Cell-based |
| Dimensions | one-dimensional |
| Computational class | Turing complete |
| Major implementations | Interpreter in JavaScript |
| Influenced by | Turing machine |
| Influenced | None |
| File extension(s) | .rrr |
Rrr is a simple Turing-complete language for programming Turing machines equipped with an unbounded tape using only a binary alphabet consisting of symbols R and r. Other symbols are ignored.
A program in Rrr is a list of transitions of a Turing machine encoded as quintuplets of unary numbers with the value r symbols and the separator R symbols. Each quintuplet includes a starting state, a conditional read symbol, a write symbol, a move action, and a next state.
How it works
A universal Turing machine reads a description of a Turing machine encoded as a program in Rrr and simulates it.
In each state qi with the current symbol s on the tape, the universal machine searches for a quintuple with the starting state qi and the read symbol s. If found, the symbol on the tape is replaced by the write symbol from the quintuple, the reading head moves left or right according to the move action in the quintuple, and the current state is updated to the next state qi+1 from the quintuple.
In that sense, the quintuples do not only serve as a description of a Turing machine, but also as instructions for a universal Turing machine.
The tape alphabet must be provided to the interpreter as a parameter.
Quintuplets
Elements of a quintuplet are encoded as follows:
| Order | Meaning | Values |
|---|---|---|
| 1. | Starting state | r × N, N > 0
|
| 2. | Read symbol | r × T, T > 0
|
| 3. | Write symbol | r × T, T > 0
|
| 4. | Move action | r for left, rr for right
|
| 5. | Next state | r × N, N > 0
|
Where N is a count of the internal states of the Turing machine, and T is the size of the tape alphabet. For instance, states of a Turing machine with two internal states q0 and q1 are encoded as r and rr respectively; the tape symbols 0 and 1 of the binary tape alphabet {0, 1} are encoded as r and rr respectively.
Elements are in a quintuple separated by R; quintuples in a program are also separated by R. For example, the following Rrr code consists of two quintuplets representing the transitions (q0, ε, 0, >, q1) and (q1, ε, 1, >, q2) of a three-state Turing machine with a tape alphabet { ε, 0, 1}.
rRrRrrRrrRrr R rrRrRrrrRrrRrrr
or simply as
rRrRrrRrrRrrRrrRrRrrrRrrRrrr
Examples
(The line wrapping used in the following code is completely arbitrary.)
1-state busy beaver
It prints "X" on the output.
The tape alphabet is { ε, X}.
rRrRrrRrrRrr
Because all symbols except R and r are ignored, the following program is equivalent:
One-state busy beaver ===================== 1. Read a symbol under the head. 2. Reading a zero, write a one. 3. Right away move to the right. 4. Transit to the next state. 5. Ready. The program terminates.
2-state busy beaver
It prints "XXXX" on the output.
The tape alphabet is { ε, X}.
rRrRrrRrrRrrRrRrrRrrRrRrrRrrRrRr rRrRrRrrRrrRrrRrrRrrr
Copier
The copier program effectively duplicates the given input, appending it to the end of the existing tape. This doubling process repeats the input string. For example, if the input is "x" the output will be "xx". If the input is "xxx", the output will be "xxxxxx", and so on.
The program uses the symbol ! as an operational marker.
The input alphabet is {x}. The tape alphabet is { ε, !, x}.
rRrrrRrrRrrRrrRrrRrrrRrrrRrrRrrR rrRrRrRrrRrrrRrrrRrrrRrrrRrrRrrr RrrrRrRrrrRrRrrrrRrrrrRrrrRrrrRr RrrrrRrrrrRrRrRrRrrrrrRrrrrrRrrr RrrrRrRrrrrrRrrrrrRrrRrrrRrrRrRr RrRrrrRrrRrrrrrrRrrrrrrRrrrRrrrR rrRrrrrrrRrrrrrrRrRrRrRrrrrrrrRr rrrrrrRrrrRrRrRrrrrrrrr
Palindromes
A palindrome is a sequence of symbols that reads the same backward as forward, such as "B", "ABA", or "BBABB".
The following program accepts the input string as a palindrome by printing an A, or rejects it by printing a B on the tape.
The tape alphabet is { ε, A, B}.
rRrrrRrRrrRrrRrrRrrRrrRrrRrrRrrR rrrRrrrRrrRrrRrrRrRrRrRrrrRrrrRr RrRrRrRrrrRrrrRrRrRrrrrRrrrrRrrR rrRrRrrrrRrrrrRrrrRrrrRrRrrrrRrr rrRrRrRrrRrRrRrrRrRrrRrrrrrRrrrr rRrrRrrRrrRrrrrrRrrrrrRrrrRrrrRr rRrrrrrRrrrrrRrRrRrRrrrrrrRrrrrr rRrRrRrRrRrrrrrrRrrRrRrRrrrrRrRr RrrrRrrRrrrrrrrrRrrrRrrRrRrRrrrr rrrRrrrrrrRrrrRrRrRrrrrrrrRrrrrr rrRrrRrRrRrrrrrrrRrrrrrrrRrrrRrR rRrrrrrrrRrrrrrrrRrRrrRrrRrrrrrr rr
Hello World
It simply prints "Hello World".
The tape alphabet is { ε, H, e, l, o, W, r, d }.
rRrRrrRrrRrrRrrRrRrrrRrrRrrrRrrr RrRrrrrRrrRrrrrRrrrrRrRrrrrRrrRr rrrrRrrrrrRrRrrrrrRrrRrrrrrrRrrr rrrRrRrRrrRrrrrrrrRrrrrrrrRrRrrr rrrRrrRrrrrrrrrRrrrrrrrrRrRrrrrr RrrRrrrrrrrrrRrrrrrrrrrRrRrrrrrr rRrrRrrrrrrrrrrRrrrrrrrrrrRrRrrr rRrrRrrrrrrrrrrrRrrrrrrrrrrrRrRr rrrrrrrRrrRrrrrrrrrrrrr