Universal Turing Machine

In this class, We discuss Universal Turing Machine.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of the Turing Machine. Click Here.

At the beginning of the truing machine, we said that the truing machine works as of today’s computer.

Is it correct?

Yes, Why is the statement correct? Understand in this class.

Our previous classes showed Turing machine works as addition, Subtraction, and comparator.

If we can do addition, Subtraction, and comparator, we can do any computation.

But today’s computer acts according to your input.

If we click on the game, the game will execute.

If we click on the application, the application will execute.

According to your input, the computer will execute the program.

Is it possible to use a turing machine? No.

We had a separate turing machine for addition, Subtraction, etc.

Universal turing machine exactly works as of today’s computers.

Universal turing machine had a finite control.

We have three tapes for a universal turing machine.

Tape 1: Used for representation of turing machines.

If we have a turing machine for the addition, we place it on tape 1.

How we place will be discussed down.

All the turing machines needed are placed on tape 1.

Tape 2: used to save the input.

Tape 3: Used to represent the state of the turing machine.

Suppose we are executing a turing machine. On which state the turing machine is working is maintained on tape 3.

With the help of finite control, we can execute any turing machine on tape 1 with the given input and maintain the states in tape 3.

Representing Turing Machine

Assume we have 3 states in our turing machine.

q0, q1, and q2 encoded as 1, 11, 111.

The input symbols are a, b.

We encode the input symbols as 1, 11.

We encode the direction left and right as 1, 11.

The transition function is δ(q0, a) = [q1, b, L]

We encode the transition as 10101101101.

q0 as 1 and a separation zero.

‘a’ as 1 and a separation zero.

We represent the transition function with a separation symbol zero.

Similarly, We converted each transition of the turing machine and placed it on tape.

All the turing machines are converted and placed on tape 1.