What is it that computers CAN’T do? A simple introduction to Turing’s Halting Problem

May 29, 2011

(This is the first in a series about computationally insolvable problems, with a focus on Turing machines and the halting problem)

As a modern society, we rely on faster and more powerful computers in greater and more diverse areas of our life with every successive generation. In fact, some people believe in (and are working hard towards) the possibility of a technological “Singularity” by the 2030’s, when artificial intelligence will have surpassed human intelligence sufficiently to recursively self-improve (eg. A slightly smarter-than-human AI will make an AI slightly smarter than itself, which will in turn improve its own design, etc) and when the future will become extremely difficult to predict.

Read the rest of this entry »