\newpage \subsection {Uncomputability; Goedel Theorem.}

\subsubsection* {Universal and Complete Functions.}\vspace{-2pt}

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$-{\em
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$-{\em
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 {\em universal} for a class $F$, any $u$ which $k$-simulates all
functions in $F$ for a fixed $k$. When $F$ contains $f^-,f^+$ for each $f\in
F$, universality is equivalent to [or implies, if only $f^+\in F$] {\em
completeness}: $u$ $k$-intersects all $f\in F$. Indeed, $u$ $k$-simulates $f$
iff it $k$-intersects $f^-$; $u$ $2k$-intersects $f$ if it $k$-simulates $f^+$.

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

A {\em negation} of a (partial or total) function $f$ is the total predicate
$\neg f$ which yields $1$ iff $f(x) = 0$ 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.

\subsubsection* {Goedel Theorem.}\vspace{-1pt}

There is no complete function among the {\em total} computable (recursive)
ones, as this class is closed under negation. So the universal in $R$ function
$u$ (and $u_2=(u\bmod2)$) has no total computable extensions.

Formal proof systems are computable functions $A(P)$ which check if $P$ is an
acceptable proof and output the proven statement. $\vdash s$ means $s= A(P)$
for some $P$. $A$ is {\em rich} iff it allows computable translations $s_x$ of
statements ``$u_2(x)=0$,'' provable whenever true, and refutable ($\vdash\neg
s_x$), whenever $u_2(x)=1$. $A$ is {\em consistent} iff {\bf at most} one of
any such pair $s_x,\neg s_x$ is provable, and {\em complete} iff {\bf at least}
one of them always (even when $u(x)$ diverges) is. A rich consistent and
complete formal system cannot exist, since it would provide an obvious total
extension $u_A$ of $u_2$ (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.)\footnote
 {A closer look at this proof reveals the second famous Goedel theorem: the
consistency itself is an example of unprovable $\neg s_x$. Consistency $C$ of
$A$ is expressible in $A$ as divergence of the search for contradiction. $u_2$
intersects $1-u_A$ for some prefix $a$. $C$ implies that $u_A$ extends $u_2$,
and, thus, $u_2(a),u_A(a)$ both diverge. So, $C\Rightarrow\neg s_a$. This proof
can be formalized in $A$ which yields $\vdash C\Rightarrow\ \vdash\neg s_a$.
But $\vdash\neg s_a$ implies $u_A(a)=1$, so $C$, $\vdash C$ are incompatible.}

\paragraph {Recursive Functions.\label{rec}}
Another byproduct is that the Halting (of $u(x)$) 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 {\em
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 {\em recursive} (due
to an alternative definition). Their ranges (and, equivalently, domains) are
called (recursively) {\em enumerable} or {\em r.e.} sets. An r.e.\ set with an
r.e. complement is called recursive (as is its yes/no characteristic function)
or {\em 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. $x\in A \iff f(x)\in B$. Then $A$ is
called {\em m-} (or {\em many-to-1-}) {\em reducible} to $B$. A more complex
{\em Turing} reduction is given by an algorithm which, starting from input $x$,
interacts with $B$ by generating strings $s$ and receiving answers to $s\in?B$
questions. Eventually it stops and tells if $x\in A$. 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].