Dissertação

Space Bounded Scatter Machines EVALUATED

Neste trabalho estudamos o poder computacional de um modelo de computação abstracto quando limitado em espaço polinomial. O modelo de computação em estudo consiste numa máquina de Turing acoplada a uma experiência física como oráculo (a experiência de dispersão). Este modelo de computação (a máquina de dispersão) já está estudado em relação a restrições em tempo polinomial, de onde adaptamos a maioria das técnicas de prova usadas neste trabalho. Averiguamos quais seriam as funções para as quais podemos construir um relógio (uma máquina de Turing específica) em espaço polinomial. Existem relógios em espaço polinomial para funções com um crescimento no máximo exponencial. Apresentamos também um novo protocolo de comunicação (o protocolo generalizado) entre os componentes analógico e digital da máquina de dispersão que, neste caso, permite usar todo o poder computacional da experiência de dispersão como oráculo. Introduzimos uma classe de complexidade uniforme, que usamos como classe de suporte para uma classe de complexidade não uniforme necessária para descrever os resultados computacionais obtidos. Estabelecemos os resultados computacionais da máquina de dispersão limitada em espaço polinomial para ambas, a parede com vértice e para a parede diferenciável, utilizando em cada caso, ambos os protocolos de comunicação padrão e generalizado. Estabelecemos os resultados para os três casos de precisão usuais (precisão infinita, precisão ilimitada e precisão fixa), e em alguns casos da experiência com parede diferenciável obtivemos resultados diferentes dependendo de se usamos o relógio temporizador (relógio para limitar o tempo de execuçção da experiência) ou não.
Computação analógico-digital

Julho 19, 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