Loading...
Publication
Applications of real recursive infinite limits
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 442.1 KB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
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.
Description
Doutor in Informatics, speciality of Theory of Computation
Keywords
Funções Reais Recursivas Máquinas de Turing Teoria da Computação Real Recursive Functions Turing Machines Theory of Computation