2.2 Uncomputability; Goedel Theorem.

Universal and Complete Functions.

Notations: Let us choose a special mark and after its k-th occurrence, break any string x into Prefix_k(x) and Suffix_k(x). Let f⁺(x) be f(Prefix_k(x) x) and f^-(x) be f(Suffix_k(x)). We say u k-simulates f iff for some p=Prefix_k(p) and all s, u(ps)=f(s). The prefix can be intuitively viewed as a program which simulating function u applies to the suffix (input). We also consider a symmetric variant of relation ``k-simulate'' which makes some proofs easier. Namely, u k-intersects f iff u(ps)=f(ps) for some prefix_k p and all s. E.g., length preserving functions can intersect but not simulate one another.

We call universal for a class F, any u which k-simulates all functions in F for a fixed k. When F contains for each , universality is equivalent to [or implies, if only ] completeness: u k-intersects all . Indeed, u k-simulates f iff it k-intersects ; u 2k-intersects f if it k-simulates .

Problem: Describe explicitly a function complete for the class of all linear (e.g., 5x or 23x) functions.

A negation of a (partial or total) function f is the total predicate which yields 1 iff and yields 0 otherwise. Obviously, no closed under negation class of functions contains a complete one. So, there is no universal function in the class of all (computable or not) predicates. This is the well known Cantor Theorem that the set of all sets of strings (as well as the sets of all partial functions, reals etc.) is not countable.

Goedel Theorem.

There is no complete function among the total computable (recursive) ones, as this class is closed under negation. So the universal in R function u (and ) has no total computable extensions.

Formal proof systems are computable functions which check if P is an acceptable proof and output the proven statement. means for some P. A is rich iff it allows computable translations s_x of statements ``,'' provable whenever true, and refutable ( ¬s _x provable), whenever . A is consistent iff at most one of any such pair s_x, ¬s_x) is provable, and complete iff at least one of them always (even when diverges) is. A rich consistent and complete formal system cannot exist, since it would provide an obvious total extension of (by exhaustive search for P to prove or refute s_x). This is the famous Goedel's Theorem which was one of the shocking surprises of the science of our century. (Here A is an extension of the formal Peano Arithmetic; we skip the details of its formalization and proof of richness.)

Recursive Functions.

Another byproduct is that the Halting (of ) Problem would yield a total extension of u and, thus, is not computable. This is the source of many other uncomputability results. Another source is an elegant Fixed Point Theorem by S. Kleene: any total computable transformation A of programs (prefixes) maps some program into an equivalent one. Indeed, the complete/universal u(ps) intersects computable u(A(p)s). This implies (exercise), e.g., that the only computable invariant (i.e. the same on programs computing the same functions) property of programs is constant (Rice-Uspenskii).

Computable (partial and total) functions are also called recursive (due to an alternative definition). Their ranges (and, equivalently, domains) are called (recursively) enumerable or r.e. sets. An r.e. set with an r.e. complement is called recursive (as is its yes/no characteristic function) or decidable. A function is recursive iff its graph is r.e. An r.e. graph of a total function is recursive. Each infinite r.e. set is the range of a 1-to-1 total recursive function (``enumerating'' it, hence the name r.e.).

We can reduce membership problem of a set A to the one of a set B by finding a recursive function f s.t. . Then A is called m- (or many-to-1-) reducible to B. A more complex Turing reduction is given by an algorithm which, starting from input x, interacts with B by generating strings s and receiving answers to questions. Eventually it stops and tells if . R.e. sets (like Halting Problem) to which all r.e. sets can be m-reduced are called r.e.-complete. One can show a set r.e.-complete (and, thus, undecidable) by reducing the Halting Problem to it. So Ju.Matijasevich proved r.e.-completeness of Diophantine Equations Problem: given a multivariate polynomial of degree 4 with integer coefficients, find if it has integer roots. The above (and related) concepts and facts are broadly used in Theory of Algorithms and should be learned from any standard text, e.g., [Rogers 67].