Impossible Programs
The source of computers' power and its inevitable limitation
Every aspect of our lives has been transformed by the invention of general-purpose programmable computers. As a result, it’s tempting to believe that computers can solve any logical or mathematical problem; that if we throw enough time, money and nerds at a question, we can produce a program which answers it.
Unfortunately the universe is never that convenient. There are hard theoretical limits on what programs are capable of doing, and there will always be easily-stated problems which are impossible for any computer to solve.
This talk by Tom Stuart at the 2013 Scottish Ruby Conference uses Ruby to tell a nail-biting, math-free story about the source of a computer’s power, the inevitable drawbacks of that power, and the impossible programs which lie at the heart of uncomputability.
