Máquina oráculo
De Wikipedia, la enciclopedia encyclopedia
En teoría de la complejidad y en la teoría de la computabilidad, una máquina oráculo es una máquina abstracta usada para estudiar problemas de decisión. Puede ser visualizada como una máquina de Turing con una caja negra, llamada oráculo, la cual puede decidir ciertos problemas de decisión en una simple operación. El problema puede ser cualquier clase de complejidad. Incluso pueden usarse problemas indecidibles, como el problema de la parada.
Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. |