tur.1

.Dd 2026-07-11
.Dt TUR 1
.Os
.Sh NAME
.Nm tur
.Nd compose Turing machines
.Sh SYNOPSIS
.Nm tur
.Op Fl c
.Op Fl iIO
.Oo
.Fl l Cm tur | Cm ir
.Oc
.Oo
.Fl b
.Ar path
.Oc
.Oo
.Fl x
.Ar suffix
.Oc
.Oo
.Fl m
.Ar machine1.tm
.Fl m
.Ar machine2.tm Ns \&...
.Oc
.Op Ar source.tur
.Op Ar machine.tm
.Nm tur
.Fl r
.Op Fl denskC
.Ar machine.tm
.Nm tur
.Fl cr
.Op Fl iOenskC
.Oo
.Fl l Cm tur | Fl l Cm ir
.Oc
.Oo
.Fl b
.Ar path
.Oc
.Oo
.Fl x
.Ar suffix
.Oc
.Oo
.Fl m
.Ar machine1.tm
.Fl m
.Ar machine2.tm Ns \&...
.Oc
.Ar source.tur
.Sh DESCRIPTION
.Nm
compiles a description of a Turing machine given in the
.Ar source
file (conventionaly named with a
.Sq tur
suffix)
into an actual Turing machine,
i.e. the tuples describing the machine\(cqs transfer function
and stores it in the
.Ar machine
output file (conventionaly named with a
.Sq tm
suffix).
.Pp
The source language is described below.
It is expressive enough to describe compositions
of complex machines from simpler machines.
The input and output is encoded on the tape with unary notation
.Pq sometimes called Tally Notation .
Number 0 is encoded as 1, number 1 as 11, number 2 as 111 etc.
Multiple numbers are separated with a single symbol 0.
The blank symbol is also 0.
An empty tape is valid, it can be interpreted as an empty list.
The machine should start at the beginning of the tape content
.Pq the first symbol 1 if the tape is not empty
and when it halts, the position should also be at the beginning; otherwise
the output is considered invalid.
Included machines must also use this convention.
.Sh OPTIONS
The
.Fl c
and
.Fl r
options determine what to do.
If neither on them is present,
.Fl c
is assumed.
.Bl -tag -width Ds
.It Fl c , Fl \-compile
Compile the machine from source.
The source is read from the
.Ar source
file or from the standard input if no source file is specified.
The resulting machine is saved in the
.Ar machine
output file or printed to the standard output if no output file is specified.
If used with
.Fl r ,
the machine is not printed nor saved, but run with tape content from
the standard input.
.It Fl r , Fl \-run
Run the resulting machine.
Exactly one argument is required: the
.Ar machine
file from which the machine transfer function is read
or (when used with the
.Fl c
option) the
.Ar source
file from which the machine is compiled first.
The initial content of the tape is read from the standard input;
the eventual content of the tape is printed to the standard output,
if and when the machine halts.
.El
.Pp
The following options can be used with the
.Fl c
option:
.Bl -tag -width Ds
.It Fl i , Fl \-instructions
Print the instructions (intermediate representation of the program)
to the standard error output.
.It Fl I , Fl \-only-instructions
Do not create the machine, only display the instructions.
These are printed into the output file or to the standard output
if no output file is specified.
.It Fl O , Fl \-optimize
Optimize the machine.
.It Fl l Cm tur | Cm ir , Fl \-input-language Cm tur | Cm ir
.Fl l Cm tur
(default) means that the input is in the primary source language of
.Nm tur ,
.Fl l Cm ir
means that the input is in the form of IR (intermediate representation).
.It Fl b Pa path , Fl \-include-base Pa path
Use this
.Pa path
as the base path for
.Ic include
statements in the source.
The default path is the directory where the
.Ar source
file is located.
.It Fl x Ar suffix , Fl \-include-suffix Ar suffix
Use this string as the suffix of included files.
The default is
.Em .tm .
The suffix does not have to be just an extension, the directory
separator can be used to mark that the machine file is inside a
directory with the name of the include.
.It Fl m Ar machine1.tm , Fl \-machine Ar machine1.tm
Use this machine for
.Ic require
statements in the program.
Machines provided with this option map in order with
.Ic require
statements.
.El
.Pp
The following options can be used with the
.Fl r
option:
.Bl -tag -width Ds
.It Fl s , Fl \-steps
Trace the machine steps: print the tape content and the current state
to the standard error output.
.It Fl k , Fl \-keep-blanks
Keep leading and trailing blank symbols.
.It Fl d , Fl \-decode
Decode sequences of ones in the output as decimal numbers.
.It Fl e , Fl \-encode
Encode numbers from the input as sequences of ones (unary notation).
.It Fl n , Fl \-numbers
A shortcut for
.Fl d Fl e .
.It Fl C , Fl \-no-color
Do not highlight the current position in the output or while tracing with
formating sequences.
Normally, when tracing or when the output is printed
without encoding, the current position is highlighted, which may pose a
problem when using this output further.
.El
.Ss The Source Language
The source language is a high-order language, described below in detail.
As an example, the following source get compiled into a machine
that computes the greatest common divisor of two given numbers:
.Bd -literal
	[a, b] = input;
	while b > 0:
		B = a mod b;
		a = b;
		b = B;
	endwhile;
	output = a;
.Ed
.Pp
Only single-line comments are supported.
They start with
.Ic #
anywhere on line.
.Pp
Every
.Em variable
represents one tape of the machine on which numbers can be written.
The special names
.Va input
and
.Va output
are reserved for the input tape and the output tape.
.Pp
The following types of
.Em expressions
are supported:
.Bl -tag -width Ds
.It A numeric constant (any positive integer or zero):
.Bd -literal
0
18
.Ed
.It The number of items on the tape of a variable:
.Bd -literal
count variable
\(*r variable
.Ed
.It The value of a variable or a specific slice thereof:
.Bd -literal
input # The first number of a variable
input[0] # Also the first number
input[0:1] # Also the first number
input[4] # The fifth number
input[5:7] # The fifth and sixth number
input[1:] # All numbers except the first one
input[0:2] # First two numbers
input[:2] # Also first two numbers
input[0:] # All numbers
input[:] # Also all numbers
input... # Also all numbers (either three dots or the Unicode ellipsis, both is supported)
.Ed
.It The result of a machine on a given input (any non-logical expressions); the result can be sliced:
.Bd -literal
f() # The result of the run of f on an empty tape (first number)
f()... # The result of the run of f on an empty tape (the whole tape)
g(input[0], input[1])[1] # The second number of the run of the g machine with the first two numbers of the input
g(input[:2])[1] # The same thing
g(12, input)... # The whole result of running g on a tape with the number 12 and the first number of the input
h(g(f(input)...)...)... # Composition of three functions
.Ed
.It Arithmetical and logical operations:
.Bd -literal
a + b # Addition
a - b # Subtraction, both hyphen-minus and Unicode minus is supported
a \[u22C5] b # Multiplication (Unicode dot operator)
a \[tmu] b # Also multiplication
a * b # Also multiplication
a / b # Integer division (undefined behavior for division by zero), both normal slash and Unicode fraction slash is supported
a \[u2236] b # Also division (Unicode ratio)
a mod b # Modulo (remainder; undefined behavior for division by zero)
a % b # Also modulo
a min b # Minumum of two values
a & b # Also minumum of two values
a max b # Maximum of two values
a | b # Also maximum of two values
a==b # Equality
a!=b # Inequality
a \(!= b # Also inequality
a < b # Less than
a > b # Greater than
a \*(<= b # Less than or equal
a <= b # Also less than or equal
a \*(>= b # Greater than or equal
a >= b # Also greater than or equal
!(a==b) # Negation
\[tno] a==b # Also negation
a==b \(AN c==d # Conjunction (and)
a==b && c==d # Also conjunction
a==b and c==d # Also conjunction
a==b \(OR c==d # Disjunction (or)
a==b || c==d # Also disjunction
a==b or c==d # Also disjunction
a==b xor c==d # Exclusive disjunction (xor)
.Ed
.El
.Pp
The following types of
.Em statements
are supported:
.Bl -tag -width Ds
.It A definition of a Turing machine:
.Bd -literal
dec1 = { A 1 0 R _ }; # old state, old symbol, new symbol, direction, new state
dec2 = { stateA 1 0 R stateB }; # Any state name is valid, if it does not contain a digit, a whitespace, } or #.
dec3 = { stateA10RstateB }; # The whitespace is optional (any number of spaces, tabs or newlines can be used).
inc1 = { A11LA A01N_ }; # More transitions (the old state of the first transitions is the initial state). This whitespace is not optional.
inc2 = { A11LA A01SB }; # _ had no special meaning, when the machine halts, the answer is read. S is an alias of N.
inc3 = {
	A 1 1 L A
	A 0 1 N _ # place one extra 1
}; # Using more lines and adding comments might improve legibility.
.Ed
.It \&An include of a machine defined in a separate file (the syntax of the machine file is the same as in the {} block):
.Bd -literal
include gcd; # gcd.tm is expected in the same directory as the source file, unless specified otherwise with CLI options.
.Ed
.It \&An include of a requried machine passed by a command line option at compile time:
.Bd -literal
require f; # Compilation requires an option like this: -m machine1.tm
require g; # More requirements require more -m options.
.Ed
.It Call of a Turing machine on a variable (a tape). Unlike call expressions, changes will affect the variable directly:
.Bd -literal
f(input...); # Using ... is required.
.Ed
.It Assignment of an expression to a variable, possibly at a given index, \
replacing all the content following (or preceding) the position:
.Bd -literal
output = 1; # The variable output will contain a single number 1.
output[2:] = 2; # The first two numbers will be preserved, 2 will rewrite the rest (undefined behavior for less than two numbers in output).
output[] = 3; # Append the number 3.
#output[4] = 4; # This is forbidden (for now), any destination slice must be rightwise unbounded. A workaround is output[4:] = [4, output[5:]]; or output[:5] = [output[:4], 5];.
output = input; # Assign the first number of input.
output = input...; # Assign the whole content of input.
output[10:] = f(input[5:8])[2:4]; # Any non-logical expression of any length can be assigned.
output = output[1:5];
output[2:] = output[1:5];
output[:0] = 1; # Prepend the number 1.
output[:2] = output[0]; # Replace the first two numbers with only the first one.
output[-1:] = 2; # Replace the last number with 1.
output[:-2] = input...; # Replace everything except the last two numbers with input.
.Ed
.It Incrementing or decrementating the first number on a tape:
.Bd -literal
a++;
b--; # Either two hyphen-minuses or two Unicode minuses.
.Ed
.It Branching ( Ic if , Ic elseif , Ic else Ns ):
.Bd -literal
if input==42:
	output = 1;
# The other branches are optional, endif can go here.
elseif input > 0:
	output = 2;
# More elseif branches can follow.
else:
	output = 0;
endif;
.Ed
.It Loops ( Ic while , loop , for Ns ):
.Bd -literal
loop: # Loop without condition (until break):
	while a > 0: # Loop with condition.
		if b==10:
			continue; # Skip to the next iteration of the innermost loop (the inner loop here).
		endif;
		a--;
	endwhile;
	b++;
	if a==10:
		break; # Exit the innermost loop (the outer loop here).
	endif;
endloop;

for x = 0; x < a; x++: # Initial statement, condition, step statement.
	if x % 5==0:
		continue; # Jump to the step statement.
	endif;
	output[] = x;
endfor;

for ; a > b; a--; b++: endfor; # The initial statement and the body is optional, there can be multiple step statements (but at least one).
.Ed
.It Ic exit No statement :
.Bd -literal
if output==20:
	exit; # Skip behind the last statement of the program.
endif;
output = 40; # This will be skipped if the first number of the output is 20.
.Ed
.It Joining (imploding) multiple expressions to a varible:
.Bd -literal
output = [1, 2, 3]; # output will contain those three numbers.
output[2:] = [1, 2, 3]; # The variable can be indexed.
output[] = [1, 2, 3]; # Appending is also possible.
output = [f(input)..., 10, input[2:5], output]; # Any non-logical expressions can be used.
output[:1] = []; # Delete the first number.
output[:0] = [1, 2, input]; # Prepend 1, 2, and the first number from input (the tape will then start with 1).
output[-3:] = [1, 2, 3]; # Replace the last three numbers with 1 2 3.
output[:-1] = [input, 0, output]; # Replace everything except the last number with input[0] 0 output[0].
.Ed
.It Splitting (exploding) an expression to multiple variables:
.Bd -literal
[a, b, c] = input; # First number goes to a, second number goes to b, third number goes to c (undefined behavior for less than 3 numbers in input).
[a, b...] = input; # First number goes to a, the reset goes to b (undefined behavior for empty input).
[a, b..., c, d] = input; # First number goes to a, last two numbers go to c and d, the rest goes to b (undefined behavior for less than 3 numbers in input).
[a, b] = input...; # The ellipsis can be there, but it is optional.
[a, b] = a[1:]; # Other indexation than ellipsis is possible, but it has to be rightwise unbounded.
[a, b] = f(a, b)...; # Any expression which can yield more numbers is possible as the right side. The ellipsis is optional here as well.
.Ed
.El
.Ss Instructions
In addition the source language described above, intermediate representation
(IR) can also be used.
The flags
.Fl i
and
.Fl I
are used to print the IR as output, while
.Fl l Cm ir
can be used to accept IR as input.
The first line of IR states how many tapes are used by the program.
It looks like this:
.Bd -literal
TAPES 3
.Ed
.Pp
If this line is missing, one tape is assumed.
The next lines are instructions.
Each line contains the name of the instructions followed by its arguments in
parentheses.
Leading and trailing whitespace and comments (#) are ignored.
Here is an example of a simple program:
.Bd -literal
TAPES 1
decompress(1) # Use tape 1 as input
compare(1[0] = 42, 2, 3) # Compare the first number on tape 1 with 42
jump(COMEFROM 2) # Come from the label 2 (if true)
writeNumber(1[0:], 1) # Write 1 on the beginning of tape 1
jump(GOTO 1) # Go to the label 1
jump(COMEFROM 3) # Jump from the label 3 (if false)
writeNumber(1[0:], 0) # Write 0 on the beginning of tape 1
jump(GOTO 1) # Go to the label 1
jump(COMEFROM 1) # Come from the label 1
compress(1) # Use tape 1 as output
.Ed
.Pp
The following instructions are supported:
.Bl -tag -width Ds
.It Ic decompress
This should be the first instruction of every program.
It specifies where the input of the compiled Turing machine should be placed.
The only argument of this instruction is the input tape.
.It Ic compress
This should be the last instruction of every program.
It specifies which tape is considered to be the output.
The only argument of this instruction is the output tape.
.It Ic writeNumber
This instruction writes a number on a specific position on a tape.
The rest of the tape is deleted.
When this instruction is executed, the tape must be long enough, so that
the position is no further than the end of the tape.
It has two arguments separated by comma: destination and number.
The destination has three variants:
.Bd -literal
writeNumber(2[5:], 10) # Write 10 directly after the fifth number on the tape 2
writeNumber(2[], 15) # Append 15 to the tape 2
writeNumber(2[\(mi2:], 20) # Replace the last two numbers on the tape 2 with 20 (Unicode minus)
.Ed
.It Ic clear
This instruction clears a range on a tape.
The range must start with the index 0 or must be rightwise unbounded.
The tape with range is the only argument.
.Bd -literal
clear(1[0:]) # Clear the whole tape 1
clear(1[0:5]) # Delete the first five numbers while keeping the rest
clear(1[5:]) # Delete everything after the fifth number
clear(1[\(mi1:]) # Delete the last number (Unicode minus)
#clear(1[0:\(mi1]) # This is not supported, you have to use REVERSE
.Ed
.It Ic copy
This instruction copies a range from one tape to another.
The arguments are: the source tape, the source range, comma, the destination
tape, the destination range.
The source range is specified by the first index, followed by colon and the
optional second index, all in square brackets.
The destination range must be rightwise unbounded, it is specified
by an index followed by colon, all in square brackets, or by empty sqaure
brackets, which means that the data should be appended.
All indices can be negative (indexed from the end), but both source indices
must have the same sign.
.Bd -literal
copy(3[0:1], 4[0:]) # Copy the first number of the tape 3 to the beginning of the tape 4, the content of the tape 4 will be lost
copy(3[1:], 4[]) # Copy the content of the tape 3 except for the first number to the end of the tape 4, the content of the tape 4 will not be lost
copy(3[1:], 4[]) # Copy the content of the tape 3 except for the first number to the end of the tape 4, the content of the tape 4 will not be lost
copy(1[\(mi2:\(mi1], 2[0:]) # Copy the penultimate number from the tape 1 to the tape 2
copy(1[\(mi1:], 2[\(mi1]) # Replace the last number of the tape 2 with the last number of tape 1
.Ed
.It Ic call
This instruction simulates a defined Turing machine on a single tape.
It has two arguments separated by comma: the tape and the machine.
.Bd -literal
call(1, { A11LA A01N_ }) # Increment the first number on tape 1
.Ed
.It Ic jump
This instruction jumps to or from a label, which is a number.
There are two types of jumps:
.Ic GOTO
and
.Ic COMEFROM .
Each label should be associated with one
.Ic COMEFROM
jump and
at least one
.Ic GOTO
jump, compare or compareTapeLength.
As arguments, the type (GOTO or COMEFROM) followed by the label (without comma)
is provided.
A
.Ic COMEFROM
jump must follow if and only if the previous instruction jumps
somewhere
.Po
.Ic GOTO
jump,
.Ic compare , compareTapeLength\&
.Pc .
.It Ic compare
This instruction compares two arguments and jumps to one of two specified
labels, depending on the result of the comparison.
The comparison arguments can either be constants or tapes with indices.
These operators can be used: \(eq, \(!=, <, >, \(<=, \(>=
.Bd -literal
compare(1[3] > 2[0], 1, 2) # If the fourth number on tape 1 is greater than the first number on tape 2, jump to 1, else jump to 2
compare(1[3] < 20, 3, 4) # If the fourth number on tape 1 is less than 20, jump to 3, else jump to 4
compare(1 = 1, 5, 6) # This always jumps to 5
.Ed
.It Ic compareTapeLength
This instruction compares the length of a tape with a number.
These operators can be used: \(eq, \(!=, <, >, \(<=, \(>=
.Bd -literal
compareTapeLength(|1| < 2, 1, 2) # If there are fewer than 2 numbers on the tape 1, jump to 1, else jump to 2
compareTapeLength(|2| = 0, 3, 4) # If the tape 2 is empty, jump to 3, else jump to 4
.Ed
.It Ic REVERSE
This is a pseudoistruction which causes the machine to work like in mirror.
The tape numbers will stay, but their starts will now be ends and vice versa.
This state will remain until the next
.Ic REVERSE .
It is possible to combine jumps with
.Ic REVERSE ,
but it is necessary that the reversed labels match (jumps from a reversed part
of the program must lead also to a reversed part).
.Bd -literal
REVERSE # Start the reversed state
clear(1[1:]) # This clears everything but the last number
REVERSE # End the reversed state
.Ed
.El
.Sh AUTHORS
.An Šimon Rataj Aq Mt ratajs@ratajs.cz
.Pp
This software was developed with the support of the
Faculty of Information Technology, Czech Technical University in Prague.
For more information, visit
.Lk https://fit.cvut.cz .