Turing Machines

Now we need to define the Turing machine.

A Turing machine is a septuple where M =(Q, Σ, Γ, δ, q0, qa, qr) where Q, Σ, Γ are all finite sets and

Q is the set of states
Σ is the input alphabet (not containing a blank character)
Γ is the tape alphabet (it mus contain all of Σ and the blank character, may also have a shadow alphabet)
δ is the transistion function (this is usually shown in the form of a state diagram)
q0 is the start state
qa is the accpet state
qr is the reject state

Most of this is in the textbook, so I'll just write up the definitions.

Definition: A Turing Machine M accepts w (a string) if there exists a sequence c1,c2,ck such that
1. c1 is the start configuration with input w
2. ci+1 is obtained from ci by δ
3. ck is an acceptin configuration

Definition: the Language of M is L(M) = {w is a member of Σ*|M accepts w}

Definition: a Language L is Turing Recognizable if there is a turing machine fuch that L = L(M)

Definition: a Language is Turing Decidable if there is a decider (a decider halts on all input) M such that L = L(M)

Note: Every decidable language is recognizable but not conversely

Note: Every finite language is decidable