Emil Leon Post - Emil Leon Post

Emil Leon Post
Emil Leon Post.jpg
Nascer 11 de fevereiro de 1897
Augustów , governadorado de Suwałki , Congresso da Polônia , Império Russo
(agora Polônia)
Morreu 21 de abril de 1954 (21/04/1954)(57 anos)
Nova York, EUA
Alma mater City College of New York (BS, 1917)
Columbia University (AM 1918, Ph.D. 1920)
Conhecido por Formulação 1
Pós problema da correspondência
Integralidade à prova de Principia ' s proposicional cálculo
fórmula de inversão do Post
estrutura do Post
teorema de Pós
Carreira científica
Campos Matemática , lógica
Instituições Universidade de Princeton
Tese Introdução a uma teoria geral de proposições elementares  (1920)
Orientador de doutorado Cassius Jackson Keyser

Emil Leon Post ( / p oʊ s t / ; 11 de fevereiro de 1897 - 21 de abril de 1954) foi um matemático e lógico americano nascido na Polônia . Ele é mais conhecido por seu trabalho no campo que eventualmente se tornou conhecido como teoria da computabilidade .

Vida

Post nasceu em Augustów , governadorado de Suwałki , Congresso da Polônia , Império Russo (agora Polônia) em uma família judia polonesa que imigrou para a cidade de Nova York em maio de 1904. Seus pais eram Arnold e Pearl Post.

Post se interessava por astronomia, mas aos 12 anos perdeu o braço esquerdo em um acidente de carro. Essa perda foi um obstáculo significativo para ser um astrônomo profissional, levando à sua decisão de buscar matemática em vez de astronomia.

Post frequentou a Townsend Harris High School e continuou a se formar no City College of New York em 1917 com um bacharelado em matemática.

Após completar seu Ph.D. em matemática em 1920 na Columbia University , supervisionado por Cassius Jackson Keyser , ele fez um pós-doutorado na Princeton University no ano acadêmico de 1920–1921. Post então se tornou um professor de matemática do ensino médio na cidade de Nova York.

Post se casou com Gertrude Singer em 1929, com quem teve uma filha, Phyllis Post Goodman (1932–1995). Post passava no máximo três horas por dia pesquisando a conselho de seu médico, a fim de evitar ataques maníacos, que vinha experimentando desde seu ano em Princeton.

Em 1936, foi nomeado para o departamento de matemática do City College de Nova York. Ele morreu em 1954 de ataque cardíaco após tratamento com eletrochoque para depressão ; ele tinha 57 anos.

Trabalho cedo

Em sua tese de doutorado, posteriormente encurtada e publicada como "Introdução a uma Teoria Geral das Proposições Elementares" (1921), Post provou, entre outras coisas, que o cálculo proposicional de Principia Mathematica estava completo: todas as tautologias são teoremas , dados os axiomas de Principia e as regras de substituição e modus ponens . Post também desenvolveu tabelas de verdade independentemente de Ludwig Wittgenstein e CS Peirce e as colocou em bom uso matemático. O conhecido livro fonte de Jean van Heijenoort sobre lógica matemática (1966) reimprimiu o clássico artigo de Post de 1921 apresentando esses resultados.

Enquanto estava em Princeton, Post chegou muito perto de descobrir a incompletude do Principia Mathematica , o que Kurt Gödel provou em 1931. Post inicialmente falhou em publicar suas idéias, pois acreditava que precisava de uma 'análise completa' para que fossem aceitas. Como Post disse em um cartão postal para Gödel em 1938:

Eu teria descoberto o teorema de Gödel em 1921 - se eu fosse Gödel.

Teoria da recursão

Em 1936, Post desenvolveu, independentemente de Alan Turing , um modelo matemático de computação que era essencialmente equivalente ao modelo da máquina de Turing . Pretendendo ser o primeiro de uma série de modelos de poder equivalente, mas com complexidade crescente, ele intitulou seu artigo Formulação 1 . Este modelo é às vezes chamado de "máquina de Post" ou máquina de Post-Turing , mas não deve ser confundido com as máquinas de etiquetas de Post ou outros tipos especiais de sistema canônico Post , um modelo computacional que usa reescrita de string e desenvolvido por Post na década de 1920, mas primeiro publicado em 1943. A técnica de reescrita de Post é agora onipresente na especificação e design de linguagens de programação, e assim com o lambda-cálculo de Church é uma influência saliente da lógica moderna clássica na computação prática. Post desenvolveu um método de 'símbolos auxiliares' pelos quais ele poderia representar canonicamente qualquer linguagem Pós-gerativa e, de fato, qualquer função computável ou conjunto.

Os sistemas de correspondência foram introduzidos por Post em 1946 para dar exemplos simples de indecidibilidade. Ele mostrou que o Post Correspondence Problem (PCP) de satisfazer suas restrições é, em geral, indecidível. A indecidibilidade de seu problema de correspondência do Post acabou sendo exatamente o que era necessário para obter resultados de indecidibilidade na teoria das linguagens formais .

Em um discurso influente para a American Mathematical Society em 1944, ele levantou a questão da existência de um conjunto recursivamente enumerável incontestável cujo grau de Turing é menor do que o do problema da parada . Essa questão, que ficou conhecida como problema de Post , estimulou muitas pesquisas. Foi resolvido afirmativamente na década de 1950 com a introdução do poderoso método de prioridade na teoria da recursão .

Grupos poliádicos

Post fez uma contribuição fundamental e ainda influente para a teoria dos grupos poládicos, ou n- arários, em um longo artigo publicado em 1940. Seu teorema principal mostrou que um grupo poliádico é a multiplicação iterada de elementos de um subgrupo normal de um grupo , de modo que o grupo quociente é cíclico de ordem n - 1. Ele também demonstrou que uma operação de grupo poliádico em um conjunto pode ser expressa em termos de uma operação de grupo no mesmo conjunto. O artigo contém muitos outros resultados importantes.

Artigos selecionados

  • Post, Emil Leon (1919). "As funções gama generalizadas" . Annals of Mathematics . Segunda série. 20 (3): 202–217. doi : 10.2307 / 1967871 . JSTOR  1967871 .
  • Post, Emil Leon (1921). "Introdução a uma teoria geral das proposições elementares". American Journal of Mathematics . 43 (3): 163–185. doi : 10.2307 / 2370324 . hdl : 2027 / uiuo.ark: / 13960 / t9j450f7q . JSTOR  2370324 .
  • Post, Emil Leon (1936). "Processos Combinatórios Finitos - Formulação 1". Journal of Symbolic Logic . 1 (3): 103–105. doi : 10.2307 / 2269031 . JSTOR  2269031 .
  • Post, Emil Leon (1940). "Grupos poliádicos" . Transactions of the American Mathematical Society . 48 (2): 208–350. doi : 10.2307 / 1990085 . JSTOR  1990085 .
  • Post, Emil Leon (1943). "Reduções formais do problema geral de decisão combinatória". American Journal of Mathematics . 65 (2): 197–215. doi : 10.2307 / 2371809 . JSTOR  2371809 .
  • Post, Emil Leon (1944). "Conjuntos recursivamente enumeráveis ​​de inteiros positivos e seus problemas de decisão" . Boletim da American Mathematical Society . 50 (5): 284–316. doi : 10.1090 / s0002-9904-1944-08111-1 .Apresenta o importante conceito de redução muitos-um .

Veja também

Notas

Referências

Leitura adicional

  • Anshel, Iris Lee; Anshel, Michael (novembro de 1993). "Do Teorema Post-Markov Através de Problemas de Decisão à Criptografia de Chave Pública". The American Mathematical Monthly . Mathematical Association of America. 100 (9): 835–844. doi : 10.2307 / 2324657 . JSTOR  2324657 .
    Dedicado a Emil Post e contém material especial no Post. Isso inclui "Post's Relation to the Cryptology and Cryptographists of his Era: ... Steven Brams, o famoso teórico dos jogos e cientista político, comentou para nós que a vida e o legado de Emil Post representa um aspecto da vida intelectual de Nova York durante o primeira metade do século XX que necessita muito de uma exploração mais profunda. Os autores esperam que este artigo sirva para promover essa busca ". (pp. 842-843)
  • Davis, Martin, ed. (1993). O Indecidível . Dover. pp.  288 –406. ISBN 0-486-43228-9.
    Reimprime vários artigos por Post.
  • Davis, Martin (1994). "Emil L. Post: sua vida e obra". Solvabilidade, Provabilidade, Definibilidade: The Collected Works of Emil L. Post . Birkhäuser. pp. xi – xxviii.
    Um ensaio biográfico.
  • Jackson, Allyn (maio de 2008). "Uma entrevista com Martin Davis" . Avisos da AMS . 55 (5): 560–571.
    Muito material sobre Emil Post de suas lembranças de primeira mão.

links externos