Surprises in Logic (2016)

Surprises in Logic John Baez April 4, 2016 There's a complexity barrier built into the very laws of logic: roughly speaking, while lots of things are more complex than this, we can't prove any specific thing is more complex than this. And this barrier is surprisingly low! Just how low? Read this. And then see what happens when combine this idea with the famous 'surprise examination paradox', also known as the 'unexpected hanging paradox'. Mathematically speaking, these ideas are called Chaitin's incompleteness theorem and the Kritchman–Raz proof of Gödel's second incompleteness theorem. But don't be intimidated: I'll explain everything you need to know! After that I'll explain another surprise: there's a computer that computes any uncomputable function... in some model of arithmetic. Could we grow the whole universe with all its seeming complexity starting from a little seed? How much can you do with just a little information? People have contests about this. Dan Piponi pointed ... Read full article.