Skip to main content
added 1 character in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The answer is no. Suppose that there are computable funtionsfunctions $q$ and $s$ as you describe.

Let $k$ be a program that performs the following task. It starts enumerating $1$s at the start of the sequence until it discovers that $s(k)$ is defined. (We use the Kleene recursion theorem to know that there is such a self-referential program $k$.) Note that this must eventually happen, since otherwise $\varphi_k$ would be $\infty$, in which asecase $s(k)$ should be defined.

When it finds that $s(k)$ is defined, then the program pauses the enumeration of its output and starts computing $\varphi_{q(s(k))}$. This will definitely produce an element of $\mathbb{N}_\infty$. And so the program waits until either it produces more $1$s than we have put on $\varphi_k$, in which case program $k$ switches to $0$s immediately, causing $\varphi_{q(s(k))}\neq\varphi_k$; or else $\varphi_{q(s(k))}$ produces a $0$, in which case we can let $\varphi_k$ produce all $1$s, again causing $\varphi_{q(s(k))}\neq\varphi_k$.

The answer is no. Suppose that there are computable funtions $q$ and $s$ as you describe.

Let $k$ be a program that performs the following task. It starts enumerating $1$s at the start of the sequence until it discovers that $s(k)$ is defined. (We use the Kleene recursion theorem to know that there is such a self-referential program $k$.) Note that this must eventually happen, since otherwise $\varphi_k$ would be $\infty$, in which ase $s(k)$ should be defined.

When it finds that $s(k)$ is defined, then the program pauses the enumeration of its output and starts computing $\varphi_{q(s(k))}$. This will definitely produce an element of $\mathbb{N}_\infty$. And so the program waits until either it produces more $1$s than we have put on $\varphi_k$, in which case program $k$ switches to $0$s immediately, causing $\varphi_{q(s(k))}\neq\varphi_k$; or else $\varphi_{q(s(k))}$ produces a $0$, in which case we can let $\varphi_k$ produce all $1$s, again causing $\varphi_{q(s(k))}\neq\varphi_k$.

The answer is no. Suppose that there are computable functions $q$ and $s$ as you describe.

Let $k$ be a program that performs the following task. It starts enumerating $1$s at the start of the sequence until it discovers that $s(k)$ is defined. (We use the Kleene recursion theorem to know that there is such a self-referential program $k$.) Note that this must eventually happen, since otherwise $\varphi_k$ would be $\infty$, in which case $s(k)$ should be defined.

When it finds that $s(k)$ is defined, then the program pauses the enumeration of its output and starts computing $\varphi_{q(s(k))}$. This will definitely produce an element of $\mathbb{N}_\infty$. And so the program waits until either it produces more $1$s than we have put on $\varphi_k$, in which case program $k$ switches to $0$s immediately, causing $\varphi_{q(s(k))}\neq\varphi_k$; or else $\varphi_{q(s(k))}$ produces a $0$, in which case we can let $\varphi_k$ produce all $1$s, again causing $\varphi_{q(s(k))}\neq\varphi_k$.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The answer is no. Suppose that there are computable funtions $q$ and $s$ as you describe.

Let $k$ be a program that performs the following task. It starts enumerating $1$s at the start of the sequence until it discovers that $s(k)$ is defined. (We use the Kleene recursion theorem to know that there is such a self-referential program $k$.) Note that this must eventually happen, since otherwise $\varphi_k$ would be $\infty$, in which ase $s(k)$ should be defined.

When it finds that $s(k)$ is defined, then the program pauses the enumeration of its output and starts computing $\varphi_{q(s(k))}$. This will definitely produce an element of $\mathbb{N}_\infty$. And so the program waits until either it produces more $1$s than we have put on $\varphi_k$, in which case program $k$ switches to $0$s immediately, causing $\varphi_{q(s(k))}\neq\varphi_k$; or else $\varphi_{q(s(k))}$ produces a $0$, in which case we can let $\varphi_k$ produce all $1$s, again causing $\varphi_{q(s(k))}\neq\varphi_k$.