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

Esta tese propõe uma nova abordagem da computabilidade de Turing clássica, denominada aborgadem 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. Em particular, 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.obtidos. Nessa direção, os resultados apresentados a respeito de propriedades tais como estabilidade, absoluticidade, universalidade e logicidade enfatizam as potencialidades da computabilidade modelo-teórica de primeira ordem. Em especial, demonstra-se que a lógica subjacente às teorias de Turing é uma lógica minimal intuicionista, 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 consequência, postula-se um princípio de internalidade 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, portanto, 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.