Turing Machines

Return to List of Lectures

Previous Lecture

• Misc
  • PRISM Mentoring
    • Wednesday, March 9, 3:30
    • South 328
    • Advice from math majors re course selection, summer experiences, etc.
• Kleene Discussion Comments
  • Neat thought in discussion about Kleene’s finite automata subsuming cellular automata
    • Could be an optional presentation at the end of the course if someone wants to take it a little further
  • Hard to read?
    • Need to make some allowance for more formal language in 1950s papers than now
    • But otherwise it’s not that different from reading modern math papers
      • Think carefully about what each claim says and why it follows from previous ideas
      • Keep careful track of variables
• Questions?
• Turing Machines
  • Section 3.1
    • Step up from finite and pushdown automata
    • Tape instead of stack
      • Can move back and forth (left and right) to read and change any element
    • Formal definition has 7 components
      • Q = set of states
      • Σ = input alphabet (does not contain blank)
      • Γ = tape alphabet (includes blank and maybe other symbols)
      • δ = transition function
      • q₀ = start state
      • q_accept = accept state
      • q_reject = reject state
    • Computation stops immediately on entering accept, reject states
    • Turing recognizable: L is Turing recognizable iff there exists a Turing machine that enters q_accept when started with any string in L
    • Turing decidable: L is Turing decidable iff there exists a Turing machine that enters q_accept when started with any string in L and enters q_reject when started with any string not in L
    • Examples
  • Our own examples
    • Decide aⁿb^mc^n+m
      • Idea: blank out cs at end of tape against as and bs at beginning
        
      • Algorithm:
        

        If 1st symbol is blank, accept (a0b0c0)
        Else
        	Repeat:
        		Write X
        		Search right for blank
        		Move left
        		If symbol not c, reject
        		Write blank
        		Search left for X
        		Move right
        		If symbol not a or b, reject (really ought to use 2 loops, one for a and one for b, to ensure as and bs in right order)           

    • Actually compute aⁿb^mc^n+m
      • Given input aⁿb^m
      • Enter q_accept with c^n+m on tape
        

        One left-to-right pass over tape
        	If symbol is a or b, write c and move right
        	If symbol is blank, accept

• Next
  • Other forms of Turing machine
  • Read section 3.2

Next Lecture