Class Notes (1,100,000)
CA (630,000)
UTSG (50,000)
CSC (1,000)
F.Pitt (1)

CSC363 Lecture Notes 1 - Introduction to Turing Machines

Computer Science
Course Code

This preview shows page 1. to view the full 4 pages of the document.
CSC363 Lecture Notes t Week 1
Turing Machines
- 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"
You're Reading a Preview

Unlock to view full version