Surprises in Logic (2016)

Summary

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 out this animated video created in 2009 using a program less than 4 kilobytes long that runs on a Windows XP machine: VIDEO A beautiful alien planet compressed into a mere 4 kilobytes of information! As my friend the programmer Bruce Smith noted: To be fair, the complexity of some of the OS, graphics drivers, and hardware should be included, but this is a lot less than you might think if you imagine rewriting it purely for compactness rather than for speed, and only including what this sort of program needs to produce output. Still, it's quite amazing. Mind you, people didn't figure out how to produce such fancy images from tiny amounts of information overnight! Iñigo Quílez, one of the guys who made this video, has explained some of the tricks. They're deep! And they were developed over decades in the demoscene — a computer art subculture where people produce demos: non-interactive audio-visual computer presentations that run in real time. According to the Wikipedia article on the demoscene:...