Autor(es): Gomes, Luís Mendes
Data: 2007
Identificador Persistente: http://hdl.handle.net/10400.3/118
Origem: Repositório da Universidade dos Açores
Assunto(s): Funções Reais Recursivas; Máquinas de Turing; Teoria da Computação; Real Recursive Functions; Turing Machines; Theory of Computation
Doutor in Informatics, speciality of Theory of Computation
Usando a teoria das funções reais recursivas, que deriva da proposta original em [Moo96], mostramos como cada função periódica definida por partes, que admite um desenvolvimento em série de Fourier, pode ser definida como uma destas funções reais recursivas. Demonstramos, também, que o poder computacional de um certo tipo de autómatos finitos em tempo contínuo está limitado à computação de sinais que são descritos por funções lineares parcialmente periódicas definidas por partes, as quais constituem um subconjunto muito restrito de sinais que podem ser gerados por funções reais recursivas. Uma função real recursiva com limites infinitos é apresentada para simular máquinas de Turing em tempo infinito, restrito a w2, bem como o seu poder computacional, nomeadamente para decidir as respectivas aproximações w2 aos problemas da paragem e, ainda, a hierarquia da aritmética recorrendo a um número finito de limites. Para isso, é introduzido um novo esquema de iteração nos ordinais até w2, que simula as máquinas de Turing em tempo infinito com a codificação para inputs binários finitos, introduzida por Christopher Moore, e o sistema de equações diferenciais da simulação da máquina de Turing, introduzido, recentemente, por Jerzy Mycka e José Félix Costa.
