Emil Leon Post ( 11 de febrero de 1897 - 21 de abril de 1954) fue un matemático y lógico estadounidense . Es más conocido por su trabajo en el campo que eventualmente se conocería como teoría de la computabilidad .
Post nació en Augustów , Gobernación de Suwałki , Polonia del Congreso , Imperio ruso (ahora Polonia) en una familia judía polaca que emigró a la ciudad de Nueva York en mayo de 1904. Sus padres eran Arnold y Pearl Post. [2]
Post se había interesado por la astronomía, pero a los doce años perdió su brazo izquierdo en un accidente de coche. Esta pérdida supuso un importante obstáculo para su carrera profesional como astrónomo, lo que le llevó a decidir dedicarse a las matemáticas en lugar de a la astronomía. [3]
Post asistió a la Townsend Harris High School y continuó sus estudios hasta graduarse en el City College de Nueva York en 1917 con una licenciatura en matemáticas. [1]
Tras completar su doctorado en matemáticas en 1920 en la Universidad de Columbia , bajo la supervisión de Cassius Jackson Keyser , realizó un posdoctorado en la Universidad de Princeton en el año académico 1920-1921. Post se convirtió luego en profesor de matemáticas de secundaria en la ciudad de Nueva York.
Post se casó con Gertrude Singer en 1929, con quien tuvo una hija, Phyllis Post Goodman (1932-1995). [4] Post dedicaba tres horas diarias como máximo a la investigación siguiendo el consejo de su médico para evitar los ataques maníacos que venía sufriendo desde su año en Princeton. [5]
En 1936 fue nombrado miembro del departamento de matemáticas del City College de Nueva York. Murió en 1954 de un ataque cardíaco tras un tratamiento de electroshock para la depresión ; [5] [6] tenía 57 años.
En su tesis doctoral, más tarde abreviada y publicada como "Introducción a una teoría general de proposiciones elementales" (1921), Post demostró, entre otras cosas, que el cálculo proposicional de Principia Mathematica era completo: todas las tautologías son teoremas , dados los axiomas de Principia y las reglas de sustitución y modus ponens . Post también ideó tablas de verdad independientemente de CS Peirce y Ludwig Wittgenstein y les dio un buen uso matemático. El conocido libro de referencia de Jean van Heijenoort sobre lógica matemática (1966) reimprimió el clásico artículo de Post de 1921 que exponía estos resultados.
Mientras estaba en Princeton, Post estuvo muy cerca de descubrir la incompletitud de los Principia Mathematica , algo que Kurt Gödel demostró en 1931. Al principio, Post no publicó sus ideas porque creía que necesitaba un «análisis completo» para que fueran aceptadas. [2] Como dijo Post en una postal a Gödel en 1938:
En 1936, Post desarrolló, independientemente de Alan Turing , un modelo matemático de computación que era esencialmente equivalente al modelo de la máquina de Turing . Con la intención de que este fuera el primero de una serie de modelos de potencia equivalente pero de complejidad creciente, tituló su artículo Formulación 1. Este modelo a veces se denomina "máquina de Post" o máquina Post-Turing , pero no debe confundirse con las máquinas de etiquetas de Post u otros tipos especiales de sistema canónico de Post , un modelo computacional que utiliza la reescritura de cadenas y desarrollado por Post en la década de 1920 pero publicado por primera vez en 1943. La técnica de reescritura de Post es ahora omnipresente en la especificación y el diseño de lenguajes de programación, y así, junto con el cálculo lambda de Church , es una influencia destacada de la lógica moderna clásica en la computación práctica. Post ideó un método de "símbolos auxiliares" mediante el cual podía representar canónicamente cualquier lenguaje postgenerativo y, de hecho, cualquier función o conjunto computable.
Los sistemas de correspondencia fueron introducidos por Post en 1946 para dar ejemplos simples de indecidibilidad . [8] Demostró que el problema de correspondencia de Post (PCP) de satisfacer sus restricciones es, en general, indecidible. La indecidibilidad del problema de correspondencia resultó ser exactamente lo que se necesitaba para obtener resultados de indecidibilidad en la teoría de lenguajes formales .
En un influyente discurso ante la American Mathematical Society en 1944, planteó la cuestión de la existencia de un conjunto recursivamente enumerable e incomputable cuyo grado de Turing es menor que el del problema de detención . Esta cuestión, que se conoció como el problema de Post , estimuló mucha investigación. Se resolvió afirmativamente en la década de 1950 mediante la introducción del poderoso método de prioridad en la teoría de la computabilidad .
Post hizo una contribución fundamental y todavía influyente a la teoría de los grupos poliádicos, o n -arios, en un extenso artículo publicado en 1940. Su teorema mayor mostró que un grupo poliádico es la multiplicación iterada de elementos de un subgrupo normal de un grupo , de modo que el grupo cociente es cíclico de orden n − 1. También demostró que una operación de grupo poliádico sobre un conjunto puede expresarse en términos de una operación de grupo sobre el mismo conjunto. El artículo contiene muchos otros resultados importantes.