You have to define Turing Machines that work on binary strings. The encoding must allow the user to define any normal TM with its transitions, including states, read from tape, write to tape, move right, left or stay. The encoding must also separate the TM definition from the string to simulate.

The encoding can use any tricks$/$means needed to help on building in an easier manner the TMs and the overall UTM.

The encoding must also allow generating pseudo$-$random TMs$.$

Example

For instance, a valid encoding could be something like this:

$$0$T$0$#$0$#$00$#$1$#RT$0$#$0$#$00$#$1$#L$$110011$

Here, $ separates the TMs definition from the string w $110011.$

The first $0$ means q$0$ is a final state. Multiple final states could be provided with some separator. The encoding uses the pattern of q$0=0,$ q$1=00,$ q$2=000,$ and so on$,$ to encode states.

The TM definition is formed by $2$ transitions separated by a T$.$ The first transition $0$#$0$#$00$#$1$#R shows separators using # for $5$ pieces. The first $0$ is q$0,$ the second $0$ is the symbol $0$ to be read from the input tape during the simulation, the next $00$ means q$1,$ while the $1$ means it will write a $1$ in the input tape. The final R means move to the right.

The UTM

It is recommended to divide it into smaller TURING MACHINES. For instance, as part of the UTM, there has to be an initial TM that checks if the input string follows the defined encoding, and if not it rejects.

Then there has to be a TM that simulates the execution of the TMs that are encoded, it has to keep track of the current state, it has to be able to read the transitions, keep a head where the reading and writing into the input tape is happening.

It is recommended to use multiple tapes, as it helps in separating state management, input tape management, and transitions.

TM for encoding

TM for finding transitions

TM for executing the rest of the simulation and accept$/$reject