1
$\begingroup$

Is there a computable function $F: \mathbb N_0^2 \rightarrow \mathbb N_0$, such that for every computable function $f: \mathbb N_0 \rightarrow \mathbb N_0$, there exists an $e \in \mathbb N_0$, such that $F(e, x) = f(x), \forall x \in \mathbb N_0.$

My intuition says there is not, but I haven't found a formal proof. Can anyone confirm my suspicions or know a proof?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes there is. Such an $F$ is called a universal Turing machine.

$e$ is then just an encoding of the Turing machine that computes $f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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