Hacker News Reader

Comment by vbezhenar | Hacker News Reader

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 including god. So you can claim copyright for everything.

View on HN

> 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

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.

[1] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

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.

Yes, you're right. I did not do a clear job of explaining the flaw.

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.

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.

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.

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.

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.

Well, it could contain the floating-point representation, since floating-point is a finite representation.

But it couldn't contain the real number representation.

Incorrect.

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.)

All you have to do is enumerate an infinity of infinities. It's no problem at all.

> 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.)

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.

> even an infinitely long byte sequence cannot represent all [real] numbers

You misread. The previous comment said

> you can trivially write a program which will enumerate all the possible [finite] byte sequences in the universe

No one is interested in your infinitely long musical score.

One could make the same argument for a mathematician with a typewriter. The fact that it could come up with a particular sequence is, I think, less important than whether or not ot actually has recorded a particular sequence.

Claiming copyright of everything won't save you from producing all that child pornography and hate speech, not to mention unauthorized copies of state secrets. ;)

For the state secrets, the state would have to identify the specific strings that constitute the violation, so that's unlikely to be a problem in practice.

Nah, they have no problem identifying the string, they'll just slap you with a gag order, which itself will also have a gag order.

That's all great until the judge asks for a demonstration to show it can generate the material you're presumably suing over.

At that point, you simply explain Cantor's diagonalization proof and the concept of countable and uncountable infinities.

But is it enough to prove that it could produce any melody? After all, couldn't a binary adder produce every executable binary possible? Well, eventually, and with enough memory.

No, because each thing you want to claim copyright on must be “fixed in physical form.”

Reply on news.ycombinator.com