Is the following function

$$ g(x) = \begin{cases} 1 & \text{if $\exists n \geq 0:\ \varphi_n(x) \downarrow$}\\ \uparrow & \text{otherwise} \end{cases} $$


Please note that $\varphi_n(x) \downarrow$ means that the function with index $i$ halts on input $x$.


Quick loophole: If $\varphi_i$ means something even remotely like what it looks like it should, then your function is the same function as $$ g(x) = 1 $$ which is very easy to compute.

(If $\varphi_i$ is something so unconventional that this doesn't work, you'll probably want to look up dovetailing. The Wikipedia article I link to is perhaps not particularly approachable, but a bit of determined googling may turn up something better.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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