CSC363 Lecture Notes J Week 1 Turing Machines Motivation: - Goal: define computation as abstractly and generally as possible. - Many possible formalizations: start with one, study it, then compare with others. Informal idea: similar to FSA but with no limitation on access to input: - one-way infinite tape divided into squares (or cells) (each square holds one symbol); - read-write head positioned on one square at a time; - control can be in one of a fixed number of states; - initially, tape contains input (one symbol per square, starting on leftmost square) and blanks, and head is on leftmost input symbol; - current state and symbol read determine next state, symbol written, and movement of head (one square left or right). Differences between FSA and Turing machines: - TM can both read and write symbols. - Infinite tape. - Head can move left or right (convention: moving left on leftmost square leaves head where it is). - Special accept and reject states that stop computation immediately. Example: M_1 that accepts exactly strings of the form w#w for w (- {0,1}* Read first symbol and cross it off (replace with new symbol x), move right until #, keep moving right until first non-x symbol to verify same as first symbol seen earlier (remembered through states), cross it off and go back to leftmost non-x symbol to repeat. If more than one # or different symbols or more symbols on one side than the other, reject; otherwise, accept. Formal definition: - A TM is a 7-tuple (Q,Sigma,Gamma,delta,q_0,q_accept,q_reject), where . Q: fixed, finite, non-empty set of states . q_0 (- Q: start state (or initial state) . q_accept (- Q: accepting state www.notesolution.com

More
Less