Proving that there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ that is not URM-computable.

Question

I'm trying to prove the statement given in the question title, and I'm unsure as to whether my approach is valid. A confirmation of my approach or a correction with a hint pointing me in the right direction would be most appreciated!

My approach:

Any URM program that computes a function can be specified by a finite number of lines of code. The URM has a 4-element instruction set. Any given line of code is either $Z(i)$ which zeroes the given register, $S(i)$ which increments the given register, $T(i, j)$ which transfers the value of register i to register j, and $J(i, j, k)$ which jumps to line k in the code provided that the values stored in registers i and j are equal. We can think of Z(i) and S(i) as points in $\mathbb{N}$, $T(i, j)$ as a point in $\mathbb{N}^2$, and $J(i, j, k)$ as a point in $\mathbb{N}^3$. Since $\mathbb{N}$, $\mathbb{N}^2$, and $\mathbb{N}^3$ are all countable, the number of possible instructions for any given line of code is the union of these four sets which is countable. Since there is a bijection between the number of lines of code in a URM-Program and $\mathbb{N}$, the total number of possible URM-programs is the countable union of countably many instruction sets which is countable. I would then go on to prove that there are an uncountable number of functions $f: \mathbb{N} \rightarrow \mathbb{N}$.

Answer 1

Hint The set $A$ of all functions $f : \mathbb N \to \{ 0,1\}$ is a subset of your set, and it is uncountable:

You can construct a bijection $F: A \to \mathcal{P}(\mathbb N)$ by $$F(f) = \{ x | f(x) =1 \}$$

Alternately, you can think about each such function $f \in A$ as being a number $x \in [0,1]$ written in binary as $0.f(1)f(2)f(3)....$.

This identification is onto, which shows uncountability. It is not 1-1 due to the fact that some numbers can be represented as a finite binary but also as $.x_1x_2...x_k\bar{1}$, but is it one to one outside a countable set.

Second solution

You can also prove that the set of functions $f :\mathbb N \to \mathbb N$ is uncounatble by the Cator diagonal argument.

Assume that it is countable, write all the functions in a sequence $f_1, f_2,..,f_n ,..$ and then define a new function by $$g(n) \neq f_n(n)$$ this function is not in your list.