This

**preview**shows page 1. 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

###### You're Reading a Preview

Unlock to view full version