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
== External resources ==
* An interpreter in JavaScript
Category:Languages Category:Turing complete Category:Cell-based Category:Implemented Category:2023