[doctor_phil]

Overall an interesting blog post, but the author makes this claim several times:

> So you can never close the case on even one candidate, let alone all of them at once, which means the lower bound stays sealed.

Which is simply not true. The specifics depends on what language you use, but let's take Turing machines as an example. Many candidates are easily disproven: ones that halt immediately, ones that have no rule for writing a "1", ones that have no rule for halting and so on. It's impossible to write a program that can handle every possible candidate though.

And if your string is short enough, let's say the string you are investigating is "0011" then you CAN sit down and check all Turing machines of size 4 and lower. This is essentially what the https://bbchallenge.org/ project did.

For Turing machines we have determined if they halt or not for all machines up to 5 states. It is very computationally hard to push this limit further, but we don't know where the theoretical limit is. We have some large upper bound where a Turing machine computes something that we know is independent of ZFC (see Scott Aaronson for more details), but many suspect that the limit is way lower.