Massimo Caliman
by Massimo Caliman
1 min read

Categories

  • Programming

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. ρiMρi-1 for i∈[1,n-1] , ρ0in=ρ’

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