notas.itmens
Introduction
Terminological Issue#
We shall always use total for total computable functions. For partial computable functions we shall also use the term computable function.
The class of all partial functions from \(\mathbb{N}^n\) to \(\mathbb{N}\) will be denoted by \(\mathcal{F}_n\).
General Overview#
Various models of computation can be proved to be equivalent in terms of computability. By the Church-Turing thesis, these models of computation, exemplified by Turing machines, are all that can be said to be computational procedures. The functions these models of computation compute are called partial computable functions. Also called partial recursive functions.
Partial recursive functions are built with the primitive recursive functions together with the unbounded \(\mu\)-operator. A total partial computable function is called recursive/computable. A set is said to be computable if the characteristic function of the set if computable.
It turns out that computable functions are representable in Peano Arithmetic; in fact these are exactly those functions that can be fully described in a first order theory.
By Godel coding it is possible to enumerate partial computable functions. Let \(\phi_e\) be this enumeration: \(e\) is a number and \(\phi_e\) is the \(e\)-th partial computable function of arity 1 (this doesn't rule out the possibility that for \(e_1\neq e_2\) we have \(\phi_{e_1} = \phi_{e_2}\); their corresponding Turing machine may be different but these intensional details are collapsed in computability theory).
In fact,
- The enumeration theorem states that \(\phi_z(x)\) is a partial computable function of \(x\) and \(z\).
- Let \(f\) be a given partial computable function, the padding lemma: there exists infinitely many indices \(i\) s.t. \(\phi_i = f\).
- Let \(f(x,y)\) be partial computable, then the s-m-n theorem: there is a computable \(g\) for which \(f(x,y) = \phi_{g(x)}(y)\).
The Universal Turing Machine Theorem is kind of the reverse of the s-m-n theorem: there is a Turing machine \(U\) s.t. given input \((e,x)\) it simulates the \(e\)-th Turing machine with input \(x\), i.e. \(\phi_U^{(2)}(e,x) = \phi_e(x)\). This is directly by Church-Turing thesis.
There are several fixed point/recursion theorems of primal importance.
- The Second Recursion Theorem(s), both of the following two are called “the second recursion theorem”.
- The (Kleene/Rogers) Fixed Point Theorem: given a total computable function \(f\), there is a \(k\in\mathbb{N}\) for which \(\phi_{f(k)} = \phi_{k}\).
- The Second Recursion Theorem: given a partial computable function \(f(x,y)\) there is an index \(p\) s.t. \(\phi_p(y) = Q(p,y)\) (use both the first recursion theorem and the s-m-n theorem)
- The First Recursion Theorem: For a recursive operator \(\Phi:\mathcal{F}_m\to\mathcal{F}_m\) there is a partial computable function \(f_\Phi\) that is the least fixed point of \(\Phi\): \(\Phi(f_\Phi) = f_\Phi\) and if \(\Phi(g)=g\), \(f_\Phi\subseteq g\). (An operator is recursive if there is a computable function \(\phi(z,x)\) such that \(\Phi(f)(x)=y\) iff there is finite function \(\phi\subseteq f\) s.t. \(\phi([\theta],x)=y\) for all \(f\); here \([\theta]\) is the code for \(\theta\) and finite function means the domain is finite)
and from the second recursion theorem, Rice's theorem, which states that all non-trivial semantic properties of programs are undecidable: Let \(P\) be a subset of \(\mathbb{N}\) which is neither \(\empty\) nor \(\mathbb{N}\) itself, and that for \(m,n\in\mathbb{N}\) we have that if \(\phi_m = \phi_n\) then \(m\in P \leftrightarrow n\in P\), then \(P\) is undecidable.
If Turing machiens can obtain information from the real world, we get oracle Turing machines. Then we have a whole theory based on relativised Church-Turing thesis, and the theory of Turing degrees.