Alan Turing introdujo el concepto de máquina de Turing en el trabajo "On computable numbers, with an application to the Entscheidungsproblem", publicado por la Sociedad Matemática de Londres en 1936, en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no.