\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].