Post #2298373

@simontatham@hachyderm.io This reminds me of something I've been thinking about ... We have literally no idea what computers can do. Due to the Busy Beaver question, people have extensively investigated what "extremely short" programs can and can't do. Progress on this problem is extremely hard. Finding BB(6,2) requires fully understanding all turning machines of a particular size "roughly 42 bytes long" (my estimate, may be wildly incorrect!) and the value of BB(6,2) is an open question. (https://en.wikipedia.org/wiki/Busy_beaver#:~:text=current%206%2Dstate%2C%202%2Dsymbol%20best%20contender) By contrast, some have found that the smallest i386 linux program is in the range of 45 bytes (https://www.muppetlabs.com/~breadbox/software/tiny/teensy.html) and it's routine for programs (just the executable file!) to clock in at over 100MB. Given that the sheer number of even 1kB programs dwarfs the number of programs humans will ever try running, it seems likely that there are substantially shorter programs that make "an office suite", "a mastodon client", "a web browser" ... but we have no effective way of finding them. Instead, to borrow your framing, we've chosen a paradoxically much easier "search" method that generates huge programs instead of tiny programs. This also means that there are probably extremely small programs that do surprising things we haven't even conceived of. This reminds me of a quip I've seen attributed to Knuth about the P=?NP problem itself: Given the sheer number of possible programs (exponentially many for any length), it seems statistically likely that at least one of them must solve the problem of interest in polynomial time, therefore P=NP. I've never been sure if this is some kind of meta-joke or is actually a held position... (And of course there's also the famous apology about writing such a long letter: The author simply didn't have enough time to write a short letter on the subject)