Can algorithm discovery be brute forced? 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.


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.
The amount of possible permutations of 1's and 0's is $2^n$ where n = the number of bits in your code.
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.
There are $2^{100,000} = 10^{30,103}$ permutations of 1's and 0's.
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.
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.
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.
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.
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.