|
== Máquinas de Turing Probabilísticas (MTP)==
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.
Podemos observar como cada posible estado tiene asociado una probabilidad. Además, la suma de dichaestas probabilidadprobabilidades siempre debe darnossumar uno.
Cabe destacar que las MTP’s nos permiten resolver rápidamente problemas que en una máquina de Turing clásicatradicional tardarían mucho tiempo en resolverse. Sin embargo, debemos resaltar que una MTP no aumenta el tamaño de las clases de las funciones computablesque se pueden computar.
AdemásAsimismo, 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énTambién podemos definir las Máquinas de Turing Probabilísticas como máquinas deterministas. Para ello deberemos añadir la instrucción “write”''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 tiemposdiferentes variablestiempos o, incluso, que no llegue a parar; inclusoy aunque parezca increíble, puede que durante una ejecución acepte una determinada entrada y no la admita endurante la siguiente ejecución.
Por tanto, podemos concluir que podemos definir de diferentes formas la entrada ena 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.
CabeEs importante 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.
| 