Emil Leon Post

Emil Leon Post ( / p oʊ s t / ; 11 de febrero de 1897 – 21 de abril de 1954) fue un matemático y lógico estadounidense . Es conocido principalmente por su trabajo en el campo que posteriormente se conocería como teoría de la computabilidad .

Post nació en Augustów , gobernación de Suwałki , Polonia del Congreso , Imperio ruso (actualmente Polonia), en el seno de una familia polaco-judía que emigró a la ciudad de Nueva York en mayo de 1904. Sus padres fueron Arnold y Pearl Post. ^{[ 2 ]}

Post siempre había estado interesado en la astronomía, pero a los doce años perdió el brazo izquierdo en un accidente automovilístico. Esta pérdida representó un obstáculo importante para convertirse en astrónomo profesional, lo que lo llevó a decidirse por las matemáticas en lugar de la astronomía. ^{[ 3 ]}

Post asistió a la escuela secundaria Townsend Harris y posteriormente se graduó del City College de Nueva York en 1917 con una licenciatura en matemáticas. ^{[ 1 ]}

Tras obtener 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 durante el año académico 1920-1921. Posteriormente, Post se convirtió en profesor de matemáticas de secundaria en la ciudad de Nueva York.

Post se casó con Gertrude Singer (1900–1956) en 1929, con quien tuvo una hija, Phyllis Post Goodman (1932–1995). ^{[ 4 ]} Post dedicaba como máximo tres horas al día a la investigación por consejo de su médico para evitar los ataques maníacos que venía experimentando desde su año en Princeton. ^{[ 5 ]}

En 1936, fue nombrado profesor en el departamento de matemáticas del City College de Nueva York. Falleció en abril de 1954 de un infarto tras un tratamiento de electroshock para la depresión . ^{[ 5 ] [ 6 ]}

En su tesis doctoral, posteriormente abreviada y publicada como «Introducción a una teoría general de las 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 C.S. Peirce y Ludwig Wittgenstein y les dio un buen uso matemático. El conocido libro 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.

Durante su estancia en Princeton, Post estuvo muy cerca de descubrir la incompletitud de Principia Mathematica , que Kurt Gödel demostró en 1931. Inicialmente, Post no publicó sus ideas, ya que creía que necesitaba un «análisis completo» para que fueran aceptadas. ^{[ 2 ]} Como dijo Post en una postal a Gödel en 1938:

Habría descubierto el teorema de Gödel en 1921, si hubiera sido Gödel. ^{[ 7 ]}

En 1936, Post desarrolló, independientemente de Alan Turing , un modelo matemático de computación que era esencialmente equivalente al modelo de máquina de Turing . Con la intención de que este fuera el primero de una serie de modelos de potencia equivalente pero complejidad creciente, tituló su artículo Formulation 1. Este modelo a veces se llama "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 del 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 generativo de Post, y de hecho cualquier función computable o conjunto computable .

Los sistemas de correspondencia fueron introducidos por Post en 1946 para dar ejemplos sencillos de indecidibilidad . ^{[ 8 ]} Demostró que el problema de correspondencia de Post (PCP), que consiste en satisfacer sus restricciones, es, en general, indecidible. La indecidibilidad del problema de correspondencia resultó ser precisamente 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 no computable cuyo grado de Turing sea menor que el del problema de la parada . Esta cuestión, que se conoció como el problema de Post , impulsó numerosas investigaciones. Fue resuelta afirmativamente en la década de 1950 con la introducción del potente método de prioridad en la teoría de la computabilidad .

Post realizó 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 teorema principal demostró que un grupo poliádico es el producto iterado de elementos de un subgrupo normal de un grupo , de tal manera 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.

• Post, Emil L. (1919). "Las funciones gamma generalizadas" . Annals of Mathematics . Segunda serie. 20 (3): 202– 217. doi : 10.2307/1967871 . JSTOR 1967871 . 
• Post, Emil L. (1921). "Introducción a una teoría general de proposiciones elementales". American Journal of Mathematics . 43 (3): 163– 185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR 2370324 . 
• Post, Emil L. (1936). "Procesos combinatorios finitos – Formulación 1". Journal of Symbolic Logic . 1 (3): 103– 105. doi : 10.2307/2269031 . JSTOR 2269031 . S2CID 40284503 .  
• Post, Emil L. (1940). "Grupos poliádicos" . Transactions of the American Mathematical Society . 48 (2): 208– 350. doi : 10.2307/1990085 . JSTOR 1990085 . 
• Post, Emil L. (1943). "Reducciones formales del problema general de decisión combinatoria". American Journal of Mathematics . 65 (2): 197– 215. doi : 10.2307/2371809 . JSTOR 2371809 . 
• Post, Emil L. (1944). "Conjuntos recursivamente enumerables de enteros positivos y sus problemas de decisión" . Boletín de la Sociedad Matemática Americana . 50 (5): 284– 316. doi : 10.1090/s0002-9904-1944-08111-1 .Introduce el importante concepto de reducción de muchos a uno .

• Jerarquía aritmética
• Completitud funcional
• Lista de múltiples descubrimientos
• Lista de pioneros en informática

• Stillwell, John (2004), "Emil Post y su anticipación de Gödel y Turing" (PDF) , Mathematics Magazine , 77 (1): 3–14 , doi : 10.2307/3219226 , JSTOR 3219226 
• Urquhart, Alasdair (2008). "Emil Post" (PDF) . En Gabbay, Dov M.; Woods, John Woods (eds.). Lógica de Russell a Church . Manual de Historia de la Lógica. Vol.  5. Elsevier BV.
• Neary, Turlough (2015), "Indecidibilidad en sistemas de etiquetas binarias y el problema de correspondencia de publicaciones para cinco pares de palabras", Simposio Internacional sobre Aspectos Teóricos de la Informática, Actas Internacionales Leibniz en Informática (LIPIcs), páginas 649–661, 2015.

• Anshel, Iris Lee; Anshel, Michael (noviembre de 1993). "Del teorema post-Markov a través de problemas de decisión a la criptografía de clave pública". The American Mathematical Monthly . 100 (9). Mathematical Association of America: 835– 844. doi : 10.2307/2324657 . JSTOR 2324657 . 

  Dedicado a Emil Post, este libro contiene material especial sobre él. Entre sus temas se incluye: «La relación de Post con la criptología y los criptógrafos de su época:… Steven Brams, reconocido teórico de juegos y politólogo, nos ha comentado que la vida y el legado de Emil Post representan un aspecto de la vida intelectual neoyorquina durante la primera mitad del siglo XX que merece una exploración más profunda. Los autores esperan que este artículo contribuya a dicha exploración». (págs.  842-843)

• Davis, Martin, ed. (1993). Lo indecidible . Dover. págs. 288-406 . ISBN  0-486-43228-9.

  Reimprime varios artículos de Post.

• Davis, Martin (1994). "Emil L. Post: Su vida y obra". Solvabilidad, demostrabilidad, definibilidad: Obras completas de Emil L. Post . Birkhäuser. pp. xi– xxviii. 

  Un ensayo biográfico.

• Jackson, Allyn (mayo de 2008). "Una entrevista con Martin Davis" . Notices of the AMS . 55 (5): 560– 571.

  Gran cantidad de material sobre Emil Post procedente de sus propios recuerdos.

• Jackson, Allyn (octubre de 2018). "Emil Post: Fidelidad psicológica" . Inference: International Review of Science . doi : 10.37282/991819.18.48 . S2CID 240012225 . 

  Un artículo biográfico.

• Documentos de Emil Leon Post 1927-1991 , Sociedad Filosófica Americana , Filadelfia, Pensilvania.
• "Celebrando a Emil Post y su 'problema irresoluble' del tag: 100 años después" . YouTube . Wolfram. 19 de mayo de 2021. Archivado del original el 21 de diciembre de 2021.