[ Imprint ] [ Data Privacy Statement ] [ Contact ] [

]

Turing Machine

No basic lecture in computer science can do without a mention of the Turing machine.

Martín Ugarte has written a very nice programmable simulator for Turing machines that gives students a very practical approach to this otherwise rather theoretical topic.

If you are listening to the lecture "Fundamentals of Computer Science" at the HFT Stuttgart, you will find here, in addition to the examples already explained there, further programs to deepen the topic and for your own experiments.

A guide explains how to use the pages in this website, their behaviour may be adjusted in the settings.

Programming

A program for the Turing simulator consists of a preamble and a series of definitions for the state transitions of the Turing machine.

The prefix defines the program name as well as the names of the initial state and the "acceptable" final states. If the Turing machine is in one of the named final states at the end of a program (i.e. when no more suitable state transitions can be found), the program is considered "accepted" (i.e. it has run through without errors) - otherwise an error has occurred.

name: program name
init: name of the initial state
accept: name of a final state, ..., possibly further names

The definition of a state transition consists of two lines each:

the first line defines the name of the state and the symbol that must be read from the memory tape so that the state transition just to be defined can take place.
the second line defines the name of the target state, specifies the symbol to be written into the current cell of the memory tape and defines in which direction the read/write head is to be moved afterwards.

name of current state,symbol to be read (or _ for an empty cell)
name of target state,symbol to be written,movement of read/write head

The read/write head can make the following movements

< - one field to the left
> - one field to the right
- - stay on the same field

Lines beginning with a double slash are considered comment lines and are ignored. Blank lines are also skipped:

// comment line

Work Flow

In the simplest case, the program source text is typed into the input field of the Turing simulator (or copied into it) and translated by clicking on the green "Compile" button.

After a successful translation, the simulator's user interface appears above the input field - otherwise the first translation error found is displayed there.

The user interface can be used to preset the memory band (with one character per field, as entered to the left of "Load") and to control the simulator.

Nota bene: you must still click "Load" even if you do not want to preallocate the memory band, but leave it empty.

and this is what it looks like.

Fig. 1: User interface of the Turing simulator

A few examples of Turing programs

At first, the examples are still trivial, but become successively more complicated. Later examples usually build on previous (simpler) ones.

An (almost) empty Program (to test translator and simulator)

Source Code

name: just an (almost) empty program
init: qInit
accept: qAccept

qInit,_
qAccept,_,-

Skipping a single "0"
Skipping fields on the memory tape is one of the most common actions in Turing programs
Source Code
```
name: skip a single zero
init: q0
accept: q1

q0,0
q1,0,>
```
State Diagram

Fig. 2: Zustandsdiagramm

Skip all subsequent "0 "s
Source Code
```
name: skip all zeros
init: q0
accept: q0

q0,0
q0,0,>
```
State Diagram

Fig. 3: Zustandsdiagramm

Skipping a single Bit
. A "bit" here is a field on the memory tape with the content "0" or "1".
Source Code
```
name: skip a single bit
init: q0
accept: q1

q0,0
q1,0,>

q0,1
q1,1,>
```
State Diagram

Fig. 4: Zustandsdiagramm

Skip all subsequent Bits
Source Code
```
name: skip all bits
init: q0
accept: q0

q0,0
q0,0,>

q0,1
q0,1,>
```
State Diagram

Fig. 5: Zustandsdiagramm

Invert a single Bit
Source Code
```
name: invert a single bit
init: q0
accept: q1

q0,0
q1,1,>

q0,1
q1,0,>
```
State Diagram

Fig. 6: Zustandsdiagramm

Invert all the subsequent Bits
Load the memory tape with a sequence of bits (i.e. a sequence of "0" and "1") and watch the Turing machine invert them bit by bit.
Source Code
```
name: invert all bits
init: q0
accept: q0

q0,0
q0,1,>

q0,1
q0,0,>
```
State Diagram

Fig. 7: Zustandsdiagramm

Writing a parity Bit
This is the example from the lecture: load the memory tape with a bit sequence (i.e. a sequence of "0" and "1") and watch the Turing machine add a parity bit.

Source Code

name: Parity Bit Generator
init: qEvenParity
accept: qAccept

qEvenParity,0
qEvenParity,0,>

