Comment by atomicnumber3
12 hours ago
Something I have always (even pre-LLMs) found funny to think about is - all code possible to run on a computer already exists. It's some permutation of all the bits of available memory. It's in there somewhere. So, suppose you want a specific program.
1. Some huge % of those possible programs are obviously not the one you want (most don't even compile).
2. Remaining programs might look similar to the one you want, but are buggy enough to be completely unusable, unreadable to the point of intractability, and so on.
3. Remaining programs look substantially correct but upon using for > a few mins you note major bugs that make it still not correct enough.
4. Remaining programs look substantially correct and seem to generally do your will but contain a long-tail showstopper subtle bug that corrupts saved data, or makes all the output subtly incorrect, etc.
5. Remaining programs might be useful, even if they're mildly annoying.
6. This process can probably continue for several thousand iterations until you finally find "it." The program you wanted. Or... one of them. There's probably still 10k+ candidate programs left at this stage.
Our job has always been to get to 5 and aspire to 6. Indeed most of software development is just doing 5->6 in a loop.
I think LLMs help us get to somewhere between 3 and 5 faster than we used to. And a big problem with them is that programs in 3 vs 5 all already look substantially correct and there's no way to know if you're getting 3 or 5.
Generally, the above is not how it _felt_ to write software pre-LLMs, it was just a cute way to imagine what you're doing. Now it's weirdly apropos.
I once saw a YouTube video where two beginners were learning the basics programming, and upon opening a cmd prompt, one of them said "It's insane if you just type the right words into this box, you can steal someone's 401K in Arkansas" (Or something along those lines). It's always stuck with me that technically that's pretty correct. It's probably not how you'd go about it, but with the correct magic words in the right order it would work
One of my professors used an example like this to encourage you to pause if you ever find yourself doing something like "maybe if I just flip this < to > the tests will pass". The space of incorrect programs (even ones that pass your tests) is enormous compared to the space of correct programs.
If you like thinking about this and haven't seen this before, check out the busy beaver problem[1].
[1]: https://en.wikipedia.org/wiki/Busy_beaver
I remember the Computer Recreations column in Scientific American on busy beavers back in 1984. I was too young then to really appreciate it. (I really miss that column—and the Amateur Scientist.)
I found it here (page 19) https://wkbpic.com/wkbx/SA/1984/1984-08-01.pdf
flipping > to >= works quite often though!
I was about to say a lot of algorithms or invariant bugs for me are slight mistakes at an edge of something
2 replies →
all code possible to run on a computer already exists. It's some permutation of all the bits of available memory. It's in there somewhere
This seems either mathematically impossible or vacuous, depending on what you mean ...
I think the intent is clear. We could just enumerate all strings in size and lexicographical order. Then the task is only to filter, which strings are programs we desire.
It's the same sentiment as "the typing itself is not the issue, it's the order of the button presses that's difficult."
Of course, by Rice's theorem, all interesting questions are undecidable anyway...
It's the same mindset some artists have when considering raw stone for a statue: there's a Greek god in there somewhere, you just have to find him.
It's a way of thinking, not some deep metaphysical mystery. Unless it is actually a deep metaphysical mystery, but I'd rather not go there.
You should check out Borges’, The Library of Babel.
Basically if you have an infinite string of characters in some language then you have every possible book, tweet, script, scribble, and scrap of everything ever written. You just have to find it.
Thats already a large universe to cover. Programs? Much bigger set.
the infinite string must have more refined properties than infinite length. an infinite string of a repeating char doesn't encode much of interest.
I believe it's more that the library contains the finite set of all books which have a (unique) permutation of the language's characters to size N. The challenge to finding the cure to cancer in such a collection of sufficiently large N is indeed finding which book it is in.
I've thought similarly about music before. Everything's there in white noise. To get music you just have to selectively remove parts of it.
> all code possible to run on a computer already exists
You have to be careful; that line of thinking might get you trapped in L-space. You’d need a very skilled librarian and possibly a bag of peanuts to get back out.
Oook
I think this is a great abstraction of the process I've never considered in those terms and I like it. It explains a bit of how software development differs from some other building processes where the desired outcome is being discovered as you figure out how to make something that produces that outcome
There are plenty of processes that have this property, though. For example: setting up a home, workspace, kitchen, factory, office, etc. to fit a particular purpose. As you discover what works well in a particular space, you will refactor your workflows, seating organization, storage systems, etc to fit what you're doing. And it may even have multiple valid configurations - for example seasonal variations like outdoor vs indoor areas.
> It's some permutation of all the bits of available memory. It's in there somewhere.
True, but the number of possible permutations is so large it's incomprehensible. Let's limit ourselves to say a 50 MiB program, meaning the size of the compiled binary. If I'm remembering the math correctly, that amount of memory can hold 2^(2^20 * 50 * 8) different states. That's 2^419430400 or roughly 10^126000000. For comparison, the heat death of the universe is predicted to occur in about 10^100 years, or 10^107 seconds. You'd need to be able to look at more than a million programs per second to examine them all before the end of the universe.
yes and if you want to code a little swimmer that explores program-space, you'll find there too!
Reality is a fractal (Mandelbrot?) and this is where LLMs will help science. They will help us explore the fuzzy edges faster. LLMs probably won't find new "leaves", but they should be able to cover a lot of useful but "boring" fuzz.