Sistemas de lógica baseados em ordinais -Systems of Logic Based on Ordinals

Systems of Logic Based on Ordinals foi a dissertação de doutorado do matemático Alan Turing .

A tese de Turing não é sobre um novo tipo de lógica formal, nem ele estava interessado nos chamados sistemas de 'lógica classificada' derivados da numeração ordinal ou relativa, nos quais comparações podem ser feitas entre estados de verdade com base na veracidade relativa. Em vez disso, Turing investigou a possibilidade de resolver a condição de incompletude de Gõdel usando o método dos infinitos de Cantor . Essa condição pode ser declarada assim - em todos os sistemas com conjuntos finitos de axiomas, uma condição ou exclusiva se aplica ao poder expressivo e à comprovação; ou seja, pode-se ter poder e nenhuma prova, ou prova e nenhum poder, mas não ambos.

A tese é uma exploração de sistemas matemáticos formais segundo o teorema de Gödel . Gödel mostrou para que qualquer sistema formal S poderoso o suficiente para representar a aritmética, existe um teorema G que é verdadeiro, mas o sistema é incapaz de provar. G poderia ser adicionado como um axioma adicional ao sistema no lugar de uma prova. No entanto, isso criaria um novo sistema S 'com seu próprio teorema verdadeiro G' não comprovado, e assim por diante. A tese de Turing analisa o que acontece se você simplesmente iterar este processo repetidamente, gerando um conjunto infinito de novos axiomas para adicionar à teoria original, e ainda dar um passo adiante no uso de recursão transfinita para ir "além do infinito", produzindo um conjunto de novos teorias G n , uma para cada número ordinal n.

A tese foi concluída em Princeton sob Alonzo Church e foi uma obra clássica em matemática que introduziu o conceito de lógica ordinal .

Martin Davis afirma que, embora o uso de um oráculo de computação por Turing não seja o foco principal da dissertação, ele provou ser altamente influente na ciência da computação teórica , por exemplo, na hierarquia de tempo polinomial .

Referências

links externos


Ícone de esboço

Este artigo relacionado à lógica matemática é um esboço . Você pode ajudar a Wikipedia expandindo-a .
Ícone de esboço

Este artigo sobre uma publicação matemática é um esboço . Você pode ajudar a Wikipedia expandindo-a .