Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»
Contenido eliminado Contenido añadido
Línea 57:
((Falta subir el dibujo))
A partir de los conceptos introducidos anteriormente, intuitivamente podemos afirmar que una MTO puede resolver el problema de la parada. Para ello, basta con facilitarle el alfabeto correspondiente a dicho problema. Este tipo de máquinas nos permite descubrir si para una determinada entrada ''n'', la máquina se va a detener o no:
• Si no se detiene entonces la salida de la Máquina con Oráculo debe ser cero.
• Si se detiene retornará el resultado pertinente.
El problema de la parada se suele utilizar en la teoría de la recursión, puesto que nos permite describir los diferentes niveles de computabilidad existentes. De esta manera si podemos computar un conjunto en una MTO con un determinado oráculo, que denotaremos por la letra H, entonces podemos decir que es computable en H o recursiva en H.
Podemos considerar una máquina de Turing como un caso particular de una O-Machine. Para ello basta con imaginar una máquina de Turing con un oráculo vacío. Por tanto, este tipo de máquinas incrementan, de manera obvia, el poder computacional de una máquina de Turing clásica. Además, las MTO’s permiten computar todas las funciones recursivamente enumerables.
Una propiedad sumamente interesante de las MTO’s es que podemos encontrar una máquina oráculo que compute una determinada función definida de N en N. Sin embargo, no podemos construir una O-Machine que sea capaz de computar cualquier tipo de función definida de N en N.
Esta paradoja se debe a que una Máquina Oráculo está formada por una Máquina de Turing clásica (es decir, una máquina de Turing formada por una serie tanto de transiciones finitas como de estados) y un oráculo (es decir, un conjunto, posiblemente, infinito de números). Esto nos permite trivializar la computación que ha sido generalizada, es decir, si pudiéramos elegir el oráculo en función de la definición de la función, entonces podríamos usar el oráculo para realizar búsquedas infinitas de símbolos.
A pesar de esta limitación, la noción de O-Machine resulta interesante y presenta unos fundamentos sólidos, puesto que nos permite resolver funciones utilizando para ello un oráculo determinado.
| |||