Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»
Contenido eliminado Contenido añadido
Línea 85:
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, tal como se muestra en la siguiente figura:
((Falta subir la imagen))
Podemos observar como cada posible estado tiene asociado una probabilidad. Además, la suma de dicha probabilidad siempre debe darnos uno.
Cabe destacar que las MTP’s nos permiten resolver rápidamente problemas que en una máquina de Turing clásica tardarían mucho tiempo. Sin embargo, debemos resaltar que una MTP no aumenta el tamaño de las clases de las funciones computables.
Además, una MTP puede simular el funcionamiento de una Máquina de Turing (MT) para lo cual tendrá que simular, uno a uno, todos los posibles caminos correspondientes a los diferentes valores que se pueden obtener (Giuliano Benenti, 2004; Gill, 1974).
Leew, Moore, Shannon y Shapirio propusieron el primer modelo de MTP en 1955; en seguida, empezaron a surgir otros trabajos como el de Rabin en 1963 o el de Gill en 1974.
Asimismo, también podemos definir las Máquinas de Turing Probabilísticas como máquinas deterministas. Para ello deberemos añadir la instrucción “write”, de tal forma que el valor de la escritura quede distribuido, de manera uniforme, en el alfabeto que reconoce la máquina.
Como consecuencia de este hecho, una MTP puede proporcionarnos un resultado estocástico, es decir, dado un programa para la máquina, al que le asociamos una determinada entrada, puede ocurrir que el programa se ejecute en tiempos variables o, incluso, que no llegue a parar; incluso, puede que durante una ejecución acepte una determinada entrada y no la admita en la siguiente ejecución.
Por tanto, podemos concluir que podemos definir de diferentes formas la entrada en una MTP. Las clases de complejidad que incluyen RP, Co-RP, BPP y ZPP hacen referencia a dichas formas. Además, como es necesario restringir la máquina a usar tiempo logarítmico (en vez de polinómico que es lo habitual), es necesario definir una serie de clases análogas llamadas RL, Co-RL, BPL y ZPL. Si incluimos ambas restricciones obtendremos las clases RLP, Co-RLP, BPLP y ZPLP.
Cabe destacar que el modelo de cálculo que utilizan los computadores cuánticos es substancialmente probabilístico.
Esta es una forma de definir una MTP. Sin embargo, otros autores proponen otras definiciones.
Por ejemplo, Song Yan (Yan, 2002) define una MTP como una MT no determinista que contiene una serie de estados especiales llamados “coin-tossing states”. Para cada uno de estos estados se determinan dos estados posibles. Sin embargo, este concepto no resulta muy diferente de la definición que hemos utilizado anteriormente.
Giuliano Beneti define una máquina similar a la que utiliza Yan donde cada posibilidad tiene asociada una probabilidad de ½, de tal forma que cada estado tiene una probabilidad P de ser elegido y 1-P de no ser escogido. Esta máquina resulta difícil de simular.
Ja Mika Hirvensalo (Hirvensalo, 2004) y Colin P. Williams (Williams y Clearwater 1999), consideran una version más genérica de la MTP donde a partir de cada uno de los estados por los que pasa la máquina podemos obtener una serie de estados a los que nos podemos desplazar cuya suma de las probabilidades asociadas es uno. Una vez más, esta concepción de MTP no es muy diferente de la que hemos comentado originalmente.
| |||