Let s say you were generating binaries that are 1KB in size (pretty small). 1KB is 8192 bits. That means there s a total of 2⁸¹⁹² possible 1KB "programs". Let s say you could generate 2²⁰ programs per second (roughly a million programs per second, which is quite high). That means it would still take you 2⁸¹⁷² seconds to generate all possible 1KB binaries, which is (according to wolfram alpha) roughly 10²⁴⁴² times the age of the universe. This should give you an idea as to how unlikely it would be to come across a useful program in an exhaustive search of all 1KB programs (how many useful 1KB programs are there, anyway?)

I ll expand Firestand s answer on genetic programming.

There were ideas like yours already; they were almost all the times limited to some artificial environment though.

My friend wrote a system to automatically (using genetic programming) evolve programs for a CoreWars environment. These programs aren t long (tens-to-hundreds of assembly instructions), and the set of legal instructions is not very big, so the space of possible programs is much smaller than full-blown GUI applications for x86. At the beginning the bots were hardly fighting each other; but with each generation there were better and better fighters in the set.

You can read more about this concept in a research paper (PDF).

It wouldn t be very easy to apply this idea to x86, the set of instructions here is large and interactions between them are sometimes very complex. However you could theoretically build a virtual machine with a simplified instruction set and evolve programs for it. I have read about that somewhere, but I can t recall where.

Still, checking all possible combinations is not reasonable even for very very simple code. You really want to have some heuristic strategy, like genetic programming.

Your idea has yet another flaw. You assume that you can strictly specify all requirements for your programs, so that all requirements can be tested automatically. This is impossible or very close to impossible. Assuming that you want to find a program that adds two int32 numbers, to be really sure that program works correctly you have to check all possible inputs, so 2^64 possibilities. Try to imagine how many scenarios you would have to check if you were writing a financial program.

You could try to use an "intelligent" system to find correctness proofs for your programs... but because you re not limited to some subset of programs (you can generate simply anything that can be run on a processor), you cannot reason about all programs because of the Halting problem. Simply put, it is impossible to detect whether some programs work correctly without checking all possible inputs.

Look into Genetic Programming http://en.wikipedia.org/wiki/Genetic_programming

sure you could generate millions of random executables, but thats the easy bit, the hard bit would be working out which ones do something useful, which requires testing, which you aren t automating.

Short answer: no. Although it s theoretically possible, it s much, much less likely than you winning the jackpot in every lottery in the world, every day, for the rest of your life.

An application is just a series of binary values.

Indeed - a series of precisely ordered binary values. By randomly generating series of binary values, you ll get an application that actually is an executable, actually executes, and doesn t crash instantly, with the probability of 0, before the universe ends. (All right, it s not exactly zero, but it s so close to zero that it s undistinguishable from it in the real universe, as opposed to mathematics).

See the Infinite monkey theorem, particularly the section Probabilities.

This is like the old saw: If you had a large number of monkeys typing for a sufficiently long time, they would eventually produce the works of Shakespeare.

That s the good news. The bad news is they would also produce every possible misspelling of the works of Shakespeare, including those written backwards, or with every beautiful word replaced by a vulgar word, and even that would be a negligible fraction of all the other stuff they would produce.

Unless, you only had one monkey, Shakespeare himself.