URM Computable Functions of One Variable is Countably Infinite
Jump to navigation
Jump to search
Theorem
The set $\mathbf U$ of all URM computable functions of $1$ variable is countably infinite.
Proof
Let $\mathbf U$ be the set of all URM computable functions.
For each $f \in \mathbf U$, let $P_f$ be a URM program which computes $f$.
Such a program is very probably not unique, so in order to be definite about it, we can pick $P_f$ to be the URM program with the smallest code $\gamma \left({P_f}\right)$.
This is possible from the Well-Ordering Principle.
Let us define the function $h: \mathbf U \to \N$ as:
- $h \left({f}\right) = \gamma \left({P_f}\right)$
Since the same URM program can not compute two different functions of $1$ variable, it can be seen that $h$ is injective.
The result follows from Domain of Injection to Countable Set is Countableā.
$\blacksquare$