Dissertação

Infinite Time Turing Machines EVALUATED

As máquinas de Turing em tempo infinito prolongam as operações das máquinas de Turing ordinárias para o tempo ordinal transfinito. Desta forma, obtemos um modelo natural de computabilidade infinita, e uma base téorica para o estudo do poder e das limitações dos chamados algoritmos para supertarefas. A teoria da computabilidade resultante, conduz a uma noção de computação sobre os reais, bem como a conceitos de decidibilidade e semi-decidibilidade sobre os reais e conjuntos de reais. É fácil verificar que todo o conjunto aritmético é decidível em tempo infinito por estas máquinas; um pouco mais de sofisticação mostra que todo o conjunto $\Pi^1_1$ é decidível em tempo infinito, e que os conjuntos semi-decidíveis são uma parte dos conjuntos $\Delta^1_2$. Neste trabalho iremos estudar a teoria das máquinas de Turing em tempo infinito e os desenvolvimentos recentes relacionados com a mesma. Estas máquinas fornecem um modelo natural de computabilidade infinita, com noções robustas de computabilidade e decidibilidade sobre os reais, enquanto permanecem próximas de conceitos clássicos de computabilidade. O estudo das máquinas de Turing em tempo infinito assenta cada vez mais na interacção de métodos provenientes de diversas áreas, tais como a teoria dos conjuntos, teoria descriptiva dos conjuntos e teoria da computabilidade. No último capitúlo mencionaremos alguns teoremas estruturais dos graus de Turing em tempo infinito, e o análogo ao teorema de Post em tempo infinito, e a recente solução negativa do problema P=NP no contexto infinito.
Computabilidade, Computação com Supertarefas, Máquinas de Turing em Tempo Infinito, Tempo Ordinal Transfinito.

Abril 18, 2008, 14:30

Documentos da dissertação ainda não disponíveis publicamente

Orientação

ORIENTADOR

António Marques Fernandes

Departamento de Matemática (DM)

Professor Auxiliar