Class Notes (922,111)
CA (542,723)
UTSG (45,887)
CSC (768)
CSC104H1 (67)
F.Pitt (1)
Lecture

CSC363 Lecture Notes 1 - Introduction to Turing Machines

4 Pages
155 Views

Department
Computer Science
Course Code
CSC104H1
Professor
F.Pitt

This preview shows page 1. Sign up to view the full 4 pages of the document.
CSC363 Lecture Notes t 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

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
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
Unlock Document


Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

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


OR

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.


Submit