Caros colegas e estudantes: gostaria de convidar a todos para a Sessão de Defesa de Tese de Doutorado do meu orientando Anderson de Araújo , nesta sexta-feira, 18 de março de 2011, no IFCH- UNICAMP.
Todos são muito bem-vindos; detalhes abaixo. Atenciosamente Walter Carnielli --------------------------------------------------------------------------------- Data: Sexta-feira, 18 de março de 2011 Horário: 14 horas Local: Secretaria de Pós-graduação do IFCH-UNICAMP, Sala de defesa de teses. Banca examinadora: Prof. Dr. Walter Carnielli (UNICAMP - Orientador) Prof. Dr. Antônio Mariano Nogueira Coelho (UFSC) Prof. Dr. Marcelo Finger (USP) Prof. Dr. Hugo Luiz Mariano (USP) Prof. Dr. Arnaldo Vieira Moura (UNICAMP) Suplentes: Prof. Dr. Francisco Antonio de Moraes Accioli Doria (UFRJ) Prof. Dr. Dirk Greimann (UFF) Prof. Dr. Ruy José Guerra Barretto de Queiroz (UFPE) 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. 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 obtidos 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 conseqüê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, no que diz respeito a certos métodos, para a possibilidade de solução desse problema central em complexidade computacional. 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. -- -- +++++++++++++++++++++++++++++++++++++++++++++++++ Prof. Dr. Walter Carnielli Director Centre for Logic, Epistemology and the History of Science – CLE State University of Campinas –UNICAMP 13083-859 Campinas -SP, Brazil Phone: (+55) (19) 3521-6517 Fax: (+55) (19) 3289-3269 e-mail: walter.carnie...@cle.unicamp.br Website: http://www.cle.unicamp.br/prof/carnielli _______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
