Uma abordagem modelo-teórica da computabilidade de Turing clássica

Autor(es)

Anderson Araújo

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Filosofia e Ciências Humanas
• Data de defesa: 2011-03-18

Membros da banca

Walter Alexandre Carnielli; Antônio Mariano Nogueira Coelho; Marcelo Finger; Hugo Luiz Mariano; Arnaldo Vieira Moura

• Orientador: Walter Alexandre Carnielli

Resumo

Esta tese propõe uma nova abordagem da computabilidade de Turing clássica, denominada abordagem modelo-teórica. De acordo com essa abordagem, estruturas e teorias são associadas às máquinas de Turing a fim de investigar as características de suas computações. Uma abordagem modelo-teórica da computabilidade de Turing através da lógica de primeira ordem é desenvolvida, e resultados de correspondência, correção, representação e completude entre máquinas, estruturas e teorias de Turing são demonstrados. Nessa direção, os resultados obtidos a respeito de propriedades tais como estabilidade, absoluticidade, universalidade e logicidade enfatizam as potencialidades da computabilidade modelo-teórica de primeira ordem. Demonstra-se que a lógica subjacente às teorias de Turing é uma lógica minimal intuicio-nista, sendo capaz, inclusive, de internalizar um operador de negação clássico. As técnicas formuladas nesta tese permitem, sobretudo, investigar a computabilidade de Turing em modelos não-padrão da aritmética. Nesse contexto, uma nova perspectiva acerca do fenômeno de Tennenbaum e uma avaliação crítica da abordagem de Dershowitz e Gurevich da tese de Church-Turing sào apresentadas. Como conseqüência, postula-se um princípio de interna-lidade aritmética na computabilidade, segundo o qual o próprio conceito de computação é relativo ao modelo aritmético em que as máquinas de Turing operam. Assim, a tese unifica as caracterizações modelo-aritméticas do problema P versus NP existentes na literatura, revelando, por fim, uma barreira modelo-aritmética para a possibilidade de solução desse problema central em complexidade computacional no que diz respeito a certos métodos. Em sua totalidade, a tese sustenta que características cruciais do conceito de computação podem ser vislumbradas a partir da dualidade entre finitude e infinitude presente na distinção entre números naturais padrão e não-padrão (AU)

• Processo FAPESP: 08/06205-5 - Aspectos lógicos e ontológicos de uma aritmética generalizada
• Beneficiário: Anderson Beraldo de Araújo
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto