Is the Church Turing thesis a theorem

Church's thesis. The set of Turing-computable functions is exactly the set of functions that can be computed in the intuitive sense.

Transcript

1 1 Church's thesis The set of Turing-computable functions is exactly the set of functions that can be computed in the intuitive sense.

2 variants of Turing machines 2 variants of Turing machines Turing machines with several belts Turing machines with one-sided limited belt Turing machines with several reading heads Turing machines with multi-dimensional working belt Theorem Turing machines are just as powerful as their variants.

3 Turing machines with several belts 3 Turing machines with several belts Turing machine with k belts TM = (S, I, A, d, s 0, F) d (s, a 1, ..., ak) SA k {l, r, n} k for all s S and all (a 1, ..., ak) A k, all other components as for (single-cover) Turing machines.

4 Turing machines with several bands 4 configurations Configuration: u 1 sv 1, ..., uk sv k with s S, uj, vj A (j = 1, ..., k) Initial configuration: λs 0 w, s 0 ,. .., s 0 with w I

5 Turing machines with several bands 5 subsequent configuration If (s, b 1, ..., bk, x 1, ..., xk) d (s, a 1, ..., ak): u 1 sa 1 v 1, ..., uk sa kvku 1s v 1, ..., u ks vk, where ujsvj is obtained from u jsa jvj as follows: 1. Overwrite aj by b j. 2. Replace s with s. 3. Shift s according to x j.

6 Turing machines with several bands 6 Recognized language Let T M = (S, I, A, d, s 0, F) be a Turing machine with k bands. Then L (T M) is the language recognized by T M with L (T M) = {w I s 0 w, s 0, ..., s 0 u 1 sv 1, ..., u k sv k, s F}

7 Turing machines with several bands 7 Equivalence between multi-band Turing machines and Turing machines Theorem Multi-band Turing machines recognize the same languages ​​as (single-band) Turing machines.

8 Turing machines with several bands 8 Proof sketch: Let T M (k) be a Turing machine with k> 1 bands. Simulate T M (k) as follows: 1. Write all k input words next to each other on the working tape so that they are separated by special symbols and the position of the reading heads is coded using special symbols. 2. Carry out the actions of T M (k) one after the other at the marked positions. (It may be necessary to create space for this by moving the contents of the tape.)

9 Equivalence between deterministic and nondeterministic Turing machines 9 Equivalence between deterministic and nondeterministic Turing machines Deterministic Turing machine TM is deterministic if d (s, a) contains at most one element for every s S and a A. Theorem Nondeterministic Turing machines recognize the same languages ​​as deterministic Turing machines.

10 Equivalence between deterministic and nondeterministic Turing machines 10 Proof sketch: Let T M = (S, I, A, d, s 0, F) be a nondeterministic Turing machine. Let k = max {d (s, a) s S, a A}. Simulate T M by a deterministic Turing machine with 3 bands: 1. Write the input of T M on the first band. 2. On volume 2, gradually generate all the words over {1, ..., k}. 3. For each word u on volume 2, copy the entry on volume 3 and simulate T M using the sequence of numbers in u.

11 Turing machines and type 0 languages ​​11 Turing machines and type 0 languages ​​Theorem The languages ​​recognized by Turing machines are exactly the type 0 languages.

12 Turing machines and type 0 languages ​​12 Translation of Chomsky grammars in Turing machines Let G = (N, T, P, S) be a Chomsky grammar. Then T M (G) works as follows: 1. Choose a rule u :: = v P. 2. Replace any occurrence of v in the current volume w with u, if v occurs in w. (If u v parts of w have to be shifted.) 3. If S is the current tape content, go to a final state; otherwise go to 1.

13 Turing machines and type 0 languages ​​13 Theorem Correctness of the translation L (G) = L (T M (G))

14 Turing machines and type 0 languages ​​14 Translation of Turing machines into type 0 grammars Let T M = (S, I, A, d, s 0, F) be a Turing machine. Then G (T M) = (N, I, P, S) contains the following rules: 1. Rules that generate words of the form from S. $ s 0 w # w with w I, $, # / A 2. Rules that convert $ s 0 w # w into $ usv # w, if s 0 w etc. 3. Rules that convert $ usv # w to w if s F.

15 Turing machines and type 0 languages ​​15 Definition of the rules of G (TM) 1. Rules for S $ s 0 w # w: (see exercise) 2. Rules for $ s 0 w # w $ usv # w: If (b, s, l) d (s, a): csa :: = s cb for all c A $ sa :: = $ sb further cases analogously. 3. Rules for $ usv # w w: s :: = L, Lc :: = L, cl :: = L, $ L # :: = λ (with s F, c A)

16 Turing machines and type 0 languages ​​16 Theorem Correctness of the translation L (T M) = L (G (T M))

17 Linearly constrained Turing machine 17 Linearly constrained Turing machine Only uses the space in which the input is located. Recognizes border fields through special symbols. Marking of the left border field immediately after the start. Input alphabet: I Î with Î = {ˆx x I}. Start configurations have the form: s 0 wˆx with w I and ˆx Î. λ cannot be recognized.

18 Linearly Bounded Turing Machine 18 Definition of Linearly Bounded Turing Machine A Turing machine TM = (S, I, A, d, s 0, F) is called linearly bounded if for all w I, u, v A, s S: s 0 w etc. = w = uv.

19 Linearly restricted Turing machine 19 Recognized language The language recognized by a linearly restricted Turing machine TM = (S, I, A, d, s 0, F) is defined by {wx w I, x I, s 0 wˆx usv, s F} . Theorem The languages ​​recognized by linearly bounded Turing machines are precisely the monotonous languages.

20 Linearly Bounded Turing Machine 20 Open Problem Can deterministic linearly bounded Turing machines recognize the same languages ​​as nondeterministic linearly bounded Turing machines?

21 Unsolvability of the word problem for type 0 languages ​​21 Unsolvability of the word problem for type 0 languages ​​Theorem The word problem for type 0 languages ​​cannot be calculated (e.g. by a CE-S specification, a Turing machine or a WHILE- Program).

22 Proof of unsolvability by means of reduction 22 Proof of unsolvability by means of reduction Reduction Let dp i: A i BOOL (i = 1, 2) decision problems. dp 1 can be reduced to dp 2 if there is a computable function red: A 1 A 2 such that dp 1 (w) = T dp 2 (red (w)) = T for all w A 1.

23 Proof of unsolvability by means of reduction 23 Proof of unsolvability by means of reduction Theorem dp is not computable. Proof Choose another decision problem dp 0 whose unsolvability is already known. Reduce dp 0 to dp.