Computer Science 3331A/B Chapter Notes - Chapter 17: Turing Machine, Halting State, If And Only If
22 Jan 2020
School
Department
Course
Professor
Document Summary
Powerful enough to describe all computable things- unlike fsm and pda. Simple enough so we can formally reason with it- like fsm and pda, unlike computers. At each step: choose next state, write on current square, move left or right. Turing machine m behaviour will be defined only on finite input strings and only characters on m"s input alphabet. M has single r/w head- when m starts, r/w head at blank immediately to the left of the leftmost character of input: may be at a different location in the case of subroutines. Initially, all tape sq that do not have character in are blank sq. Careful of writing blank sq- m must be able to tell that its not going into infinite, but it is reading a patch of blank sq. Active tape- shortest fragment of all of m"s tape that includes square under r/w head and all noblank squares.
