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,Σ,Γ,q_{0},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
- q
_{0}∈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,Σ,Γ,q_{0},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,Σ,Γ,q_{0},B,F〉 a TM, the language L(M)⊆Σ* accepted by M is defined as
L(M)={u∈Σ* | q_{0}u⊢α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