Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»
Contenido eliminado Contenido añadido
Línea 77:
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 ==
Las máquinas de Turing probabilísticas se utilizan, en la teoría de la complejidad computacional, principalmente para detallar las diferentes clases de complejidad existentes.
Se trata de máquinas no deterministas que toman decisiones aleatoriamente. De manera informal, podemos definir una Máquina de Turing Probabilística (MTP) como una máquina en el que las decisiones se toman en base a una determinada probabilidad. Por simplicidad, podemos asumir que en, cada paso, la máquina tiene únicamente dos estados a los cuales se les asocia una probabilidad de ½. Este hecho, implica que al computar un problema de tamaño k obtenemos una probabilidad de 2-k (Herken, 1994).
Es decir, cada transacción tiene asociada la misma probabilidad:
| |||