Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»
Contenido eliminado Contenido añadido
Sin resumen de edición |
|||
Línea 28:
Finalmente, el cursor es el elemento que nos permite comunicar la unidad de memoria y el procesador. Para almacenar su posición dentro de la cinta utilizamos una variable entera. Cabe destacar, que el cursor sólo puede procesar un elemento de la cinta por unidad de tiempo.
== Máquinas con Oráculo (O-Machines o MTO's) ==
En primer lugar es necesario decir que tanto en la teoría de la complejidad como en la de la computabilidad, el término oráculo se define como una ''caja negra'' que nos permite computar una función en un sólo paso. Por tanto, podríamos encontrarnos con una función que es capaz de solucionar un problema NP-completo como, por ejemplo, el de la suma de un subconjunto. Incluso podría tratarse de una función no computable (es decir, no recurrente) como, por ejemplo, el problema de la parada.
Las máquinas de Turing con oráculo o MTO nos permiten resolver los problemas planteados, utilizando para ello información adicional. Además, estas máquinas fueron concebidas por Turing para poder estudiar aquellos problemas que carecen de solución algorítmica.
La MTO es una máquina de Turing conectada a un oráculo que es capaz de determinar si un elemento pertenece a un conjunto específico de números naturales. Asimismo, esta máquina presenta tres estados especiales:
| |||