116b- Lecture 15 « Computability Theory

116b- Lecture 15

By andrescaicedo

We proved that the class of functions computable by means of Turing machines coincides with the class of recursive functions. Together with the characterization of the recursive functions as those admitting $\Sigma_1$ graphs, one can see this result as empirical evidence for Church’s thesis, the claim that the intitive notion of “algorithymically computable” is correctly formalized in the notion of recursive. An immediate consequence of this result is the existence of universal Turing machines.

We defined machines with oracles and stated the corresponding result: Given an oracle $X\subseteq{\mathbb N}$ , a function $f: \mbox{dom}(f)\subseteq{\mathbb N}^k\to{\mathbb N}$ is computable by a Turing machine with oracle $X$ iff $f$ is recursive in $X$ (meaning that it is built up from $\chi_X$ and the basic functions by composition, recursion and minimalization) iff $f$ has a graph $\Sigma_1$ definable in the structure $({\mathbb N},+,\times,0,1,<,X)$ . We then defined the partial order $A\le_T B$ among subsets of ${\mathbb N}$ which holds iff $\chi_A$ is recursive in $B$ .

This entry was posted on March 4, 2008 at 9:37 am and is filed under 116b. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Computability Theory

116b- Lecture 15

Leave a Reply