FIT2014 Lecture 14: Turing Machine
29 Jun 2018
School
Department
Course
Professor
Lecture 14: Turing Machine
Turing Machine Setup:
- Infinitely long tape divided into cells
- Each cell may contain a symbol from a finite alphabet
- Head scans one tape cell at a time.
- The machine is in some state
Program: For each state and symbol, specify the next state, next symbol and direction (one step left and one
step right) ( we don’t stand still)
Computation step: at each step, apply the appropriate instruction.
When we in state one, if we read a in the tape cell, we replace a with A and we move Rright in the tape. And if
we read a again in state three, we read and simply move to the right. And so on.
TM Components
- A Tape and Tape Head
- An Input Alphabet
- A Tape Alphabet (could be larger than the input alphabet)
- A finite set of states
- Each state is numbered by an integer ≥ 1.
- Start State (1)
- Accept State (2)
Note: a Reject state is optional (if crash = reject) A finite set of rules letter → letter, direction between states
For a Turing Machine T
Accept(T): The set of strings leading to the Accept state. Called the language accepted by T.
Reject(T): The set of strings that crash, or lead to a Reject state (if there is one), during execution.
Loop(T): The set of strings that cause T to loop forever.
Every Regular Language can be accepted by a Turing Machine.
Document Summary
Each cell may contain a symbol from a finite alphabet. Head scans one tape cell at a time. Program: for each state and symbol, specify the next state, next symbol and direction (one step left and one step right) ( (cid:449)e do(cid:374)"t sta(cid:374)d still) Computation step: at each step, apply the appropriate instruction. When we in state one, if we read a in the tape cell, we replace a with a and we move rright in the tape. And if we read a again in state three, we read and simply move to the right. A tape alphabet (could be larger than the input alphabet) Ea(cid:272)h state is (cid:374)u(cid:373)(cid:271)ered (cid:271)y a(cid:374) i(cid:374)teger 1. Note: a reject state is optional (if crash = reject) a finite set of rules letter letter, direction between states. Accept(t): the set of strings leading to the accept state.
