Can algorithm discovery be brute forced?

Question

Ultimately, when you compile them to machine code, algorithms are just 1's and 0's. So then - could you brute force the genesis, and thus the discovery of new, useful algorithms? Say, in pursuit of polynomial time algorithms for NP-complete problems.

Of course, rather than pure brute force, perhaps some intelligent force could be applied as a refinement.

---

My back-of-the-napkin-ish attempt to answer the question. Just an exercise; I don't really trust it.

1. In theory, yes - absolutely. The question is whether, in practice, it could be done in a reasonable amount of time in a cost-effective manner.
2. The amount of possible permutations of 1's and 0's is $2^n$ where n = the number of bits in your code.
3. Roughly how many bits does it take to write algorithms? To answer this question, I googled for a quick sort implementation in c, and compiled it to machine code. The result was about 10,000 bytes. So 80,000 bits. Let's say 100,000 bits for a round number.
4. There are $2^{100,000} = 10^{30,103}$ permutations of 1's and 0's.
5. You'd have to test each of these permutations. Let's say it takes 1 minute to test a permutation of 1's and 0's. Then that'd take $10^{30,097}$ years to finish testing. No good.
6. Perhaps the parameters could be tweaked. Let's try just 1,000 bits and 1 second to test each permutation. $2^{1000} = 10^{301}$ permutations. That'd take $10^{295}$ years.
7. Even if we used a lot of computing power, that'd still only cut the exponent down by 5 or 10, maybe. So ultimately, it seems impractical to actually brute force. The question then becomes whether we can combine intelligent force with brute force in algorithm generation.
8. Even though brute force seems impractical, I wonder if future generations will have insane computational power that we would never dream of. If so, brute forcing algorithm generation may be possible. Of course, they may have figured out all the algorithms by then.

Answer 1

You are correct in saying that algorithms are no more than a sequence of strings. However, you should make the distinction between syntactic and semantic properties of the algorithm. Syntactic properties are those relating to the actual code, e.g. what is the length of the program? how many "while" loops does it contain? Semantic properties are related to what the program actually does, e.g. is there some input that would cause this program to go into an infinite loop?

The problem you encounter in your suggestion is that almost every interesting semantic property is undecidable, meaning that even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code. So in fact, the situation is worse than what you think. Even the craziest hardware won't help us, since such tasks are impossible for a computer.

As a side note, suppose your situation was better, and you try to cope with some decidable problem which has an exponential lower bound (i.e. all algorithms for this problem would require exponential time, not just brute force search, even the "smart" ones). Again, better hardware won't help you. For some intuition regarding your parameters, you have $\approx 10^{80}$ atoms in the universe, so performing this amount of operations is hopeless. What you need is a smarter algorithm, but we started with a problem that unfortunately has an exponential lower bound.

Answer 2

Work in somewhat that direction is superoptimization, take a short stretch of machine instructions and search for a shorter/faster one doing the same. The hard part is to check that they really have the same effect. It is a very expensive process, even for it's extremely narrow objective.

Answer 3

It seems that you answered your question. As you stated in 2 your search space has the size of $2^n$, which obviously leads you towards a non polynomial time. Even if you will use some kind of a smart search on this problem that, for example, reduces the search space by the factor of 100 you will still end with a non polynomial size of the search space.

Unless P=NP, you have an algorithm that reduces the search space exponentially or some kind of hardware that works in a totally different way (for example a quantum computer. I don't know if it can help solve this particular problem but there are other problems that have similar complexity that it will solve in reasonable time) you won't be able to solve this problem in a reasonable time.