Chapter 4: Turing machines Redirected from Study/Bachelor/Year 2/Theoretical Computer Science/Summary/Chapter 4: Turing machines

Definition 4.1.1:

A Turing machine is a quintuple (K, ∑, δ, s, H) where:

• K is a finite set of states
• ∑ is an alphabet, containing the blank symbol ⊔ and the left end symbol ⊳, but notcontaining the symbol ← and →
• s ∊ K is the initial state.
• H ⊆ K is the set of waiting states
• δ the transition function is a function from (K-H) x ∑ to K x (∑ ∪ { ←, →}) such that

1. for all q ∊ K-H, if δ(q, ⊳) = (p,b) then b = →
2. for all q ∊ K-H and a ∊ ∑ if δ(q, a) = (p,b) then b ≠ ⊳

Definition 4.1.2:

a configuration of a Turing machine M = (K, ∑, δ, s, H) is a member of K x ⊳ ∑* x (∑* (∑-{⊔}) ∪ {e})

That is, all configurations are assumed to start with the left end symbol, and never end with a blank - unless the blank is currently scanned. A configuration whose state component is ⊳ in H will be called a halted configuration.

Defenition 4.1.3:

let M = (K, ∑, δ, s, H) be a Turing machine and consider two configurations of M (q₁, w₁a₁u₁) and (q₂, w₂a₂u₂),where a₁, a₂ ∊ ∑. Then

(q₁, w₁a₁u₁) ⊢_M (q₂, w₂a₂u₂)

if and only if, for some b ∊ ∑ ∪ { ←, →}, δ(q₁, a₁) = (q₂, b), and either

1. b ∊ ∑, w₁ = w₂, u₁ = u₂ and a₂ = b, or
2. b = ←, w₁ = w₂a₂ and either
   
   1. u₂ = a₁u₁, if a₁ ≠ ⊔ or u₁ ≠ e, or
   2. u₂ = e, if a₁ = ⊔ and u₁ = e; or
3. b = →, w₂ = w₁a₁, and either
   
   1. u₁ = a₂u₂, or
   2. u₁ = u₂ = e, and a₂ = ⊔.

Definition 4.1.4:

For any Turing machine M, let ⊢*_M be the reflexive, transitive closure of ⊢_M, we say that configuration C₁ yields configuration C₂ if C₁ ⊢*_M C₂. A computation by M is a sequence of configurations C₀,C₁,...,C_n for some n⪖0 such that

C₀⊢_MC₁⊢_MC₂⊢_M...⊢_MC_n

We say that the computation is of length n or that it has n steps, and we write C₀⊢ⁿ_MCn

If a ∊ ∑, then the a-writign machine will be denoted simply as a. The head moving machines M← and M→ will be abrevated as L and R

Definition 4.2.1:

Let M = (K, ∑, δ, s, H) be a Turing machine such that H = {y, n} consists of two distinguished halting states ( y and n for yes and no). Any halting state whose state component is y is called an accepting configuration while a halting configuration whose state component is n is calles a rejecting configuration Let ∑₀ ⊆ ∑ - {⊔, ⊳} be an alphabet, calles the input alphabet of M; by fixing ∑₀ to be a subset of  ∑ - {⊔, ⊳}, we allow out Turing machines to use extra symbols during their computation, besides those appearing in their input. We say that m decides a language L ⊆ ∑₀* if for any string w ∊ ∑₀* the following is true: if w ∊ L then M accepts w; and if ∉ L then M rejects w. Finally call a language : recursive if there is a Turing machine that decides it.

That is, a Turing machine decides a language L if, when started with input w, it always halts, and does so in a halt state that is correct response to the input: y if w ∊ L, n if  w ∉ L. Notice that no garantuees are given about what happens if the input to the machine contains blanks or the left end symbol.

A Turing machine, even if it has only two half states y and n, always has the option of evading an answer (yes or no) by falling to halt.

Definition 4.2.2:

Let M = (K, ∑, δ, s, {h}) be a Turing machine, let ∑₀ ⊆ ∑ - {⊔, ⊳} be an alphabet, and let w ∊ ∑₀*. Suppose that M halts on input w, and that (s,⊳⊔w) ⊢*_M (h,⊳⊔y) for some y ∊ ∑₀*. Then u is calles the output of M on input w, and is denoted M(w). Notice that M(w) is defined only if M halts on input w, and in fact does so at a configuration of the form (h,⊳⊔y) with y ∊ ∑₀*. Now let f be any function from ∑₀* to ∑₀*. We say that M computes function f if for all w ∊ ∑₀*, M(w) = f(w). That is, for all w ∊ ∑₀* M eventually halts on input w, and when it does halt, its tape contains the string ⊳⊔f(w). A function is calles recursive if there is a Turing machine M that computes f.

Definition 4.2.3:

Let M = (K, ∑, δ, s, {h}) be a Turing machine such that 0, 1; ∊ ∑ and let f be any function from ^k to for some k ⪖ 1. We say that M computes function f if for all w₁,..., w_k ∊ 0 ∪ 1 {0, 1} * (that is for any k strings that are binary encodings of integers), num (M(w₁,..., w_k)) = f(num(w₁),..., num(w_k)). That is if M is started with the binary representations of the integers n₁,...,n_k as input, then it eventually halts, and when it does halt, its tape contains a string that represents numbers f(n₁,...,n_k) - the value of the function. A function f: ^k ↦ is called recursive if there is a Turing machine M that computes f

If a Turing machine decides a language or computes a function, it can be reasonably thought of as an algorithm that performs correctly and reliably some computational task. We next introduce a third subtler way in which a Turing machine can define a language:

Definition 4.2.4:

