Programs Encoded as Prime Numbers...

[Einhander Sn0m4n]

This article on illegal prime numbers made me think.

Is it theoretically possible for any executable to be rendered as a bigass prime number?

[Beowulf]

If you use the GZip method, yes. If you want it to be directly executable, not really.

[Jaepheth]

{ 0 , 1 } represents all the information in the universe... depending on how you interpret it. (your algorithm for reading it)

[B5B7]

If it's an illegal number it should be arrested and charged. Of course murder is illegal but we don't arrest murder, we arrest the murderer.

Answer 1 for yes to a question, 2 (or 0) for no.
Q: Did you do this murder? A: 1 - this means 1 is illegal.

[ThatGuyFromThatPlace]

Wow, on some level I guess I knew the debate existed (being a cryptofreak and all) but I guess I hadn't looked into enough to realize they were debating whether the physical number representing the files/programs were 'illegal' thats just crazy awesome as a debate In practice I have to go with 'information wants to be free (except my information)'

and, to the OP:

Yes, any executable can be rendered as a prime number, its just a matter of applying a suitable algorithm.

[Durandal]

Proving that this is possible would involve proving that there exists a one-to-one mapping between the set of all prime numbers and the set of all Turing machines. My first instinct would be to say "Yes", since neither the set of all primes nor the set of all Turing machines is uncountable.

[haard]

This article on illegal prime numbers made me think.

Is it theoretically possible for any executable to be rendered as a bigass prime number?

With the right algorithm, sure.


In fact, any program is an algorithm, and any algorithm can be represented by a (natural) number, so it's not just the primes that are in danger.

[Surlethe]

Proving that this is possible would involve proving that there exists a one-to-one mapping between the set of all prime numbers and the set of all Turing machines. My first instinct would be to say "Yes", since neither the set of all primes nor the set of all Turing machines is uncountable.

Is existence enough? If there are a countably infinite number of Turing machines, then you can even show there exists a bijection between the primes and the Turing machines, but isn't saying that you can encode any Turing machine as a prime's binary representation a little stronger than simply saying you can map from the primes to the Turing machines and back?

[ThatGuyFromThatPlace]

This article on illegal prime numbers made me think.

Is it theoretically possible for any executable to be rendered as a bigass prime number?

With the right algorithm, sure.


In fact, any program is an algorithm, and any algorithm can be represented by a (natural) number, so it's not just the primes that are in danger.

Prime numbers are generally useful for encryption whereas other natural numbers are not so much.

[Kuroneko]

Of course. Since every program can be interpreted as a unique natural number n, it can also be encoded as the nth prime p_n. However, it will be easier to simply pad the program with data that will never be executed so that the resulting number is a prime in the first place (especially on a computer, where any sequence of bits is naturally interpretable as a number).