> You can trivially write a program which will enumerate all the possible byte sequences in the universe. So you can claim that this tiny program contains everything...
Not to get too far off topic, but even an infinitely long byte sequence cannot represent all numbers. It's possible to construct something not representable by that sequence via Cantor's diagonal argument: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
It doesn't contain the floating point representation of that number, which would be infinitely long, but it does contain the UTF8-encoded constructive proof that uniquely identifies that number.
Most real numbers have infinite-length constructive proofs.
Uncountable is uncountable is uncountable. If any correspondence/encoding existed between naturals and reals, the reals would be countable. (But they are not, so it is fool's errand to search for such an encoding.)
Surely not? If there are more numbers that can be represented in any amount of bytes (as shown by the diagonal argument), then you cannot represent a constructive proof for each of them in any amount of bytes.
Kind of. A constructive proof by definition means something like you can explain exactly what the number is in a finite number of bytes.
The standard diagonalization argument is a constructive proof, identifying a specific number. Normally a constructive proof is preferable. But with a bit of hand waving you can make it into a non-constructive proof that there are "unknowable" numbers that cannot be described in any finite amount of bytes.
In practice constructible for reals mean that you can approximate them with arbitrarily small know precision e.g. a sequence of retional number numbers q_n each no more that 1/n apart from the actual real number.
The point is that such a sequence needs to be constructive in the usual sense, so there are still only a countable number of them.
The argument still applies, yes. Nevertheless the string still contains all finite substrings, which includes all English sentences describing such numbers.
The implication is that human minds wouldn't be able to represent it either, at least not with language.
Perhaps I am mis-undertanding the diagonal argument, but it doesn't appear to show what you claim it shows.
The diagonal argument seems to be a proof that there are uncountably many infinite byte sequences. So while it proves that it would impossible to "enumerate" every infinite byte sequence, it doesn't prove that there exists a number that cannot be represented by some infinite byte sequence.
Indeed, I believe the opposite can be shown to be true by constructing a mapping from every finite number to an infinite byte sequence. ASCII trivially provides such a mapping for real numbers, and finite-tuples of real numbers (such as imaginary numbers) can be mapped by alternating digits from each element of the tuple.
Edit: The key distinction is that the set of finite byte sequences is infinite, but countable, while the set of infinite byte sequences is not only infinite, but also uncountable. Which of these two sets is deemed the set of "possible byte sequences" seems to be the critical distinction and the turn of phrase "all possible byte sequences in the universe" seems to imply all byte sequences of finite length.
All the possible byte sequences contain all the possible programs.
All the possible programs can receive input of infinite length and output bytes of infinite length depending on input.
So if we can supply any input to any program and treat its output as part of result, does this argument still work? Is there such a number that can't be constructed by some program receiving some input?
> All the possible byte sequences contain all the possible programs.
Correct.
> Is there such a number that can't be constructed by some program receiving some input?
Yes. Most numbers are not representable by a program...unless you allowed a program to be infinite length, in which case the first statement is no longer true.
There's nothing particularly unique about a digit-based encoding for Cantor's diagonal argument.
> in which case the first statement is no longer true.
Why is that? What would be an example of an infinite program that could not be represented by an infinite byte sequence? Indeed, it seems trivial to map an infinite series of machine code instructions to an infinite series of bytes.
Edit: It seems like the first statement is false only if you use a different understanding of "possible" for "possible byte sequences" and "possible programs" where the former excludes infinite length and the latter does not.
I internally editorialized your first statement to be "all the possible [finite] byte sequences contain all the possible programs".
Because you cannot enumerate all infinite byte sequences, according to Cantor's diagonal argument as linked earlier. [1]
Calling certain numerical representations "computer programs" in no way changes the fundamentals. There is no way -- no matter how clever your encoding -- to enumerate all real numbers.
I am not the person you were originally responding to.
You don't have to enumerate all real numbers to create a mapping from real numbers to infinite byte sequences.
I am merely pointing out that the first statement only becomes false if you editorialize it to "all the possible [finite] byte sequences contain all the [infinite] possible programs". If you treat the meaning of "possible" consistently in that sentence, I believe it remains true regardless of whether you define infinity as possible or not.
> an infinitely long byte sequence cannot represent all numbers
Okay, all natural numbers then. I don't think that changes the argument.
(Reals are a funny thing because any format you choose has numbers that are infinitely long in that format. Which is basically the same thing you said.)
Not all numbers, such as real and complex numbers. But you indeed can represent all integers, all possible programs, all digital music, digital images, digital everything. Not sure if those other music / images which cannot be digitalized are so relevant.
Not to get too far off topic, but even an infinitely long byte sequence cannot represent all numbers. It's possible to construct something not representable by that sequence via Cantor's diagonal argument: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument