Correo de Emil León
Correo de Emil León | |
|---|---|
 | |
| Nacido | 11 de febrero de 1897 |
| Fallecido | 21 de abril de 1954 (21 de abril de 1954)(57 años) Ciudad de Nueva York, Estados Unidos |
| Alma máter | City College de Nueva York (licenciatura en 1917) [1] Universidad de Columbia (licenciatura en 1918, doctorado en 1920) [2] |
| Conocido por | Formulación 1 Problema de correspondencia posterior Prueba de completitud del cálculo proposicional de Principia Fórmula de inversión de Post Red de Post Teorema de Post |
| Carrera científica | |
| Campos | Matemáticas , lógica |
| Instituciones | Universidad de Princeton |
| Tesis | Introducción a una teoría general de proposiciones elementales (1920) |
| Asesor de doctorado | Cassius Jackson Keyser |
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 .
Vida
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]
Después de completar su doctorado en matemáticas en 1920 en la Universidad de Columbia , supervisado por Cassius Jackson Keyser , realizó un posdoctorado en la Universidad de Princeton en el año académico 1920-1921. Post luego se convirtió 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 abril de 1954 de un ataque cardíaco tras un tratamiento de electroshock para la depresión , [5] [6] menos de dos meses antes de la muerte de Alan Turing . Tenía 57 años.
Trabajos tempranos
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:
- Yo habría descubierto el teorema de Gödel en 1921, si hubiera sido Gödel. [7]
Teoría de la recursión
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 .
Grupos poliádicos
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.
Artículos seleccionados
- Post, Emil Leon (1919). "Las funciones gamma generalizadas". Anales de matemáticas . Segunda serie. 20 (3): 202–217. doi : 10.2307/1967871 . JSTOR 1967871.
- Post, Emil Leon (1921). "Introducción a una teoría general de proposiciones elementales". Revista Americana de Matemáticas . 43 (3): 163–185. doi :10.2307/2370324. hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR 2370324.
- Post, Emil Leon (1936). "Procesos combinatorios finitos – Formulación 1". Revista de lógica simbólica . 1 (3): 103–105. doi :10.2307/2269031. JSTOR 2269031. S2CID 40284503.
- Post, Emil Leon (1940). "Grupos poliádicos". Transacciones de la American Mathematical Society . 48 (2): 208–350. doi : 10.2307/1990085 . JSTOR 1990085.
- Post, Emil Leon (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 Leon (1944). "Conjuntos enumerables recursivamente de números 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 concepto importante de reducción de muchos a uno .
Véase también
- Jerarquía aritmética
- Completitud funcional
- Lista de descubrimientos múltiples
- Lista de pioneros en informática
Notas
- ^Por Urquhart (2008)
- ^ abc O'Connor, John J.; Robertson, Edmund F. , "Emil Leon Post", Archivo de Historia de las Matemáticas de MacTutor , Universidad de St Andrews
- ^ Urquhart (2008), pág. 429.
- ^ "Parque Phyllis Post Goodman". Parques de la ciudad de Nueva York .
- ^ desde Urquhart (2008), pág. 430.
- ^ Baaz, Matthias, ed. (2011). Kurt Gödel y los fundamentos de las matemáticas: horizontes de la verdad (1.ª ed.). Cambridge University Press. ISBN 9781139498432.
- ^ Stillwell, John (2004). "Emil Post y su anticipación de Gödel y Turing". Revista de Matemáticas . 77 (1): 3–14. doi :10.2307/3219226. ISSN 0025-570X. JSTOR 3219226.
- ^ EL Post (1946). "Una variante de un problema recursivamente irresoluble" (PDF) . Bull. Amer. Math. Soc. 52 (4): 264–269. doi : 10.1090/s0002-9904-1946-08555-9 .
Referencias
- 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 desde Russell hasta Church . Manual de la historia de la lógica. Vol. 5. Elsevier BV.
- Neary, Turlough (2015), "Indecidibilidad en sistemas de etiquetas binarias y el problema de correspondencia posterior para cinco pares de palabras", Simposio internacional sobre aspectos teóricos de la informática, Leibniz International Proceedings in Informatics (LIPIcs), páginas 649–661, 2015.
Lectura adicional
- Anshel, Iris Lee; Anshel, Michael (noviembre de 1993). "Del teorema post-Markov a la criptografía de clave pública pasando por problemas de decisión". The American Mathematical Monthly . 100 (9). Asociación Matemática de Estados Unidos: 835–844. doi :10.2307/2324657. JSTOR 2324657.
- Dedicado a Emil Post y contiene material especial sobre él. Entre ellos se incluye "La relación de Post con la criptología y los criptógrafos de su época: ... Steven Brams, el famoso 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 de Nueva York durante la primera mitad del siglo XX que necesita una exploración más profunda. Los autores esperan que este artículo sirva para profundizar en esta cuestió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 del Post.
- Davis, Martin (1994). "Emil L. Post: Su vida y obra". Solvabilidad, demostrabilidad, definibilidad: Las obras completas de Emil L. Post . Birkhäuser. págs. xi–xxviii.
- Un ensayo biográfico.
- Jackson, Allyn (mayo de 2008). “Una entrevista con Martin Davis”. Avisos de la AMS . 55 (5): 560–571.
- Amplio material sobre Emil Post basado en sus recuerdos de primera mano.
- Jackson, Allyn (octubre de 2018). "Emil Post: fidelidad psicológica". Inferencia: Revista Internacional de Ciencias . doi :10.37282/991819.18.48. S2CID 240012225.
- Un artículo biográfico.
Enlaces externos
- Documentos de Emil Leon Post 1927-1991, American Philosophical Society , Filadelfia, Pensilvania.
- "Celebrando a Emil Post y su "insoluble problema" de la etiqueta: 100 años después". YouTube . Wolfram. 19 de mayo de 2021. Archivado desde el original el 21 de diciembre de 2021.
