Choosing an element of $W_x$ in a computable way

43 Views Asked by At

If $W_x$ denotes the domain of the program with number $x$, the question is:

Is there a partial computable function $f$ such that if $W_x$ is not empty then $f(x)\in W_x$, and otherwise, $f(x)$ is undefined?

My attempt is to take $f(x)=x$ if $x\in W_x$ and otherwise, $f$ is undefined. But I don't know how to deal with the non-empty condition.

1

There are 1 best solutions below

1
On BEST ANSWER

Your answer does not work, because there could be some element of $W_x$ other than $x$.

This is indeed possible. I will give an informal description of how to do this.

n <- 0;
Loop {
   n <- n + 1;
   For each i such that 1 <= i <= n do {
      Attempt to run algorithm x on input i for n steps;
      If this results in x halting on input i, halt and output i.
   }
}

If $x$ halts on some input $i$, then this algorithm will eventually halt on or before the iteration where $n = i$. And if this algorithm halts and returns $i$, then it must be the case that $x$ halts on input $i$.