Turing Machine Basics
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 Machines Definition
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} |
Deciders are Turing Machines that halt on all strings: always either accept or reject an input, never loop (infinitely)
Recognizers are Turing Machines that will halt and accept the strings in the language and either reject or do not halt for strings not in the language
Computing Functions with TM
Use unary (number represented as 1s e.g. 5=11111) |
Initial and Final configurations are at the begining of the tape |
|
|
Stay-Option TM
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∈Γ |
Semi-Infinite Tape TM
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 |
Multi-Tape TM
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 |
Multidimensional TM
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 TM
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 |
|
|
|
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets
More Cheat Sheets by Vipera