Turing Machine Components:
A Turing machine is a 7-tuple:
Q: A finite set of states.
Sigma: Input alphabet.
Gama: Tape alphabet.
Delta: Transition function.
Qs: Starting state.
Qaccept: Accepting state.
Qreject: Rejecting state.
Transition Function (Delta):
D: Q * Gama -> Q * Gama * {L, R}: This denotes how the Turing machine moves from one state to another, reading and writing symbols, and moving left (L) or right (R) on the tape.
Example (Exp):
5 + 3, 11111b111bbbbbb: Simulating the addition of 5 and 3. Here, ‘b’ acts as a separator.
Qs, 1, 1, qs, R: In the starting state, read 1 and stay in the starting state, moving right.
Qs, b, 1, qe, R: On reading ‘b’, change state to qe and move right.
Qe, 1, 1, qe, R: In state qe, read 1 and stay in qe, moving right.
Qe, b, b, qb, L: On reading ‘b’, change state to qb and move left.
Qb, q, b, Qacc, L: Change state to Qacc and move left.
Regular Expression Example:
{w | w contains twice as many 0s as 1s}: The language contains strings where the number of 0s is twice the number of 1s. For example, 0001001000110.
Steps:
From the left of the input, strike out the first 0. If only x then accept, if only 1 then reject.
Strike out another 0. If only x or 1 then reject.
From the left of the input, strike out the first 1 you find. If only x or 0, then reject.
Repeat the steps.
Definition of Configuration:
Configuration: The total information of where a TM (Turing Machine) is at any point in time. Also called a “Core Dump” or “Snapshot”.
1) What’s on the tape: The current contents of the tape.
2) Where is the Eye of the TM pointing: The current position of the read/write head.
3) What state is the TM in: The current state of the Turing Machine.
How Configuration Changes:
U, V belong to Gama*: These are strings of symbols from the tape alphabet.
a, b, c belong to Gama: These are individual symbols from the tape alphabet.
1) UaQibV yields UqjacV if d(qi, b) = qj, c, L: Transition when the machine moves left.
2) UaqibV yields UacqiV if d(qi, b) = qj, c, R: Transition when the machine moves right.
Starting and Halting Configurations:
A start configuration: Q0w (initial state and input string w).
Halting configurations:
Accepting configuration: UQaccV (tape contents and accepting state).
Rejecting configuration: UQrejectV (tape contents and rejecting state).
Acceptance:
A TM M accepts input w belong to Sigma if there is a sequence of configurations*:
C1, C2, C3, …, Ck such that:
C1 is a start configuration.
Ci yields Ci+1 for 1 ≤ i < k.
Ck is an accepting configuration.
[/box05]
