Cardinality of uncomputable functions

319 Views Asked by At

Let's denote the set of all computable functions from $\mathbb{N} \to \mathbb{N}$ as $F$. Now, by any Gödel numbering, $F \simeq \mathbb{N}$.

However, $\mathbb{N}^\mathbb{N} \simeq \mathbb{R}$.

It's obvious that not all functions over the natural numbers are computable, however, how would it be obvious to prove that there are as many uncomputable functions over the natural numbers as real numbers without using the statements above?

1

There are 1 best solutions below

0
On BEST ANSWER

Fix some noncomputable function $f:\mathbb{N}\rightarrow\mathbb{N}$. For each real $r\in (0,1)$, define a new function $$g_r: x\mapsto\begin{cases} f({x\over 2}) & \mbox{ if $x$ is even,}\\ \mbox{${x-1\over2}$th digit of $r$} & \mbox{ if $x$ is odd}\\ \end{cases}$$ (where if $r$ has two decimal expansions, we pick the eventually-$0$ one).

Since $f\le_Tg_r$, the function $g_r$ is noncomputable; meanwhile, the map $r\mapsto g_r$ is clearly injective. So we get an injection from $(0,1)$ to the set of noncomputable functions.