Church-Turing

Sat 03:30 PM

Prof. Calvin

CSCI 5100

Sketch

  • The Church-Turing Thesis
  • The 10th Hilbert Problem

The Church-Turing Thesis

The Thesis

The Church-Turing thesis concerns the concept of an effective or systematic or mechanical method, as used in logic, mathematics and computer science. “Effective” and its synonyms “systematic” and “mechanical” are terms of art in these disciplines: they do not carry their everyday meaning. A method, or procedure, \(M\), for achieving some desired result is called “effective” (or “systematic” or “mechanical”) just in case:

The Thesis

  1. \(M\) is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
  2. \(M\) will, if carried out without error, produce the desired result in a finite number of steps;

The Thesis

  1. \(M\) can (in practice or in principle) be carried out by a human being unaided by any machinery except paper and pencil;
  2. \(M\) demands no insight, intuition, or ingenuity, on the part of the human being carrying out the method.

Credit

Other Formulations

We shall use the expression “computable function” to mean a function calculable by a machine, and let “effectively calculable” refer to the intuitive idea without particular identification with any one of these definitions.

  • Turing, 1938

Other Formulations

No computational procedure will be considered as an algorithm unless it can be represented as a Turing Machine

  • Church, apocryphal

Other Formulations

It was stated … that “a function is effectively calculable if its values can be found by some purely mechanical process”. We may take this literally, understanding that by a purely mechanical process one which could be carried out by a machine. The development … leads to … an identification of computability with effective calculability.

  • Turing, 1938

Other Formulations

Every effectively calculable function is a computable function

  • Robin Gandy, 1980

The Lambda Calculus

Lambda Calculus

\[ \Lambda := \{ \lambda x.M \mid x \in V, M \in \Lambda \} \cup \{ x \mid x \in V \} \]

  • \(\lambda x.x\) represents the identity function.
  • Term \(x\) a variable in set of variables \(V\)
  • Term \(\lambda x. M\) an abstraction (definition)
  • Term \(M\space N\) an application (invocation/call)
  • It took Church 6 years and Turing’s help to get this logically consistent.

The 10th Hilbert Problem

Hilbert problems

  1. \(\exists A : |\mathbb{N}| \lt |A| \lt |\mathbb{R}|\)
  • Reduces to continuum hypothesis
  1. Consistency of Axioms of Mathematics
  • Provably impossible to prove via Gödel’s incompleteness
  1. …
  2. Determine Solvability of a Diophantine equation

Diophantine Equation

  • A polynomial. \[ \sum_{k=0}^n a_k x^k \]
  • Does it have a solution. \[ \sum_{k=0}^n a_k x^k = 0 \]

Diophantine Equation

  • For which all terms are integers \[ \forall k < n : a_k \in \mathbb{Z} : \sum_{k=0}^n a_k x^k = 0 : \]

Results

  • 1900
    • Problem proposed
    • Not defined
  • 1937
    • Church-Turing Thesis
  • 1970
    • Matiyasevich proves undecidability
  • Note: It is recognizable
    • Left to the student.

Notation convenience

  • Say we wish to express a polynomial
  • We note the polynomial is equivalent to a sequence of values
    • That is, an ordered collection
  • We note that numerical values are expressible in finite symbols.
    • For example, \(\{0, 1\}^n\)

We encode as strings

  • Take \(O\) some object, like a number, TM state, or anything else.
    • Could be a polynomial!
    • Could be a Turing Machine!
  • Denote \(\langle O \rangle\) the encoding of \(O\) into a string.
    • Denote \(\langle O_1,O_2,\ldots,O_K \rangle\) a list of objects in a string

Understanding check

  • Suppose two strings, \(x\) and \(y\)
  • Is \(xy = \langle x,y \rangle\)
  • Why or why not

Revist

Revist \(B\)

\[ B = \{a^kb^kc^k|k\in\mathbb{N}\} \]

  1. Check if \(w \in a^ib^jc^k\)
  2. Count each of a, b, c
  3. Accept on equal counts.

Rules of thumb

  • Ensure that any step is possible
  • Ensure that any step is finite
  • Ensure than any step halts
  • Ensure you can implement any step in e.g. Python

Outcomes

  • Three possible outcomes for \(M\) on \(w\)
    1. Accept \(w\) by halting in \(q_{acc}\)
    2. Reject \(w\) by halting in \(q_{rej}\)
    3. Reject \(w\) by looping

Recognize \(\oplus\) Decide

  • Turing-recognizable
    • \(\exists M : L(M) = \{w | M(w) \rightarrow q_{acc} \}\)
  • Turing-decidable
    • \(\exists M : L(M) = \{w | M(w) \rightarrow q_{acc} \land \forall w: M(w) \rightarrow \{q_{acc},q_{req}\}\}\)

Strings

  • \(\langle x,y \rangle\) is the string of list x,y
  • \(\langle x\rangle, \langle y \rangle\) is the list of strings of x and y

Denotation

\(M =\) “On input \(w\)

  1. Algorithm first step
  2. Algorithm next step

Stretch Break

  • Or work time on Hilbert[10], if fast
  • Home