qEvenParity,1
qOddParity,1,>

qEvenParity,_
qAccept,0,-

qOddParity,0
qOddParity,0,>

qOddParity,1
qEvenParity,1,>

qOddParity,_
qAccept,1,-

Right-shifting a single Bit

Source Code

name: shift a single bit to the right
init: q0
accept: q3

q0,0
q1,_,>

q1,_
q3,0,>

q0,1
q2,_,>

q2,_
q3,1,>

State Diagram

Fig. 8: Zustandsdiagramm

Right-shifting all subsequent Bits

Source Code

name: shift all bits to the right
init: q0
accept: q3

q0,0
q1,_,>

q0,1
q2,_,>

q1,0
q1,0,>

q1,1
q2,0,>

q1,_
q3,0,>

q2,0
q1,1,>

q2,1
q2,1,>

q2,_
q3,1,>

State Diagram

Fig. 9: Zustandsdiagramm

Left-shifting a single Bit

Source Code

name: shift a single bit to the left
init: q0
accept: q3

q0,0
q1,_,<

q1,_
q3,0,<

q0,1
q2,_,<

q2,_
q3,1,<

State Diagram

Fig. 10: Zustandsdiagramm

Left-shifting of all subsequent Bits
This example is not a mirror-image copy of the program for shifting several bits to the right, but also works through the bit sequence from left to right.
Source Code
```
name: shift all bits to the left
init: q0
accept: q0

q0,0
q1,_,<

q0,1
q3,_,<

q1,_
q2,0,>

q2,_
q0,_,>

q3,_
q2,1,>
```
State Diagram

Fig. 11: Zustandsdiagramm

Increment a single-Digit binary Number
Load the memory tape with a single "0" or "1", the program will increment this binary number by 1.
Source Code
```
name: increment a single bit
init: q0
accept: q1

q0,0
q1,1,<

q0,1
q2,0,<

q2,_
q1,1,<
```
State Diagram

Fig. 12: Zustandsdiagramm

Incrementing a multi-Digit binary Number
This program increments any binary number written to the memory tape.
Source Code
```
name: increment a binary number
init: q0
accept: q3

q0,0
q0,0,>

q0,1
q0,1,>

q0,_
q1,_,<

q1,0
q2,1,<

q1,1
q1,0,<

q1,_
q3,1,<

q2,0
q2,0,<

q2,1
q2,1,<

q2,_
q3,_,-
```
State Diagram

Fig. 13: Zustandsdiagramm

Form the 2's complement for a given binary Number
Load the memory tape with an arbitrary binary number and follow how the Turing machine forms the 2's complement of this number.
Source Code
```
name: compute 2th complement
init: q0
accept: q1,q2

q0,0
q0,1,>

q0,1
q0,0,>

q0,_
q1,_,<

q1,0
q2,1,<

q1,1
q1,0,<

q2,0
q2,0,<

q2,1
q2,1,<
```
State Diagram

Fig. 14: Zustandsdiagramm

Bitwise conjunction of two Bit Sequences
Load the memory tape with two arbitrary (but equally long) bit sequences and leave exactly one field free between them - in the Turing simulator you achieve this by an underscore ("_"), a space is not accepted as input. The Turing machine will write a bitwise conjunctive combination of your inputs on the tape after the second bit sequence.

Source Code

name: compute conjunction of two bit sequences
init: q0
accept: q0

q0,0
q1,.,>

q0,1
q5,.,>

q1,0
q1,0,>

q1,1
q1,1,>

q1,_
q2,_,>

q2,.
q2,.,>

q2,0
q3,.,>

q2,1
q3,.,>

q3,0
q3,0,>

q3,1
q3,1,>

q3,_
q4,_,>

q4,0
q4,0,>

q4,1
q4,1,>

q4,_
q9,0,<

q5,0
q5,0,>

q5,1
q5,1,>

q5,_
q6,_,>

q6,.
q6,.,>

q6,0
q3,.,>

q6,1
q7,.,>

q7,0
q7,0,>

q7,1
q7,1,>

q7,_
q8,_,>

q8,0
q8,0,>

q8,1
q8,1,>

q8,_
q9,1,<

q9,0
q9,0,<

q9,1
q9,1,<

