Emil Leon Post ( / p oʊ st / ; 11 de febrero de 1897 - 21 de abril de 1954) fue un matemático y lógico estadounidense . Es mejor conocido por su trabajo en el campo que eventualmente se conoció como teoría de la computabilidad .
Post nació en Augustów , Gobernación de Suwałki , Congreso de Polonia , Imperio Ruso (ahora Polonia) en una familia judía polaca que emigró a la ciudad de Nueva York en mayo de 1904. Sus padres fueron 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 automovilístico. Esta pérdida fue un obstáculo importante para ser un astrónomo profesional, lo que lo llevó a decidir dedicarse a las matemáticas en lugar de la astronomía. [3]
Post asistió a la escuela secundaria Townsend Harris y se graduó en el City College de Nueva York en 1917 con una licenciatura en matemáticas. [1]
Después de completar su doctorado. Se licenció en matemáticas en 1920 en la Universidad de Columbia , bajo la supervisión de Cassius Jackson Keyser , y realizó un posdoctorado en la Universidad de Princeton en el año académico 1920-1921. Luego, Post se convirtió en profesor de matemáticas en una escuela 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 dedicó como máximo tres horas al día a la investigación siguiendo el consejo de su médico para evitar ataques maníacos, que había estado experimentando 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 infarto tras un tratamiento de electroshock para la depresión ; [5] [6] tenía 57 años.
En su tesis doctoral, posteriormente 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 estaba 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 consulta sobre lógica matemática de Jean van Heijenoort (1966) reimprimió el clásico artículo de Post de 1921 en el que se exponen estos resultados.
Mientras estaba en Princeton, Post estuvo muy cerca de descubrir lo incompleto de los Principia Mathematica , lo que Kurt Gödel demostró en 1931. Inicialmente, 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 éste 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 de 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 reescritura de cadenas y desarrollado por Post en la década de 1920, pero primero. publicado 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, por lo que, junto con el cálculo lambda de Church , es una influencia destacada de la lógica moderna clásica en la informática práctica. Post ideó un método de "símbolos auxiliares" mediante el cual podía representar canónicamente cualquier lenguaje posgenerativo y, de hecho, cualquier función o conjunto computable.
El Post introdujo los sistemas de correspondencia en 1946 para dar ejemplos sencillos de indecidibilidad . [8] Mostró que el problema de la correspondencia postal (PCP) de satisfacer sus restricciones es, en general, indecidible. La indecidibilidad del problema de la correspondencia resultó ser exactamente lo que se necesitaba para obtener resultados de indecidibilidad en la teoría de los lenguajes formales .
En un influyente discurso ante la Sociedad Matemática Estadounidense en 1944, planteó la cuestión de la existencia de un conjunto recursivamente enumerable incomputable cuyo grado de Turing es menor que el del problema de detención . Esta cuestión, que pasó a ser conocida como el problema de Post , estimuló muchas investigaciones. 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 aún influyente a la teoría de los grupos poliádicos, o n -arios, en un extenso artículo publicado en 1940. Su principal teorema demostró que un grupo poliádico es la multiplicación iterada de elementos de un subgrupo normal de un grupo. , tal que el grupo cociente es cíclico de orden n - 1. También demostró que una operación de grupo poliádico en un conjunto se puede expresar en términos de una operación de grupo en el mismo conjunto. El artículo contiene muchos otros resultados importantes.