Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Somehow the beginning of my question, which says "Hi" is cut off also. –  nullgraph Sep 19 '11 at 0:48
1  
Concerning your comment: that's due to the software, see here for an explanation and links. –  t.b. Sep 19 '11 at 1:05

3 Answers 3

up vote 6 down vote accepted

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!

share|improve this answer
    
Thanks! Could you also explain why $\omega$ is computable? –  nullgraph Sep 19 '11 at 1:55
    
Define $f(x) = 1$. The constant function. Clearly this function is total and computable. $x \in \omega$ if and only if $f(x) = 1$. That is the formal proof, the real way to think about it is $\omega$ is computable because you don't need to do anything to determine if $x \in \omega$ because everything is there. –  William Sep 19 '11 at 2:01
    
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. –  William Sep 19 '11 at 2:06

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}$.

share|improve this answer

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.

share|improve this answer
    
I don't really understand your notation, what does $f \in A$ means? Do you mean $f=\varphi_e, e \in A?$ –  nullgraph Sep 19 '11 at 18:37
    
@nullgraph: I meant $n \in A$ and similarly for the other instances. $f$ is just a function. –  Carl Mummert Sep 19 '11 at 18:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.