q9,_
q10,_,<

q10,0
q10,0,<

q10,1
q10,1,<

q10,.
q10,.,<

q10,_
q11,_,<

q11,0
q11,0,<

q11,1
q11,1,<

q11,.
q0,.,>

State Diagram

Fig. 15: Zustandsdiagramm

Bitwise disjunction of two Bit Sequences
Load the memory tape with two arbitrary (but equally long) bit sequences and leave exactly one field free between them - in the Turing simulator you achieve this by an underscore ("_"), a space is not accepted as input. The Turing machine will write a bitwise disjunctive combination of your inputs on the tape after the second bit sequence.

Source Code

name: compute disjunction of two bit sequences
init: q0
accept: q0

q0,1
q1,.,>

q0,0
q5,.,>

q1,0
q1,0,>

q1,1
q1,1,>

q1,_
q2,_,>

q2,.
q2,.,>

q2,0
q3,.,>

q2,1
q3,.,>

q3,0
q3,0,>

q3,1
q3,1,>

q3,_
q4,_,>

q4,0
q4,0,>

q4,1
q4,1,>

q4,_
q9,1,<

q5,0
q5,0,>

q5,1
q5,1,>

q5,_
q6,_,>

q6,.
q6,.,>

q6,1
q3,.,>

q6,0
q7,.,>

q7,0
q7,0,>

q7,1
q7,1,>

q7,_
q8,_,>

q8,0
q8,0,>

q8,1
q8,1,>

q8,_
q9,0,<

q9,0
q9,0,<

q9,1
q9,1,<

q9,_
q10,_,<

q10,0
q10,0,<

q10,1
q10,1,<

q10,.
q10,.,<

q10,_
q11,_,<

q11,0
q11,0,<

q11,1
q11,1,<

q11,.
q0,.,>

State Diagram

Fig. 16: Zustandsdiagramm

Addition of two unsigned binary Numbers
Load the memory tape with any two unsigned binary numbers (but of equal length) and leave exactly one space between them - in the Turing simulator you achieve this by an underscore ("_"), a space is not accepted as input. The Turing machine will write the sum of your input behind the second number on the tape - if the number of bits you have specified is sufficient for this.
The program proceeds somewhat differently than you are used to from the lecture: the two numbers are added up bit by bit from left to right and any digit carryovers are entered immediately - in this way, a final overflow can possibly be detected quite early during the calculation.
Source Code
```
name: compute the sum of two binary numbers
init: q0
accept: q0

q0,0
q1,.,>

q0,1
q8,.,>

q1,0
q1,0,>

q1,1
q1,1,>

q1,_
q2,_,>

q2,.
q2,.,>

q2,0
q3,.,>

q2,1
q10,.,>

q3,0
q3,0,>

q3,1
q3,1,>

q3,_
q4,_,>

q4,0
q4,0,>

q4,1
q4,1,>

q4,_
q5,0,<

q5,0
q5,0,<

q5,1
q5,1,<

q5,_
q6,_,<

q6,0
q6,0,<

q6,1
q6,1,<

q6,.
q6,.,<

q6,_
q7,_,<

q7,0
q7,0,<

q7,1
q7,1,<

q7,.
q0,.,>

q8,0
q8,0,>

q8,1
q8,1,>

q8,_
q9,_,>

q9,.
q9,.,>

q9,0
q10,.,>

q9,1
q12,.,>

q10,0
q10,0,>

q10,1
q10,1,>

q10,_
q11,_,>

q11,0
q11,0,>

q11,1
q11,1,>

q11,_
q5,1,<

q12,0
q12,0,>

q12,1
q12,1,>

q12,_
q13,_,>

q13,0
q13,0,>

q13,1
q13,1,>

q13,_
q14,0,<

q14,0
q5,1,<

q14,1
q14,0,<
```
State Diagram

Fig. 17: Zustandsdiagramm

Addition of two unsigned binary Numbers (according to Coors)
If you are listening to my lecture "Fundamentals of Computer Science", you will find another Turing program for the addition of binary numbers in the slides of Prof. Coors.
1. convert the state diagram from Prof. Coors' slides into a program for the simulator
  Nota bene: Prof. Coors' program starts the addition in the middle of the memory tape (which is generally perfectly acceptable). However, in order for the simulator to do something with it, the read/write head must first be moved to this position by the following initial lines:
