Alan Turing nació en 1912 en Londres, Inglaterra, y murió en 1954 en Wilmslow, Inglaterra.
Su padre era miembro británico del servicio civil de la India, y el abuelo materno trabajaba en el ferrocarril. Cuando Alan tenía un año, su madre se reunió con su padre en la India, y Alan permaneció en Inglaterra con amigos de la familia. Empezó a ir a la escuela, pero como no parecía beneficiarse de ello, después de unos meses lo retiraron.
A la larga empezó a asistir a la escuela preparatoria, donde parecía un alumno de mediano a bueno en la mayoría de las materias, pero un tanto distraído por sus propias ideas. También se interesó por el ajedrez. La enseñanza tradicional de la escuela pública parecía no servirle mayor cosa, y su genio hizo que Turing siguiera sus propios intereses más que los requeridos por sus maestros.
Le criticaban su mala letra, sus problemas con el inglés e, incluso en matemáticas tenía demasiado interés en sus propias ideas y no en los métodos que enseñaban sus maestros para resolver problemas. A pesar de dar respuestas no convencionales, Turing ganaba cuanto premio en matemáticas se ofrecía en Sherborn, la escuela a donde iba. Incluso en química solía hacer experimentos según su propia intuición y en contra de los deseos de los maestros. La opinión de su maestro principal era que si no se apegaba a las enseñanzas y prefería ser un “especialista científico”, estaba perdiendo el tiempo en la escuela pública. No obstante Alan aprendía matemáticas avanzadas por su cuenta, leía a Einstein sobre relatividad y a Eddington sobre mecánica cuántica.
Finalmente ingresó al King’s College en Cambridge, en 1931, a estudiar matemáticas. El primer año, por la preparación que llevaba, no pudo obtener una beca, pero el segundo año sí la obtuvo. Siendo Cambridge un sitio más para personas no convencionales, la vida ahí era más sencilla para Turing. Empezó a leer la Introducción a la filosofía matemática de Bertrand Russell en 1933. Fue entonces que empezó a interesarse por la lógica.
Se graduó en 1934 y en 1935 llevó un curso con Max Newman sobre fundamentos de las matemáticas, donde estudiaron los teoremas de incompletitud de Gödel y las cuestiones sobre decidibilidad de Hilbert. En cierta forma, la “decidibilidad” era una cuestión simple, a saber, dada una proposición matemática, ¿es posible encontrar un algoritmo para decidir si la proposición es cierta o es falsa? Para muchas proposiciones, esto no revestía problemas. La dificultad real surgió al probar que para ciertas proposiciones no existía tal algoritmo. Cuando existía un método para resolver algún problema, era claro que se trataba de un algoritmo. Sin embargo no había una definición de algoritmo que fuera lo suficientemente rigurosa para demostrar su no existencia. Turing comenzó a trabajar en estas ideas.
En 1936 publicó Sobre números calculables, con una aplicación al Entscheidungsproblem (problema de decisión). En este artículo, Turing introdujo una máquina abstracta, ahora llamada “máquina de Turing”, que cambia de un estado a otro usando un conjunto finito preciso de reglas (dadas por una tabla finita) y dependiendo de un solo símbolo que lee de una cinta.
La publicación de este artículo en los Proceedings of the London Mathematical Society, que tiene gran importancia tanto para las matemáticas como para la ciencia de la computación, no resultó fácil, debido podemos pensar a que Alonzo Church acababa de publicar Un problema insoluble en teoría de números elemental en el American Journal of Mathematics en 1936, que también demuestra que no hay procedimiento de decisión para la aritmética. El enfoque es diferente gracias a lo cual, Newman pudo defender la publicación del trabajo de Turing ante la Sociedad Matemática de Londres.
Para Turing una “computadora” es una persona que lleva a cabo un cálculo, una computación; sin embargo, en la descripción de la máquina universal de Turing, podemos pensarla como una computadora con la cinta como programa.
Durante su estancia en Princeton, Turing consideró la posibilidad de construir una computadora. A su regreso a Cambridge comenzó a construir un artefacto mecánico análogo para investigar la hipótesis de Riemann considerado hoy como el problema no resuelto más difícil de las matemáticas. Pero, al conocer el gobierno del proyecto, Turing recibió la solicitud de ayudarlos en el trabajo de romper códigos del programa alemán Enigma.
Después de la guerra, Turing se involucró en un proyecto para construir una computadora. Pero no olvidó las cuestiones de decidibilidad, por ejemplo en el caso de grupos finitamente presentados. La pregunta es si existe un algoritmo para decidir si una determinada palabra es igual a la identidad.
La carrera de Turing se vio interrumpida al ser procesado por homosexualidad. La sentencia fue, ya fuera la castración química o la cárcel. Turing eligió la primera, con graves consecuencias en su salud. Dos años después murió por envenenamiento con cianuro de potasio mientras efectuaba experimentos de electrólisis. Se presume que haya sido suicidio.