-3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That isn't a function. What does it evaluate to for $x=2$ and $n_i=2$ for all $i$? $\endgroup$ – Dan Rust May 15 '17 at 22:03
  • $\begingroup$ @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. $\endgroup$ – quantik May 15 '17 at 22:04
  • 1
    $\begingroup$ You're talking nonsense. I think you need to brush up on some basic set theory terminology and theory. $\endgroup$ – Dan Rust May 15 '17 at 22:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Dan Rust May 15 '17 at 22:15
  • 1
    $\begingroup$ Depends on the topology you're putting on the set of problems.... $\endgroup$ – Dan Rust May 15 '17 at 22:57
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}}}}$$ $\endgroup$ – quantik May 15 '17 at 22:12
  • $\begingroup$ So what? If your tower is finite, that's still $x^n$ for some $n$. $\endgroup$ – Robert Israel May 15 '17 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.