Suppose we have a function $f:\omega^{n}\rightarrow\omega^{m}$ with $n,m\in\omega$ with $n,m\geq 1$ for which there exists a Turing machine that on input $(k_{1},...,k_{n})$ produces $f(k_{1},...,k_{n})$ as output. My question is: Is there any definition saying that this kind of function are also Turing computable? I know that the case when $m=1$ is the most found in computability books, but my question is what happens in the general case?
Asked
Active
Viewed 41 times
0
-
Just consider any computable bijection between $\mathbb N$ and $\mathbb N^m$. – Xoff Jun 09 '19 at 22:39
-
So instead of considering the computability of $f$ as described in the question, we consider the computability of the function $\varphi\circ f:\mathbb{N}^{n}\rightarrow\mathbb{N}$ where $\varphi$ is any computable bijection between $\mathbb{N}^{m}$ and $\mathbb{N}$? (I changed $\omega$ for $\mathbb{N}$ but I think that doesn't affect the question) – Fernando Altamirano Jun 19 '19 at 00:06