Let M = (K, ∑, δ, s, H) be a Turing machine let ∑₀ ⊆ ∑ - {⊔, ⊳} be an alphabet, and let L ⊆ ∑₀* be a language. We say that M semidecides L if for any string w ∊ ∑₀* the following is true w ∊ L if and only if M halts on input w. A language L is recursively enumerable if and only if there is a Turing machine M that semidecides L.

Extending the "functional" notation of Turing machines that we introduced previously (which allows us to write equations such as M(w) = u), we shall write M(w) = ⤤ if M fails to halt on input w. In this notation we can restate the definition of semidecision of a language L ⊆ ∑₀ by Turing machine M as follows: For all w ∊ ∑₀* M(w) = ⤤ if and only if w ∉ L.

A Turing machine that semidecides a language L cannot be usefully employed for telling wheter a string w is in L, because if w ∉ L, then we will never know when we have waited enough for an answer. Turing machines that semidecide languages are no algorithms

Any recursive language is also recursively enumerable. All it takes to construct another Turing machine that semidecides instead of decides, the language is to make the rejecting state n a nonhalting state, from which the machine is guaranteed to never halt.

Theorem 4.2.1:

If a language is recursive, then it is recursively enumerable.

There are recursively enumerable languages that are not recursive.

Theorem 4.2.2:

If L is a recursive language, then its complement L is also recursive

Definition 4.5.1:

Let M = (K, ∑, ∆, s, H) be a nondetermenistic Turing machine. We say that M accepts an input w ∊ (∑ - {⊔, ⊳})* if (s, ⊳⊔w) ⊢*_M (h, uav) for some h ∊ H and a ∊ ∑,u,v ∊ ∑*. Notice that a nondetermenistic machine accepts an input even though it may have many nonhalting computations on this input - as long as at least one halting computation exists. We say that M semidecides a language L ⊆ (∑ - {⊔, ⊳})* if the following holds for all w ∊ (∑ - {⊔, ⊳})* w ∊L if and only if M accepts w.

Definition 4.5.2:

Let M = (K, ∑, ∆, s, {y,n}) be a nondetermenistic Turing machine. We say that M decides a language L ⊆ (∑ - {⊳, ⊔})* if the following two conditions hold for all w ∊ (∑ - {⊔, ⊳})*:

1. There is a natural number , dependein on M and w, such that there us no configuration C satisfying (s, ⊳⊔w) ⊢ⁿ_MC
2. w ∊ L if and only if (s, ⊳⊔w) ⊢*_M (y, uav) for some u, v ∊ ∑*, a ∊ ∑

Finally, we say that M computes a function f:(∑ - {⊔, ⊳})* ↦ (∑ - {⊔, ⊳})* if the following two conditions fold for all w ∊ (∑ - {⊔, ⊳})* :

1. There is an depending on M and w, such that there is no configuration C satisfying (s, ⊳⊔w) ⊢ⁿ_MC.
2. (s, ⊳⊔w) ⊢*_M (h, uaw if and only if ua = ⊳⊔ and v = f(w)

Theorem 4.5.1:

If a nondetermenistic Turing machine M semidecides or decides a language, or computes a function, then there is a standard Turing machine M' semideciding or deciding the same language, or computing the same function.

Defenition 4.7.1:

We start by defining certian extremely simple functions from ^k to , for various values of k ≥ 0 (a o-ary function is , of course, a constant, and it has nothing on which to depend). The basic functions are the following:

1. For any k ≥ 0, the k-ary zero function is defined as zero_k(n₁,...,n_k) = 0 for all n₁,...,n_k ∊
2. For any k ≥ j ≥ 0, the j^th k-ary identity function is simply the function id_k,j(n₁,...,n_k) = n_j for all n₁,...,n_k ∊
3. The successor function is defined as succ(n) = n+1 for all n ∊

Next we introduce two simple ways of combining functions to get slightly more complex functions.

1. Let k,l ≥ 0 let g: ^k ↦ be a k-ary function, and let n₁,...,n_k be l-ary functions. Then the composition of g with h₁,...,h_k is the l-ary function defined as
   f(n₁,...,n_l) = g(h₁(n₁,...,n_l),...,h_k(n₁,...,n_l))
2. Let k ≥ 0 let g be a k-ary function, and let h be a (k+2)-ary function. Then the function defined recursively by g and h is the (k+1)-ary function defined as
   fo) = g(n₁,...,n_k)
   f(n₁,...,n_k,m+1) = h(n₁,...,n_k,m,f(n₁,...,n_k,m))
   for all n₁,...,n_k,m ∊
   The primitive recursive functions are all basic functions, and all functions that can be obtained by them by any number of successive applications of composition and recursive definition

Definition 4.7.2:

Let g be a (k+1)-ary function, for some k ≥ 0. The minimalization of g is the k-ary function defined as follows:

f(n₁,...,n_k)

{the least m such that g (n₁,...,n_k,m) = 1, if such an m exists;

0 otherwise

*** the f(n₁,...,n_k) should be in front of the bracket***

We shal denote the minimalization of a function g is always well-defined, there is no abvious method for computing it - even if we know how to compute g. The obvious method

m:=0
while g(n₁,...,n_k,m) ≠ 1 do m:= m+1;
output m

is not an algorithm, because it may fail to terminate. Let us then call a function g minimalizable if the above method always terminates. That is a (k+1)-ary function g is minimalizable if it has the following property. For every n₁,...,n_k ∊ , there is an m ∊ such that g (n₁,...,n_k,m) = 1.

Finally, call a function μ-recursive if it can be obtained from the basic functions by the operations of composition: recursive defenition, and minimalization of minimalizable functions.

Theorem 4.7.1: A function f: ^k ↦ is μ-recursive if and only if it is recursive (that is, computable by a Turing machine)