Chapter 7

Apuntes

Chapter 7 The Turing machine 7.1 Formal definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.2 Computability, decidability, enumerability . . . . . . . . . . . . . . 119 105 7.1 Formal definition Definition 7.1.1. Turing Machine (TM) A TM is a 5-tuple ( K, q 0 , Σ , γ, δ ) , where K is a non-empty, finite set of states, q 0 ∈ K is the initial state, Σ is an alphabet, and if Σ R = { a 0 , l, r, h } are reserved words, then Σ ∩ Σ R = ∅ , γ : K × Σ S → Σ I is the instruction function, δ : K × Σ S → K is the transition function where Σ S = Σ ∪ { a 0 } , Σ I = Σ ∪ Σ R and a 0 is often referred as blank symbol. Remark. The instructions set is Σ I , consequently the TM is able to: — write a symbol of Σ or a blank symbol ( a 0 ) in a cell, — move its head to the neighbouring left cell ( l ) or right cell ( r ), — halt the computation ( h ). If a TM is in a state q ∈ K and reads a ∈ Σ , it will execute the instruction γ ( q, a ) ∈ Σ I and will transit to the state δ ( q, a ) ∈ K . 106 Definition 7.1.2. Table of a TM A TM can be represented as a matrix of four columns...