```
qPre,0
qPre,0,>

qPre,1
qPre,1,>

qPre,_
q1,_,>
```
  The new initial state is therefore no longer q0, but qPre.
  Source Code (for Verification)
```
name: compute the sum of two binary numbers
init: qPre
accept: q8

qPre,0
qPre,0,>

qPre,1
qPre,1,>

qPre,_
q1,_,>

q0,_
q1,_,>

q1,0
q1,0,>

q1,1
q2,1,>

q1,_
q3,_,<

q2,0
q2,0,>

q2,1
q2,1,>

q2,_
q4,_,<

q3,0
q3,_,<

q3,_
q8,_,<

q4,0
q4,1,<

q4,1
q5,0,<

q5,0
q5,0,<

q5,1
q5,1,<

q5,_
q6,_,<

q6,0
q7,1,>

q6,1
q6,0,<

q6,_
q7,1,>

q7,0
q7,0,>

q7,1
q7,1,>

q7,_
q1,_,>
```
2. Test the program by entering "1001_100"
  (how does the program perform the addition?)

Busy beavers

Turing machines are mainly used for theoretical considerations - in practice they have no meaning at all.

A well-known question is: how many "1 "s can a Turing machine with n states write to a memory tape initially filled with "0 "s and then stop(!)?

Turing programs that fulfil this condition are called "busy beavers".

The solution for a Turing program with only one state is obvious:

Fig. 18: State Diagram for a "busy Beaver" with one State

Below are examples of "busy beavers" with up to six states. The last two programs are only considered "candidates" for a "busy beaver" because they can no longer be tested practically due to their immense running time.

However, the first four examples can still be tried out well in the simulator.

"Busy Beaver" with a single State

Source Code

name: busy beaver with one state
init: q0
accept: q1

q0,_
q1,1,>

"Busy Beaver" with two states

Source Code

name: busy beaver with two states
init: q0
accept: q2

q0,_
q1,1,>

q0,1
q1,1,<

q1,_
q0,1,<

q1,1
q2,1,>

"Busy Beaver" with three states

Source Code

name: busy beaver with three states
init: q0
accept: q3

q0,_
q1,1,>

q0,1
q3,1,>

q1,_
q2,_,>

q1,1
q1,1,>

q2,_
q2,1,<

q2,1
q0,1,<

"Busy Beaver" with four states

Source Code

name: busy beaver with four states
init: q0
accept: q4

q0,_
q1,1,>

q0,1
q1,1,<

q1,_
q0,1,<

q1,1
q2,_,<

q2,_
q4,1,>

q2,1
q3,1,<

q3,_
q3,1,>

q3,1
q0,_,>

Candidate for a "Busy Beaver" with five States

Source Code

name: busy beaver with five states
init: q0
accept: q5

q0,_
q1,1,>

q0,1
q2,1,<

q1,_
q2,1,>

q1,1
q1,1,>

q2,_
q3,1,>

q2,1
q4,_,<

q3,_
q0,1,<

q3,1
q3,1,<

q4,_
q5,1,>

q4,1
q0,_,<

Candidate for a "Busy Beaver" with six States

Source Code

name: busy beaver with six states
init: q0
accept: q6

q0,_
q1,1,>

q0,1
q4,1,<

q1,_
q2,1,>

q1,1
q5,1,>

q2,_
q3,1,<

q2,1
q1,_,>

q3,_
q4,1,>

q3,1
q2,_,<

q4,_
q0,1,<

q4,1
q3,_,>

q5,_
q6,1,<

q5,1
q2,1,>

Credits

This web page uses the following third-party libraries, assets or StackOverflow answers:

Font Awesome Free 4.7.0
License: SIL Open Font License (OFL)
answer to StackOverflow question How to get the global object in JavaScript?
contributed by Christian C. Salvadó
License: CC BY-SA 2.5
jQuery - jQuery JavaScript Library
Copyright OpenJS Foundation and other contributors, https://openjsf.org/
License: MIT License

The author would like to thank the developers and authors of the above-mentioned contributions for their effort and willingness to make their works available to the general public.

https://www.rozek.de/Turing-Machine/index_en.html

02/06/2021