Understanding Turing Machines in Theory of Computation (TOC) | Lesson 82

Turing Machine in TOC
In this class, We discuss Turing Machine in TOC.
The reader should have prior knowledge of PDA. Click Here.
First, we refresh the concepts of finite automata and push-down automata. And move to a Turing machine.
Finite automata do not have any memory.
Without having any memory devices, we can process some languages.
In push-down automata, we have a stack memory.
The push-down automata can design the languages defined using finite automata, and We difine other languages.
The turing machine has a tape memory.
Tape Memory: An infinite sequence of memory locations
Whatever today’s computers are capable of doing computations. Turing machine is capable of doing the same computations.
Point to understand: With the evolution of memory devices, computations are also evolved.
The components of Turing Machine.
The Turing machine contains a finite control and a tape.
The above diagram shows the finite control and the tape memory.
Each cell in the tape memory is filled with an input character or a Blank symbol.
The blank symbol is given using ‘B’.
The input is given 1011.
The left and right of the input have blank symbols.
The turing machine starts from the beginning of the input.
The turing machine contains states. Similar to finite automata and pushdown automata.
Finite control:
1) change state
2) Write a tape symbol
the first input character is 1. using finite control, we can change the first input character to X.
We can use any symbol.
3) move to the left or right one step on tape.
In our next class, we will discuss how to construct a Turing machine.
Turing machine is represented using a 7 tuple.
M = (Q, Σ, τ, δ, q0, B, F)
Q is a finite set of states.
Σ is a finite set of input symbols.
In our example Σ = {0,1}
τ is a finite set of complete tape symbols.
Tape symbols include input symbols also.
Σ subset τ
Example: τ = {0,1,X,Y,B}
Blank symbol is included in τ.
δ is transition function.
Example: δ (q,x) = [P, y, D].
q is the state where Turing machine is present.
x is the input symbol on which finite control is present.
P is the state we move to in this transition.
y is the symbol to write on the tape.
D is direction. We can move one step left or right.
q0 is the initial state.
F is the set of final states.
B is the blank symbol.

Link for playlists:
https://www.youtube.com/channel/UCl8x4Pn9Mnh_C1fue-Yndig/playlists


Link for our website: https://learningmonkey.in

Follow us on Facebook @ https://www.facebook.com/learningmonkey

Follow us on Instagram @ https://www.instagram.com/learningmonkey1/

Follow us on Twitter @ https://twitter.com/_learningmonkey

Mail us @ learningmonkey01@gmail.com