Máquinas de Turing não determinísticas com combinadora para a computação de funções

Abstract

Este trabalho aponta que as definições existentes de funções computadas por máquinas de Turing não determinísticas não permitem adaptar diretamente todos os problemas de decisão para funções e não justificam a obtenção, quando é, em tempo polinomial de suas saídas. Por esse motivo, propõe uma variação, baseada na associação de uma árvore de computação à estratégia de divisão e conquista, denominada máquina de Turing não determinística com combinadora, capaz dessa adaptação e com uma definição de tempo bem justificada. Além disso, exemplifica a variação proposta com máquinas que computam as funções das classes #P e OptP, as funções características dos complementos das linguagens decididas por máquinas de Turing não determinísticas e uma função que resolve o Problema de Deutsch-Jozsa.