Computação Paraconsiente: uma Abordagem Lógica à Computação Quântica

Neste trabalho mostramos evidências de que a complexidade algoritmica pode ser vista como relativa a lógica, introduzindo novos modelos de computação através de lógicas não-clássicas e estudando suas características quanto a eficiência. Desde esta visão, sugerimos um novo caminho para estudar a eficiência dos modelos de computação quânticos, consistindo na ánálise da lógica subjacente a tais modelos. O conteúdo da tese está estruturado da seguinte maneira: no primeiro capítulo apresentamos uma análise conceitual da noção de """"computação"""", indicando como este conceito tem mudado desde os trabalhos fundacionais da década de 1930 e discutindo se ele deve ser considerado um conceito puramente físico ou lógico-matemático. No Capítulo 2, introduzimos dois modelos de """"máquinas de Turing paraconsistentes"""", usando sistemas lógicos diferentes e obtendo modelos com diferentes poderes computacionais (quanto a eficiência); tal resultado constitui uma primeira evidência a favor da relatividade lógica da computação que queremos defender. Outra evidência na mesma direção é apresentada no Capítulo 3, através da generalização dos circuitos booleanos para lógicas não-clássicas, em particular para a lógica paraconsistente mbC e para a lógica modal S5, e da análise do poder computacional de tais generalizações. O Capítulo 4 consiste numa introdução à computação quântica, para logo (no Capítulo 5) estabelecer algumas relações entre modelos de computação quântica e modelos de computação paraconsistente, de maneira a propor uma interpretação lógica dos modelos quânticos. No capítulo final (Capítulo 6) descrevemos várias relações entre mecânica quântica e lógica paraconsistente, relações estas que sugerem grandes potencialidades da abordagem paraconsistente dos fenômenos quânticos e que incitam a continuar explorando esta alternativa.