Màquina oràcul

En teoria de la complexitat i en la teoria de la computabilidad, una màquina oràcul és una màquina abstracta usada per a estudiar problemes de decisió. Pot ser visualisada com una màquina de Turing en una caixa negra, cridada oràcul, la qual pot decidir certs problemes de decisió en una simple operació. El problema pot ser qualsevol classe de complexitat. Inclús poden usar-se problemes indecidibles, com el problema de la parada.

Operacions

• alvançar el cabezal llector/escritor per a la dreta.
• alvançar el cabezal llector/escritor per a l'esquerra.

La màquina de Turing escriu en la seua cinta una entrada per a l'oràcul i seguidament este s'eixecuta, en un sol pas l'oràcul computa la funció, borra l'entrada i escriu l'eixida a la cinta. A voltes la màquina de Turing és descrita en dos cintes, una destinada a passar les entrades a l'oràcul i l'atra a rebre les eixides del mateix.

Classes

La classe de complexitat de problemes de decisió que poden ser resoltes per un algoritme en classe A en un oràcul per a un problema en classe B s'escriu de la següent forma: A^B. La notació A^B també significa la classe de problemes que resoldre per l'algoritme en classe A en un oràcul per al llenguage B. Les màquines oràcul són útils per a investigar la relació entre complexitat de classes, per eixemple entre P i NP, considerant la relació entre P^A i NP^A sent A un oràcul. En particular s'ha demostrat que existixen idiomes A i B a on P^A = NP^A, pero en canvi P^B ≠ NP^B.

És interessant considerar el cas en el que l'oràcul és elegit a l'encert d'entre tots els oràculs possibles. S'ha demostrat que si l'oràcul, verdaderament s'ha elegit a l'encert, llavors, en provabilitat d'1, P^A ≠ NP^A (Bennett, Gill, 1981). Quan una pregunta és verdadera para casi tots els oràculs, es diu que és certa per a qualsevol oràcul triat a l'encert. Per un atre costat, una sentència pot ser verdadera per a un oràcul a l'encert i en canvi falsa per a una màquina de Turing. Problemes de parades en oràculs:

És possible l'existència d'un oràcul que compute una funció no-computable, com per eixemple la resposta al problema de parada o problemes similars. Una màquina en un oràcul d'este tipo és una hipercomputadora. En hipercomputadora es fa referència a varis métodos proposts per a la computació de funcions no computables per màquines de Turing, este terme va ser introduït per primera volta per Jack Copeland.

Encara que poden determinar si una particular màquina de Turing es pararà en unes determinades entrades, no poden determinar si les màquines oràcul que detecten la parada també es pararan o no. Este fet crea una jerarquia de màquines, coneguda com la jerarquia aritmètica, en la qual cada una té un major potencial i a la seua volta un major problema de parada.

Vore també

• Màquina de Turing