Are there infinite sequences not reproducible by finite algorithms?

Question

Let me know if this is a repeat question. I was thinking that sequence of integers we deal with (e.g., the digits of $\pi$, the prime numbers, the Fibonacci numbers, pseudorandom numbers) seem to be reproducible by a finite algorithm.

Are there infinite sequences of integers which are not reproducible by a finite algorithm? If so, do we know much about what these sequences "look like"? E.g., what is their cardinality?

Also, is there a name for a number whose decimal expansion is such a sequence? Do we know much about these numbers?

Answer 1

There are uncountably many such real numbers.

Any algorithm can be described as a sequence of 0's and 1's that encode its operations. Thus, we can identify any algorithm with a natural number, so it makes sense to speak of the $k^{th}$ algorithm.

Let $\alpha$ be the real number such that the $k^{th}$ digit is 1 if the $k^{th}$ algorithm halts after a finite number of steps when run with an empty string as it's input and 0 otherwise. This is basically the halting problem, so no algorithm can enumerate the digits of this real number.

To see that uncountably many such real numbers exist, note that the number of algorithms described by finite strings is countable.

Answer 2

Look up "recursive set", also "Chaitin's constant".

Answer 3

If you want a concrete example that in theory should be computable but not by any fixed finite length algorithm, consider the "busy beaver" function $B(n)$. This is the maximum number of steps a computer program of size $n$ can run on empty input and terminate without running forever. It is possible to compute $B(n)$ for small $n$, and some believe that longer and longer computer programs can compute $B(n)$ for arbitrarily large $n$ (where each program has a limit on $n$ that it can compute $B(n)$ for), but there is no one fixed finite length program that can compute $B(n)$ for all $n$.