Class Notes (807,535)
Canada (492,709)
CSC104H1 (59)
F.Pitt (1)

CSC363 Lecture Notes 1 - Introduction to Turing Machines

4 Pages
Unlock Document

University of Toronto St. George
Computer Science

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
More Less

Related notes for CSC104H1

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.