Máquina oráculo

La máquina de Turing escribe en su cinta una entrada para el oráculo y seguidamente este se ejecuta, en un solo paso el oráculo computa la función, borra la entrada y escribe la salida a la cinta.Las máquinas oráculo son útiles para investigar la relación entre complejidad de clases, por ejemplo entre P y NP, considerando la relación entre P^A y NP^A siendo A un oráculo.En particular se ha demostrado que existen idiomas A y B donde P^A = NP^A, pero en cambio P^B ≠ NP^B.Con hipercomputadora se hace referencia a varios métodos propuestos para la computación de funciones no computables por máquinas de Turing, este término fue introducido por primera vez por Jack Copeland.Este hecho crea una jerarquía de máquinas, conocida como la jerarquía aritmética, en la cual cada una tiene un mayor potencial y a su vez un mayor problema de parada.