CSC363 Lecture Notes 1 - Introduction to Turing Machines

120 views4 pages
11 Mar 2011
School
Course
Professor
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
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Already have an account? Log in

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+
$10 USD/m
Billed $120 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers