Universal Turing Machine Emulator

Turing Machine CodeTapeEverything after 111 in TM code will be used as tape

Example

Don't forget to add the input character sequence $w$ after the input $M$ (separated by a 111).

$L=\{w_{1}00w_2|w_1,w_2\in \{0,1{\}}^{\ast }\}$

1010100010100110100101001001100010100001010011000100101001001100001010000101001100001001000010010011000010001001000100

$L=\{0w|w\in \{0,1{\}}^{\ast }\}$

101010010100

Documentation

The input $Co{d}_M$ is a binary string consisting of 0s and 1s which encodes a Turing Machine (TM) $M$. Initially, the head of the machine is positioned at the leftmost character of the word $w$. In this context, the word $w$ is clearly separated from the TM $M$ by a triplet of 1s (111) and is processed without undergoing any form of encoding.

For example, a transition in the TM represented as $\delta (q_1,1)=(q_3,0,R)$ is encoded in the binary format 0100100010100. The word $w$, on the other hand, remains in its original, un-encoded form. For example, 00ab would be represented directly as 00ab. Thus, the complete input string is formulated as $Co{d}_{M}111w$ or 0100100010100$⨁$111$⨁$00ab, where $⨁$ denotes the concatenation operator.

This document describes the coding scheme for the Turing machine $M$, formally expressed as $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_1,\text{␣},\{q_2\})$. Note that $q_1$ must always be the initial state, and $q_2$ is the only accepting state.

1. State $Q$

0 = q1 (start / initial state)
00 = q2 (accept / final state / halt)
000 = q3
0000 = q4
and so on...

TIP

Any TM with multiple accepting states can be converted to an equivalent TM with only one accepting state.

2. Tape Symbol $\mathrm{\Gamma }$

0 = 0
00 = 1
000 = _ (blank)
0000 = a
00000 = b
000000 = c
and so on...

3. Direction $D$

L = 0
R = 00

4. Transition Function $\delta$

A transition $\delta (q_i,X_j)=(q_k,X_l,D_m)$ of a TM is coded via the character string:

$0^i{10}^j{10}^k{10}^l{10}^m$ with $(i,j,k,l,m\in \mathbb{N})$

5. Concatenation of Transitions $\delta$

The individual transitions are separated from each other by 11 (each $C_i$ stands for one transition):

$C_{1}11C_{2}11C_{3}11...11C_n$

TIP

You can visualize the TM as a graph to check that the transitions are correct.

6. Concatenation of TM and input character sequence

The sequence 111 in the input for $M$ serves as a unique separator between the character sequence that encodes $M$ and the input character sequence $w$ for $M$: $Co{d}_{M}111w$.

Optionally, a 1 can be prepended to the binary string to represent the TM as a decimal number.

Debugging

Make sure that the TM has an initial and final state. Where q1 is the initial state and q2 is the final state.

You can debug your TM by checking the interpreted transition table or by visualizing the TM as a graph. If the TM halted in a rejected state, the state in which it halted will be highlighted in the graph.

---

This webpage was developed as part of the course Theory of Computation at the Zurich University of Applied Sciences (ZHAW). It is based on the course material, in particular the lecture notes Teil 6: Turingmaschinen - Universelle-TM. More information about the course can be found on the course page. Feedback is welcome and can be sent to your teaching assistant (TA) or to Pascal Andermatt.