Dissertação

The computational power of infinite precision measurements EVALUATED

Nesta dissertação estudamos o poder computacional de Máquinas de Turing Analógica-Digitais que usam experiências físicas como oráculos, conseguindo assim fazer medições de números reais e portanto ultrapassando a barreira de Turing. A experiência física que consideramos é a Smooth Scatter Experiment, cujo tempo que demora a devolver a resposta depende do tamanho da query word. É possível limitar o tempo que esperamos pelo oráculo usando uma time schedule. Apesar de existir três tipos de protocolos de comunicação entre a parte analógica e a parte digital, apenas estudamos o protocolo de precisão infinita e apresentamos uma prova alternativa para o lower bound do poder computacional destas máquinas quando usam um time schedule exponencial. Além disso, analisamos a influência da natureza do time schedule quando fixamos a posição do vértice da Scatter Machine em y=1/2, caracterizando o poder computacional em termos de classes de complexidade não uniforme e completando a prova actual de quando o time schedule é um função computável.
Máquinas de Turing, Máquinas Analógica-Digitais, Time schedule, Complexidade não uniforme, Função computável, Função constructível no tempo.

Setembro 30, 2020, 10:0

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

Orientação

ORIENTADOR

José Félix Gomes da Costa

Departamento de Matemática (DM)

Professor Associado