Appearance

# Universal Turing Machine Emulator

**Turing Machine Code**

**Tape**Everything after

`111`

in TM code will be used as tape## Example

Don't forget to add the input character sequence `111`

).

`1010100010100110100101001001100010100001010011000100101001001100001010000101001100001001000010010011000010001001000100`

`101010010100`

## Documentation

The input `0`

s and `1`

s which encodes a Turing Machine (TM) `1`

s (`111`

) and is processed without undergoing any form of encoding.

For example, a transition in the TM represented as `0100100010100`

. The word `00ab`

would be represented directly as `00ab`

. Thus, the complete input string is formulated as `0100100010100`

`111`

`00ab`

, where

This document describes the coding scheme for the Turing machine

### 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

### 5. Concatenation of Transitions $\delta $

The individual transitions are separated from each other by `11`

(each

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

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.*