Show Menu

Automata - Turing Machines Cheat Sheet by

Automata - Turing Machines

Turing Machine Basics

Transi­tions 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
Σ: Input Alphabet
Γ: Tape Alphabet
δ: Transition functions
q0: Initial state
: Blank
F: Accept States
Deciders are Turing Machines that halt on all strings: always either accept or reject an input, never loop (infin­itely)
Recogn­izers 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 repres­ented as 1s e.g. 5=11111)
Initial and Final config­ura­tions are at the begining of the tape

Stay-O­ption TM

Head can move Left, Right or Stay
Stay-O­ption machines simulate Standard Turing machines (just dont use the stay)
Standard Turing machines simulate Stay-O­ption machines: just change the Stay transi­tions from
a→b,S to
a→b,L and x→x,R where x∈Γ

Semi-I­nfinite Tape TM

The head extends infinitely only to the right
Standard Turing machines simulate Semi-I­nfinite machines
Insert special symbol # on the left of the input string and add a selfloop to every state of #→#,R
Semi-I­nfinite 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
Transi­tions 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

Multid­ime­nsional TM

For example 2-dime­nsional tape, has moves L,R,U,D (Up, down) and position of x and y
Multid­ime­nsional machines simulate Standard Turing machines: only use 1 dimension
Standard Turing machines simulate Multid­ime­nsional machines: Two tape machine
•One tape with two tracks (symbols in track 1, coordi­nates in track 2)
•Second tape for current coordi­nates

Nondet­erm­inistic TM

Nondet­erm­inistic machines simulate Standard (deter­min­istic) Turing machines
Standard (deter­min­istic) Turing machines simulate Nondet­erm­inistic machines:{{nl}]•Use a 2D Tape
•Store all possible comput­ations of the non-de­ter­min­istic machine on the 2D Tape


No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Automata - CFG & PDA Cheat Sheet

          More Cheat Sheets by Vipera

          Automata Cheat Sheet
          Automata - CFG & PDA Cheat Sheet