Rrr

From Esolang
Jump to navigation Jump to search
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
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

External resources