# CSC363 Lecture Notes 1 - Introduction to Turing Machines

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

## 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}*