Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.3/118
Título: Applications of real recursive infinite limits
Autor: Gomes, Luís Mendes
Orientador: Costa, José Félix Gomes da
Palavras-chave: Funções Reais Recursivas
Máquinas de Turing
Teoria da Computação
Real Recursive Functions
Turing Machines
Theory of Computation
Data de Defesa: 8-Jun-2007
Resumo: 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.
Descrição: Doutor in Informatics, speciality of Theory of Computation
URI: http://hdl.handle.net/10400.3/118
Aparece nas colecções:DME - Teses de Doutoramento / Doctoral Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
DM_Doutor_Luis_Mendes_Gomes.pdf442,1 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.