**Logic hacking**In mathematics, unlike ordinary life, the boundary between the knowable and the unknowable is a precisely defined thing. But finding it isn't easy. Its exact location could

*itself* be unknowable. But we don't even know

*that!* This month, a bunch of 'logic hackers' have stepped up to the plate and made a lot of progress. They've sharpened our estimate of where this boundary lies. How? By writing shorter and shorter computer programs for which it's unknowable whether these programs run forever, or stop.

A

**Turing machine** is a simple kind of computer whose inner workings have N different states, for some number N = 1,2,3,...

The

**Busy Beaver Game** is to look for the Turing machine with N states that runs as long as possible before stopping. Machines that never stop are not allowed in this game.

We know the winner of the Busy Beaver Game for N = 1,2,3 and 4. Already for N = 5, the winner is unknown. The best known contestant is a machine that runs for 47,176,870 steps before stopping. There are 43 machines that might or might not stop - we don't know.

When N is large enough, the winner of the Busy Beaver Game is

*unknowable*.

More precisely, if you use the ordinary axioms of mathematics, it's impossible to prove that any particular machine with N states is the winner of the Busy Beaver Game... as long as those axioms are consistent.

How big must N be, before we hit this wall?

We don't know.

But earlier this month, Adam Yedidia and Scott Aaronson showed that it's 7910 or less.

And by now, thanks to a group of logic hackers like Stefan O’Rear, we know it's 1919 or less.

So, the unknowable kicks in - the winner of the Busy Beaver Game for N-state Turing machines becomes unknowable using ordinary math - somewhere between N = 5 and N = 1919.

The story of how we got here is is fascinating, and you can read about it on my blog post:

https://johncarlosbaez.wordpress.com/2016/05/21/the-busy-beaver-game/Anything that I didn't make clear here, should be explained there. If it ain't clear there, ask me!

#bigness