Automata - Turing Machines
|
Transitions are in form: a→b,L
meaning read a, write b, move left |
|
Accept input if machine halts in an accept state
|
|
Reject input if machine halts in a non-accept state or machine enters an infinite loop
|
|
Turing Machine:
|
M = (Q,Σ,Γ,δ,q0,◊,F)
|
|
Q: States
|
{q0,q1,q2}
|
|
Σ: Input Alphabet
|
{a,b}
|
|
Γ: Tape Alphabet
|
{a,b}
|
|
δ: Transition functions
|
δ(q1,c)=(q2,d,L)
|
|
q0: Initial state
|
|
|
◊: Blank
|
|
|
F: Accept States
|
{q2}
|
|
Use unary (number represented as 1s e.g. 5=11111)
|
|
Initial and Final configurations are at the begining of the tape
|
|
Head can move Left, Right or Stay
|
|
Stay-Option machines simulate Standard Turing machines (just dont use the stay)
|
|
Standard Turing machines simulate Stay-Option machines: just change the Stay transitions from
a→b,S to a→b,L and x→x,R where x∈Γ |
|
The head extends infinitely only to the right
|
|
Standard Turing machines simulate Semi-Infinite machines
Insert special symbol # on the left of the input string and add a selfloop to every state of #→#,R |
|
Semi-Infinite tape machines simulate Standard Turing machines: Squeeze infinity of both directions in one direction
|
|
Input string appears on Tape 1, but both tapes are read/write
|
|
Transitions are in form: (b, f ) →(g,d),L,R
|
|
Multi-tape machines simulate standard Turing Machines: The second one just remains empty
|
|
Standard Turing machines simulate Multi-tape machines: Uses a multi-track tape to simulate the multiple tapes
|
|
For example 2-dimensional tape, has moves L,R,U,D (Up, down) and position of x and y
|
|
Multidimensional machines simulate Standard Turing machines: only use 1 dimension
|
|
Standard Turing machines simulate Multidimensional machines: Two tape machine
•One tape with two tracks (symbols in track 1, coordinates in track 2) •Second tape for current coordinates |
|
Nondeterministic machines simulate Standard (deterministic) Turing machines
|
|
Standard (deterministic) Turing machines simulate Nondeterministic machines:{{nl}]•Use a 2D Tape
•Store all possible computations of the non-deterministic machine on the 2D Tape |
No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.
