4
$\begingroup$

The problem that I'm working on is to prove that $ Ext=\{ x \ | \ \varphi_x \text{is extendible to a total computable function}\} $ is not equal to $\omega$. Here $\varphi_x$ is the $x$-th partial computable function. I'm having problem understanding what $Ext$ is. Does it mean that if $x \in Ext$ then $x$ is in some $W_i \subset W_j$ where $W_j$ is computable? But doesn't that mean $W_i$ is also computable?

More on the context of this problem, this is part 2 of a problem from Soare's book. Part 1 is to prove that there exists computably inseparable r.e. set, which I did.

  • 1
    Concerning your comment: that's due to the software, [see here](http://meta.math.stackexchange.com/questions/2513/are-users-here-not-dear) for an explanation and links.2011-09-19

3 Answers 3

7

The proof that $\text{Ext} \neq \omega$ is given below. However, to address you qustion, $\text{Ext}$ is just the set of $i$ such that $\varphi_i(x)$, which may not be total can be extending to a total computable function $\varphi_j$ such that for all $x$ such that $\varphi_i(x)\downarrow$, $\varphi_j(x) \downarrow = \varphi_i(x)$.

Also it is not true that $i \in \text{Ext}$ if there is a $j$ such that $W_i \subset W_j$ and $W_j$ is computable. For example, every $W_i$ is a subset of $\omega$, which is computable. This would imply $\text{Ext} = \omega$, which you are asked to prove is not the case.

Also, you said that $W_i \subset W_j$ where $W_j$ is computable implies $W_i$ is computable. Again, every c.e. set is a subset of $\omega$ which is computable. If your statement was true then every set would be computable. Clearly, $K$ the halting problem is not.


By the enumeration theorem, there exists a index $z$ such that

$\varphi_z(e,x) = \varphi_e(x)$

That is, $z$ is the index for the universal function.

Let $k$ be the index of the following partial computable function.

$\varphi_k(x) = \varphi_z(x,x)$

The claim is that $k \notin \text{Ext}$. Suppose $k \in \text{Ext}$, this would imply that $\varphi_k$ can be extended to a total computable function \varphi'(x). Now define the computable function $\theta$ as follow :

\theta(x) = \varphi'(x) + 1

Clearly $\theta$ is a partial (actually total) computable function. Therefore, it has an index. However, it can not be $\varphi_x$ for any any $x$. This is because if $\varphi_x(x)$ converges, then \theta(x) = \varphi'(x) + 1 = \varphi_z(x,x) + 1 = \varphi_x(x) + 1 \neq \varphi_x(x). If $\varphi_x(x)$ does not coverges, then it can not be equal to $\theta(x)$ since $\theta$ is a total computable function. $\theta \neq \varphi_x$. Contradiction since $\theta$ has no index. Thus $k \notin \text{Ext}$. $\text{Ext} \neq \omega$.

At least in Soare's new book, he asks this question twice. The second you are mean to use the computably inseparable thing. If I can remember how to do it that way I will post a proof later.


Here is the proof of the result using the computably inseparable pair. Recall that $A$ and $B$ are computably inseparable if there does not exists a computable set $C$ such that $A \subset C$ and $A \cap C = \emptyset$. I assumed that you proved already that there exists an inseparable pair $A$ and $B$, where $A$ and $B$ are c.e.

Define

$\psi(x) = \begin{cases} 1 & \quad x \in A \\ 0 & \quad x \in B \end{cases}$

This function partial computable (it diverges if $x$ is in neither). Therefore, this function $\psi$ has an index, say $e$. Assuming $\text{Ext} = \omega$, $\varphi_e$ can be extended to a total computable function $\varphi_f$. Since $\varphi_f$ is total and $0,1$ valued, let $C$ be $\{x : \varphi_f(x) = 1\}$, which is computable since $\varphi_f$ is total. Clearly, $A \subset C$ since $\varphi_f(x) = 1$ whenever $\varphi_e(x) = 1$ and $\varphi_e(x) = 1$ if and only if $x \in A$. Similarly, $A \cap C = \emptyset$ since $\varphi_f(x) = 0$ if $\varphi_e(x) = 0$ and $\varphi_e(x) = 0$ if and only if $x \in B$. Thus $C$ contradict that fact that $A$ and $B$ are computable inseparable. Contradiction!

  • 0
    Also maybe we are using different notations, by $\omega$ I mean the natural numbers. I don't like using $\mathbb{N}$ since I like to reserve that symbol for the set $\{x : x = x\}$, i.e. the domain, when one is doing some model theory in something that look like arithmetics. Also $\omega$ makes it clear that classical computability theory is done on the ordinal $\omega$ rather than $\omega_1^{CK}$ or some other ordinal.2011-09-19
4

A variant: Let $f(i)$ be the number of steps Turing machine number $i$ takes to stop on an empty tape, or undefined if Turing machine number $i$ doesn't stop. That is clearly a partial computable function. But there can be no total computable function $g$ that extends $f$ (that is, such that $g(i)=f(i)$ whenever $f(i)$ is defined). Namely, if such a $g$ existed, we could decide the halting problem simply by running a given machine for $g(i)$ steps and see whether it stops by then or not.

Therefore the index of $f$ in the sequence of all partial computable functions is not a member of $\mathrm{Ext}$.

3

The definition of a pair of recursively inseparable r.e. sets is virtually identical to the definition of a partial function that cannot be extended to a total function. Consider on one hand the sets $A,B$, and on the other hand the function $f$ defined so that $f(n) = 0$ if $n \in A$, $f(n) = 1$ if $n \in B$ (or just $f(n) \downarrow\not = 0$ if $n \in B$), and $f$ is undefined otherwise. Then $f$ is computable if and only if $A$ and $B$ are r.e., and any extension of $f$ to a total function gives a recursive set $C = f^{-1}(0)$ with $A \subseteq C$ and $C \cap B = \emptyset$, and any such $C$ gives an extension of $f$ to a total function. It's all just rearranging synonyms.

  • 0
    @nullgraph: I meant $n \in A$ and similarly for the other instances. $f$ is just a function.2011-09-19