views:

133

answers:

6

Is it possible to write a automatic application generator that can output hundreds of applications/day? An application is just a series of binary values. If a super computer is put to generate millions of combinations/day and output the generated binaries with varying sizes. These binaries will then be "run" to see if they are actually run and if they do then these are sent to some testing personnels to check "what is generated".

Who knows, we might start getting 100% bug free solutions.

+2  A: 

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

Firestrand
Upvoted, and I'll add, look into Genetic Algorithms too. I also have reason to disagree with other respondents that GPs and GAs are of only theoretical interest or useful in toy domains.
High Performance Mark
+2  A: 

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.

jk
+1  A: 

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.

Piskvor
Maybe I should save this question till 2099 when I expect we will have computers that wont behave like monkeys ;-)
A9S6
To build a computer fast enough to check every possible program in sensible time you'd have to use more quartz than there is in the universe. So this will be impossible in year 2099 and in year 10000000 just the same way it is impossible now.
liori
+8  A: 

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 28192 possible 1KB "programs". Let's say you could generate 220 programs per second (roughly a million programs per second, which is quite high). That means it would still take you 28172 seconds to generate all possible 1KB binaries, which is (according to wolfram alpha) roughly 102442 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?)

Eddie
Very nice explanation: You just killed my idea :-(
A9S6
Well, just a thought: Why should we wait for "10^2442 times the age of the universe" for *all* the combinations to be processed. Even if 2 programs can be generated per second then isn't there a probability to get around 5-6 runnable programs/week? The time you calculated is the Worst Case Scenario.
A9S6
@A9S6: Interesting comment. Rather than enumerate all binary numbers within a limit, it's possible to design an alphabet consisting of instructions, and enumerate strings of those. They could be carefully chosen so that almost every "program" would "run". That leaves you with the question - Which ones are doing something that might seem interesting to semi-intelligent beings like us? Then there's the question of what input to they process, or do they just "dream"?
Mike Dunlavey
+3  A: 

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.

liori
++ Nice summary of approaches, but it awakens my dormant AI knowledge. What has already been accomplished by people can be done by computers, because people are computers (programmed by genetic algorithm). Of course, we computers are still trying to figure out how we did it :-)
Mike Dunlavey
... The thing about the Halting Problem is the way it's stated. People can't solve it either, unless one of the acceptable answers is "I give up".
Mike Dunlavey
+1  A: 

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.

Mike Dunlavey