# Uncountable number of functions representable by programs

I was reading an old thread here and came across an interesting answer. I was familiar with the Halting Problem, however it never dawned on me that there can only be countably infinite computer programs and this got me thinking.

Obviously all the functions $$x^n$$ can be implemented as computer programs. But so too couldn't all the functions $$x^{{n_1}^{{n_2}^{{n_3}^{...}}}}$$ where $$n_k \in (0..9)$$ Of course each of these would take a near infinitely long time to run but it would still exist computationally and be iterable. Correct me if I am wrong but wouldn't this imply there are uncountably infinite computer programs?

The argument I am hearing is it'd be impossible because you'd have to hardcode an infinite number of characters but I don't feel this is valid because much like the argument for the uncountability of the reals you can always create a unique program by adding another exponent much like how you could always a create a unique real by adding a digit.

• That isn't a function. What does it evaluate to for $x=2$ and $n_i=2$ for all $i$? – Dan Rust May 15 '17 at 22:03
• @DanRust You can evaluate for arbitrarily large $i$ though, correct? No matter how large $i$ is you can evaluate it for $i+1$ obviously for $i = /infty$ you can't evaluate it. – quantik May 15 '17 at 22:04
• You're talking nonsense. I think you need to brush up on some basic set theory terminology and theory. – Dan Rust May 15 '17 at 22:09
• unbounded sets can happily be countably infinite. If I get you correctly, your set is $$\{x^{n_1^{\cdots^{n_k}}}\mid x,k \in \mathbb N, n_1,\ldots n_k \in \mathbb{N}\}.$$ This is a countable set. – Dan Rust May 15 '17 at 22:15
• Depends on the topology you're putting on the set of problems.... – Dan Rust May 15 '17 at 22:57

It depends on what you mean by $\ldots$ in $x^{{n_1}^{{n_2}^{{n_3}^{...}}}}$. If that's a finite tower, it's just the same as $x^n$ for some suitable $n$. If it's an infinite tower of arbitrary $n_i$'s, whatever that means, then no, you can't implement more than countably many different ones.
• You can always construct a larger power tower though.. So for $$x^{{n_1}^{{n_2}^{{n_3}^{{...}^{n_k}}}}$$ you can construct one $$x^{{n_1}^{{n_2}^{{n_3}^{{...}^{n_k+1}}}}$$ – quantik May 15 '17 at 22:12
• So what? If your tower is finite, that's still $x^n$ for some $n$. – Robert Israel May 15 '17 at 23:43