Emil Leon Post

Emil Leon Post (Augustów, 1897 – Nueva York, 1954) fue un matemático y lógico estadounidense, conocido sobre todo por su trabajo en el campo que acabaría llamándose teoría de la computabilidad. Nació en una familia judía polaca que emigró a Nueva York en 1904. De niño se interesaba por la astronomía, pero a los doce años perdió el brazo izquierdo en un accidente de coche, lo que le cerró la carrera de astrónomo profesional y le llevó a las matemáticas.

Estudió en el City College de Nueva York, donde se graduó en 1917, y se doctoró en la Universidad de Columbia en 1920. Tras un año de posdoctorado en Princeton, trabajó como profesor de matemáticas de instituto en Nueva York. En 1936 entró en el departamento de matemáticas del City College. Padeció episodios maníacos y depresión, y murió en 1954 de un infarto tras un tratamiento de electrochoque.

En su tesis doctoral, publicada en 1921, demostró que el cálculo proposicional de los Principia Mathematica era completo, es decir, que toda tautología es un teorema. Empleó tablas de verdad de forma independiente a C. S. Peirce y Ludwig Wittgenstein. Estuvo muy cerca de descubrir la incompletitud de los Principia, resultado que Gödel probó en 1931, aunque nunca llegó a publicar sus ideas en ese sentido.

En 1936 desarrolló, con independencia de Alan Turing, un modelo de cálculo equivalente a la máquina de Turing, al que llamó Formulation 1. Sus sistemas canónicos, basados en la reescritura de cadenas de símbolos, anticiparon técnicas que hoy son habituales en la especificación de lenguajes de programación. En 1946 introdujo el problema de correspondencia de Post, un ejemplo sencillo de indecidibilidad que resultó clave para demostrar la indecidibilidad en la teoría de lenguajes formales. En 1944 planteó además la cuestión que se conoce como problema de Post, sobre la existencia de conjuntos recursivamente enumerables no computables de grado de Turing inferior al del problema de la parada; se resolvió afirmativamente en los años cincuenta. Por último, en 1940 hizo una contribución fundamental a la teoría de los grupos poliádicos o n-arios.

Su influencia se percibe en la teoría de la computabilidad, en la lógica matemática y en la informática teórica.