Como as máquinas de Turing não determinísticas calculam problemas gerais de função?

(Espero que isso não tenha sido solicitado antes, mas não encontrei nada.)

No meu entendimento, o não determinismo se aplica apenas a problemas de decisão, devido à exigência da existência de um caminho de aceitação . Na Wikipedia, a classe$NP$-easy é definido como solucionável em poltime determinístico, com acesso a um oráculo para um problema de decisão em NP. Então isso parece apoiar minha suposição.

Minha pergunta é: Existe uma maneira aceita de definir uma máquina de Turing não determinística para calcular um problema geral de função? (E é sempre por um desvio em um oráculo por um problema de decisão?)

Uma definição aceita é a seguinte: uma função $f$ (cuja saída é no máximo polinomial em sua entrada) está na classe $\mathsf{FNP}$ se dado $x,y$ pode-se decidir em tempo polinomial se $f(x)=y$. Compare isso com a classe$\mathsf{FP}$, que contém essas funções $f$ tal que dado $x$, o valor de $f(x)$ pode ser calculado em tempo polinomial.

Primeiro, sempre que você fala sobre não determinismo, precisa se livrar da ideia de ter um algoritmo que executa para obter um resultado. Modelos não determinísticos são apenas descritivos, não operacionais; não há como "executar" um algoritmo não determinístico. Às vezes, os professores dizem coisas como "a máquina sempre acha acertada" ou "executamos todos os ramos em paralelo", mas essas declarações de intuição ficam aquém de uma maneira ou de outra.

Portanto, aceite que uma máquina não determinística descreve algum objeto formal. Período.

Existem duas maneiras de obter intuição sobre autômatos não determinísticos. Na extremidade inferior, considere transdutores de estado finito . São essencialmente autômatos finitos com saída; obviamente, a FA reduz a eles. No caso não determinístico, cada entrada pode (mas não precisa!) Resultar em várias saídas. Portanto, faz sentido definir o "resultado" de um TF$A$ em $w$ como o conjunto de todas as saídas $A$ pode produzir em $w$. Agora você pode alegremente assumir a união por várias palavras de entrada ou considerar pré-imagens, e assim por diante.

Do outro lado do espectro, considere NTM. A mesma idéia funciona: para cada entrada$w$, defina como saída o conjunto de todo o conteúdo da fita que você pode ter quando a máquina parar (em um estado de aceitação) em $w$.

Observe que nada impede que você exija que o autômato tenha apenas uma saída por entrada, por exemplo, ao definir uma classe de complexidade.

É semelhante para restrições de recursos; as idéias usadas para definir classes de problemas de decisão devem, em grande parte, continuar.