Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»
Contenido eliminado Contenido añadido
Línea 33:
== Máquinas con Oráculo (O-Machines ó MTO's) ==
En primer lugar
De esta forma, seríamos capaces de encontrar una función que pudiera solucionar un problema NP-completo como, por ejemplo, el de la suma de un subconjunto. Incluso, podríamos descubrir que nos encontramos ante 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.
Línea 66 ⟶ 68:
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.
== Máquinas de Turing Probabilísticas (MTP)==
| |||