Kleeneliness is next to Gödeliness
Deterministic Turing Machines (DTM)
A Turing Machine (henceforth abbreviated to TM) is a t-upa of 6 elements 〈Q,Σ,Γ,q0,B,F〉 where
- Q set of
states(finite) - Σ the alphabet of
input - Γ alphabet of the
tapeΣ⊆Γ - δ:Q⨯Γ→Q⨯Γ⨯{L,R} partial function called transition function
- q0∈Q initial state
- B∈(Γ\Σ)
special symbol(Blank) - F⊆Q set of end states`
δ(q,X)=〈q’,Y,D〉 where q’ is next state, Y overrides X and D∈{L,R}
a tabular representation can be given by means of a transition matrix equivalent to the 5-uple list 〈q,X,q’,Y,D〉
the instantaneous description (or configuration) of a TM via the
triple ρ=αqβ where
- α∈Γ* symbols to the left of the head
- β∈Γ* symbols to the right of the head
- q head status
if β≠ε the
Single step of execution: Let M=〈Q,Σ,Γ,q0,B,F〉 a TM defines the relation ρ⊢Mρ’ induced by the transition function δ defined for cases as follows. Let α,β∈Γ* and x,y,z∈Γ we have
- αqXβ⊢M αYq’β se δ(q,X)=〈q’,Y,R〉
- αq⊢M αYq’ se δ(q,B)=〈q’,Y,R〉
- αZqXβ⊢M αq’ZYβ se δ(q,X)=〈q’,Y,L〉
- qXβ ⊢M q’BYβ se δ(q,X)=〈q’,Y,L〉
The Reachability Relationship ⊢M* between configurations is defined as the reflexive and transitive closure of the relationship ⊢M i.e. ρ⊢M*q’ ⇔ there is a sequence ρ0,…,ρn≥0 t.c. ρi⊢Mρi-1 for i∈[1,n-1] , ρ0=ρi,ρn=ρ’
Language accepted by a TM
Let M=〈Q,Σ,Γ,q0,B,F〉 a TM, the language L(M)⊆Σ* accepted by M is defined as L(M)={u∈Σ* | q0u⊢αqβ,q∈F} on non-accepted strings the computation may not terminate. Alternative without final states is where the string is accepted ⇔ the corresponding computation terminates.
Recursively enumerable languages (r.e.)
A language is r.e. if it is accepted by a TM, on some string it may happen (if not in the language) that the TM does not terminate.
Recursive languages
A language is recursive if it is accepted by a TM that terminates on every input