Turmin
 |
|
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Ttulka |
| Appeared in | 2024 |
| Dimensions | one-dimensional |
| Computational class | Turing complete |
| Major implementations | Interpreter in JavaScript |
| File extension(s) | .tm |
Turmin is neither a Turing machine nor a Minsky machine. It is a language for programming Turing machines with a minimalistic yet convenient instruction set. The explicit state machine used traditionally in description numbers of Turing machines is conveniently replaced by conditional jumps borrowed from Minsky machines.
Memory model
Like Turing machines, a Turmin program operates on an unbounded tape of cells, each holding a symbol from the program alphabet. The used charset depends on the implementation, but each interpreter must support at least ASCII starting from #20 (SPACE).
The character #20 is also the initial value of each cell, so an empty cell has the value #20. This is just a convenient shortcut, avoiding the introduction of any special characters (such as ε) or additional instructions like clear and jump if empty. An implementation can simply interpret an empty cell, either undefined or having an empty value, as a space.
Instructions
| Instruction | Name | Meaning |
|---|---|---|
sS |
SET | Set symbol S to the current cell |
r |
RIGHT | Move to the cell on the right |
l |
LEFT | Move to the cell left |
jSN |
JUMP | If the current cell is S, jump to the N-th instruction |
Instructions in a Turmin program are indexed from zero. Jumping to a nonexistent index will cause the program to halt.
Whitespaces between instructions are permitted.
Extensions
In addition to the base four instructions, a Turmin interpreter may also implement the following extensions:
Debug
The directive d (DEBUG) will output useful debugging information.
DEBUG should not be counted as an ordinary instruction, allowing it to be added to or removed from the source code without affecting the computation.
Labels
A label is a directive that begins with a colon followed by zero :0 and an arbitrary number. For instance, :01 and :099999 are valid labels.
Labels without the colon can be used in JUMP instructions as the parameter N. For instance, jx01 and jx099999.
Comments
A code comment starts with / and ends with \ or a newline.
Code comments can contain any arbitrary text; they are fully ignored by interpretation.
Examples
Infinite loop
The simplest infinite loop can be created by repeatedly jumping to the same instruction:
j 0
Addition
Turmin does not natively support numbers, so a concept must be developed. The simplest approach is to use unary numbers, represented by tally marks (| or any arbitrary symbol) separated by spaces, where the number of tally marks corresponds to the value.
For example, the following tape content represents the numbers 2 and 3:
|| |||
Adding unary numbers is straightforward—both expressions simply need to be concatenated:
j 3 r j|0 / move to the next number s| / replace a space with a tally mark r j|4 / to the end of the second number l s / erase the last tally mark
The result for the input 2 and 3 is as follows (5):
|||||
Palindromes
Turmin is a symbolic machine, making it well-suited for string manipulation.
To check if an input string of xs and ys is a palindrome, the first character is “eaten” and compared to the last one. If a discrepancy is found, the tape is erased. If all characters are eaten without finding a difference, the program prints 1:
j 27 l jx1 jy1 / to beginning r jx7 jy17 / check the rightmost symbol / check x s r jx8jy8 //8 l jy29 s l jx0jy0 //11 / check y s r jx18jy18 //18 l jx29 s l jx0jy0 //21 / accept (print 1) s1 j130 //27 / erase tape s l jx29jy29 //29
Comments //n label the instruction index, aiding in navigating jumps.
Fibonacci sequence
The idea is to use unary numbers and move them as the sequence prescribes, adding them accordingly.
The initial input consists of three arguments: the two starting elements of the sequence and the number of desired iterations.
For example, 3 iterations can be performed starting with 1 and 2:
| || |||
First, the program decrements the iteration counter. If the counter reaches zero, the program halts:
| || ||
Next, the second number is moved as the new first element by marking it digit by digit:
| | |+ || || | ++ ||
The marks are then removed, and the two numbers are added together:
|| | +| || || | || || || ||| ||
Then, the next iteration begins.
/ decrement iteration rj|0 //0 rj|2 //2 r j 999 l / halt if no iterations left rj|7 //7 l s //9 / back to the left tape begin lj|11 //11 lj|13 //13 lj|15 //15 r / to the second number / mark last digit rj|18 //18 rj|20 //20 ls+ //22 / back to the left tape begin / add a new digit to the begin lj|24 //24 lj|26 //26 lj 32 //28 lj|30 //30 s| //32 / to the third number rj|33 //33 rj|35 //35 r j+43 l / all digits marked rj|40 //40 j+22 / repeat / remove marks s|rj+43 //43 / add the 2nd and 3rd numbers sx l s lj|49 //49 s| / shift the iterations number rj|52 //52 rs| rj|56 //56 ls / to the left tape begin lj|60 //60 lj|62 //62 lj|64 //64 / new iteration r j|0
Or, in a more compact form:
rj|0rj|2rj 999lrj|7ls lj|11lj|13lj|15rrj|18rj|20ls+lj|24lj|26lj 32lj|30s|rj|33 rj|35rj+43lrj|40j+22s|rj+43sxls lj|49s|rj|52rs|rj|56ls lj|60lj|62lj|64rj|0
Hello, World!
This legendary program is straightforward to implement in Turmin:
sHrserslrslrsors,rs rsWrsorsrrslrsdrs!
Computational class
It should be evident that Turmin is a Turing-complete language, as it has read-write access to unbounded memory and supports conditional jumps. We can easily demonstrate that Turmin can show both Turing and Minsky machines.
Turing machine
A Turing machine performs computations based on state transitions. In Turmin, states can be simulated as snippets of code that the program jumps to based on a transition.
Consider the following Turing machine with two states, S1 and S2, which rewrites As to Xs until it encounters a B:
┌─A/X/R──(S1)──B/B/L──>(S2) └─────────^
Translating this Turing machine into Turmin is a mechanical process:
/ S1 jB3 sX r jA0 / S2 l
Minsky machine
We can simulate the registers of a Minsky machine using unary numbers separated by spaces or any other symbol.
Incrementing a register involves adding a tally mark and shifting to the right, while decrementing involves removing a tally mark and shifting to the left.
Conditional jumps are natively supported in Turmin, and checking for zero is as simple as verifying whether any tally mark exists between separators.
Cyclic tag system
It is almost trivial to translate any cyclic tag system into Turmin. For example, the cyclic tag system with the productions (011, 10, 101) corresponds to the following Turmin program:
/ 011 j 51 / halt on empty j014 / next production rj02j12 / move rightmost s0rs1rs1 / append 011 lj010j110r / move leftmost s r d / delete + debug / 10 j 51 / halt on empty j029 / next production rj019j119 / move rightmost s1rs0 / append 10 lj025j125r / move leftmost s r d / delete + debug / 101 j 51 / halt on empty j046 / next production rj034j134 / move rightmost s1rs0rs1 / append 101 lj042j142r / move leftmost s r d / delete + debug j00j10 / repeat
Or, in a more compact form:
j 51j014rj02j12s0rs1rs1lj010j110rs rdj 51j029rj019j119s1rs0lj025j125rs rdj 51 j046rj034j134s1rs0rs1lj042j142rs rdj00j10