CSC104H1 Lecture : CSC363 Lecture Notes 1 - Introduction to Turing Machines
155 views4 pages
Document Summary
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). Tm can both read and write symbols. 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}*
Get access
Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers