How to execute a random algorithm [closed]

Question

For a project I am working on I'd like to be able to generate and execute a random algorithm (Trust me, there is a good reason!) According to Alan Turings original paper, every TM can be assigned a unique number (A more modern way of understanding this is that every program compiles to some unique big long number in binary).

Let's say I have such a big long number. How can I now execute the program that this corresponds to?

The language is not really important here, I'd be happy to pick some language over another if it contained a mechanism to make this easier. If it's hard no matter what language you pick, I am most proficient in Java.

It would also be okay if you suggested another method of generating a random algorithm, though bear in mind I will eventually change the logic to use some heuristic to pick the algorithm rather than pure randomness.

Answer 1

There's a huge difference between "Every TM can be assigned a number" and "Every number represents a valid, meaningful TM". Consider that the binary string containing the compiled object code for a simple program, say 2000 bytes long. This is an 8000 bit number, of which there are about 10²⁴⁰⁰ values. Of that nearly infinite number of values, only a tiny microscopic fraction represent valid, executable programs. The chances that generating one at random produces anything executable is infinitesimally close to zero.

Now repeat the exercise for, say 6000-byte programs. The problem is not 3 times harder, it's about 10¹²⁰⁰⁰ times harder. And so on...

Answer 2

What you need to do is figure out a way -- any way -- to produce a program given an integer. The "standard" way to do this is to choose an arbitrary programming language, let's say Java, and imagine every possible string that corresponds to the text of a legal, compiling Java program, and then imagine those strings sorted in alphabetical order. This is a well-defined ordering on all Java programs, so if you just have this ordering you can convert any number in the list into a program just by getting the program at the given index.

Unfortunately this isn't too practical of an algorithm; you'd have to enumerate a bazillion strings just to get to the first element in the list, much less element 2134345423532243 or whatever. Every program is a string, but the vast majority of strings are not legal programs. The same issue exists in interpreting a program as a gigantic binary number: every program is a number, but almost no numbers are programs.

So if you are actually interested in generating real programs, and not spending all your time generating bogus programs that aren't actually legal programs at all, you need to do things a bit more cleverly. One way you could do it is by taking your number to be the seed of a random number generator, and then randomly generating, say, an assembly instruction with random registers based on successive calls to the RNG.