Formal language &automata theory topic: types of turing machines

[Audio] Formal language &automata theory topic: types of turing machines In this presentation we are going to see types of turing machine.

[Audio] Introduction to Turing Machines A Turing machine is a theoretical machine that manipulates symbols on a tape strip, based on a table of rules. Even though the Turing machine is simple, it can be tailored to replicate the logic associated with any computer algorithm. It is also particularly useful for describing the CPU functions within a computer.

[Audio] standard Turing machine. A standard Turing Machine is a machine which on providing an input moves either to the left or right and it may overwrite the existing symbol. A standard Turing machine is capable of accepting some of the languages, called recursively enumerable language..

[Audio] transition rules If in state 1 and the input is 0, then write a 0, transition to state 1, and move right. If in state 1 and the input is 1, then write a 1, transition to state 2, and move right. If in state 1 and the input is B (end), then write a 1, transition to state 3, and move right. The machine's transition function is the “program” that specifies each of these actions (overwriting the current symbol, moving left or right, entering a new state, optionally halting and outputting an answer) given the current state and the symbol the machine is currently reading. ..

[Audio] deterministic Turing machine Turing machines are a model of computation. It is believed that anything that can be computed can be computed by a Turing Machine. The definition won’t look like much, and won’t be used much A Turing Machine is a tuple (Q, Σ, δ, s, h) where • Q is a finite set of states. It has the states s, qacc, qrej . • Σ is a finite alphabet. It contains the symbol #. • δ : Q − × Σ → Q × Σ ∪ • s ∈ Q is the start state, qacc is the accept state, qrej is the reject state..

[Audio] deterministic turing machine In ths deterministic turing machine it has only one finite control and one read write head.

[Audio] non-deterministic Turing machine A non-deterministic Turing machine is a variant of the simple Turing machine. For every input at a state, there can be multiple paths/actions performed by the TM, meaning the transitions are not deterministic..

[Audio] multi-tape Turing machine A multi-tape Turing machine is a variant of the Turing machine that utilizes several tapes. Each tape has its own head for reading and writing the header can move up and down and in the left or right direction. Whereas in a normal Turing machine, the header can only move in Left or Right. The multidimensional turing machine is defined by 7 tuples..

[Audio] universal Turing machine. Construction of UTM Without loss of generality, we assume the following for M: Q = where q1=initial state and q2=Final State τ = where σ represent blanks Select an encoding on which q1 is representable by 1, q2 by 11, and so on. Similarly, σ1 is encoded as 1, σ2 as 11, etc. Finally, let us represent R/W head directions by 1 for L (Left) and 11 for R(Right). The symbol 0 will be used as a separator between 1s. Construction of UTM Without loss of generality, we assume the following for M: Q = where q1=initial state and q2=Final State τ = where σ represent blanks Select an encoding on which q1 is representable by 1, q2 by 11, and so on. Similarly, σ1 is encoded as 1, σ2 as 11, etc. Finally, let us represent R/W head directions by 1 for L (Left) and 11 for R(Right). The symbol 0 will be used as a separator between 1s..

[Audio] universal Turing machine. universal Turing machine.

[Audio] Thankyou. [image].