0

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.

xyz
  • 929
  • 4
  • 12

1 Answers1

2

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

Mark Saving
  • 31,855
  • 1
    +1. Note to the OP that this answer doesn't just use the set $W_x$ but the specific enumeration of $W_x$ corresponding to the index $x$; that is, we can have $W_x=W_y$ but $f(x)\not=f(y)$. It's a good exercise to show that this is unavoidable: there is no computable partial function $h$ such that $(i)$ if $W_x\not=\emptyset$ then $h(x)$ is defined and in $W_x$ and $(ii)$ if $W_x=W_y$ then $h(x)\simeq h(y)$ (where "$\simeq$" means "either both sides are undefined, or both sides are defined and equal to each other"). – Noah Schweber May 23 '21 at 02:43