News for hackers. Stuff that matters.
Re:Programmers generate every possible melody in MIDI to pre... by vbezhenar on Friday February 28, 2020 @05:11AM (#22441767)
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?

Re:Programmers generate every possible melody in MIDI to pre... by paulddraper on Friday February 28, 2020 @07:19AM (#22442248)
> 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.

Re:Programmers generate every possible melody in MIDI to pre... by shkkmo on Friday February 28, 2020 @08:45AM (#22442695)
> 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.

Re:Programmers generate every possible melody in MIDI to pre... by paulddraper on Friday February 28, 2020 @09:02AM (#22442787)
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

Re:Programmers generate every possible melody in MIDI to pre... by shkkmo on Friday February 28, 2020 @09:15AM (#22442875)
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.

Re:Programmers generate every possible melody in MIDI to pre... by paulddraper on Friday February 28, 2020 @12:20PM (#22444365)
Yes, you're right. I did not do a clear job of explaining the flaw.