Dissertação

The Power of Unreliability in Analogue-digital Computation EVALUATED

Nesta dissertação continuamos a desenvolver o estudo de um modelo de computação analógico-digital, onde experiências físicas são usadas por máquinas de Turing como oráculos, permitindo que estas executem medições sobre os reais, e tornano possível a quebra da barreira de Turing. Considera-se uma experiência física particular, a smooth scatter experiment. Após executar consultas à experiência, a máquina aguarda um número de passos de tempo determinados por alguma função que lhe é interna, o time schedule. Dois protocols de comunicação entre a experiência e a máquina de Turing são considerados, os protocolos de precisão finita e infinita. Ao longo deste trabalho analizamos as diferenças fundamentais entre lidar com um protocolo ou com o outro. Em primeiro lugar, procuramos determinar o que sucede ao poder computacional da máquina de Turing analógico-digital quando consideramos time schedules possivelmente não computáveis, e quando tornamos a informação que pode ser medida através da experiência redundante. Um novo protocolo é introduzido, o protocolo de precisão triangular, relacionado com o caso da precisão finita, e a influência deste novo protocolo sobre o que estes sistemas podem decidir é examinado. Ademais, estudamos o efeito de utilizar classes ascendentes de time schedules supra-exponenciais no poder deste paradigma computacional. Diferenças drásticas são encontradas nos resultados para as precisões infinita e triangular, evidenciando algumas dissimilaridades fundamentais entre a utilização destes protocolos.
Máquinas de Turing, Computação analógico-digital, Oráculos físicos, Complexidade não-uniforme, Hipercomputação

Dezembro 4, 2017, 15:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

José Félix Gomes da Costa

Departamento de Matemática (DM)

Professor Associado