Turing's argument that computable sequences are enumerable

84 Views Asked by At

In Turing's paper from 1936, he shows how the following counter-argument is a fallacy:

If the computable sequences are enumerable, let $\alpha_n$ be the $n$-th computable sequence, and let $\phi_n(m)$ be the $m$-th figure in $\alpha_n$. Let $\beta$ be the sequence with $1 - \phi_n(n)$ as its $n$-th figure. Since $\beta$ is computable, there exists a number $K$ such that $1 - \phi_n(n) = \phi_K(n)$ all $n$. Putting $n = K$, we have $1 = 2\phi_K(K)$, i.e. $1$ is even. This is impossible. The computable sequences are therefore not enumerable.

Turing writes that

The fallacy lies in the assumption that $\beta$ is computable

However, I'm perplexed by another point in that reasoning. As I understand it, it firstly choses an arbitrary $n$, then defines $\alpha_n$, and then says that $\exists K \in N,\; \forall n,\; 1 - \phi_n(n) = \phi_K(n)$ ("there exists a number $K$ such that $1 - \phi_n(n) = \phi_K(n)$ all $n$"). So although $n$ has been set, this still supposes $n$ can be arbitrary.

Again, the following reads "Putting $n = K$", which contradicts the fact that $n$ was already picked.

Let aside the fallacy Turing aims to highlight, am I wrong in my understanding of this reasoning?