Turing Machine: the accepted formalization for the concept of an algorithm (effective procedure).

TM M = (Q, S, T, d, q₀, B, F)

where:

Q = finite set of states

S = input alphabet (S T T) for example {0, 1}

T = allowable tape symbols for example {0, 1, B}

d: QxT Y QxTx {left, right} where all the work is done

q₀ = initial or start state

B = blank symbol where B T T - S

F = finite set of final states

A move consists of:

1) calculating a new state

2) replacing the current symbol on the tape under the r/w head

3) moving the r/w head either left or right one position

The language accepted by a TM M is L(M) = {x X S* | q₀x # a₁qa₂ where q X F}.

If L = L(M) for some TM M and x X L then M must terminate on x (enter a final state).

The class of languages accepted by TMs is the set of recursively enumerable (re) languages:

i.e., (if x X L then M halts otherwise M might halt or it might run forever).

A language L that is accepted by a TM M that halts on all inputs is known as a recursive set (recursive language).

The recursive languages are considered decidable while the recursively enumerable languages are considered undecidable.

Halting Problem: does there exist an algorithm which can determine whether TM M eventually halts on input w?

Input: <M, w>

Process: run M on w

Output: if M halts on w, then we're done

If not, what?