Una Máquina de Turing probabilística es una Máquina de Turing, en concreto de la forma no determinista, que selecciona aleatoriamente entre las transiciones disponibles en cada punto con idéntica probabilidad para cada alternativa.
Alternativamente, se puede definir también como una máquina de Turing determinista con una instrucción adicional “escribir” donde el valor de la escritura está uniformemente distribuido en el alfabeto de la máquina.
Como consecuencia, una máquina de Turing probabilística puede (a diferencia de una máquina de Turing) tener un resultado estocástico: Dada una entrada y un programa para la máquina, puede ejecutar el programa en tiempos variables de ejecución o puede no parar; más aún, puede aceptar una entrada en una ejecución y no aceptarla en la siguiente.
Se desprende que la aceptación de una cadena de entrada en una máquina de Turing probabilística puede ser definida de varias formas. Y a esas formas de terminar corresponden diferentes clases de complejidad que incluyen RP, Co-RP. BPP y ZPP. Al restringirse la máquina a solo usar espacio logarítmico en lugar de tiempo polinómico, se definen las clases análogas RL, Co-RL, BPL, y ZPL. Al incluir ambas restricciones se obtienen las clases RLP, Co-RPL, BPLP y ZPLP.
NIST Página sobre máquinas de Turing probabilísticas
Datos:Q1191836
Diciembre 21, 2021
máquina, turing, probabilística, teoría, complejidad, computacional, utilizan, máquinas, turing, probabilísticas, para, definir, diferentes, clases, complejidad, máquina, turing, concreto, forma, determinista, selecciona, aleatoriamente, entre, transiciones, d. En Teoria de la complejidad computacional se utilizan Maquinas de Turing probabilisticas para definir diferentes clases de complejidad Una Maquina de Turing probabilistica es una Maquina de Turing en concreto de la forma no determinista que selecciona aleatoriamente entre las transiciones disponibles en cada punto con identica probabilidad para cada alternativa Alternativamente se puede definir tambien como una maquina de Turing determinista con una instruccion adicional escribir donde el valor de la escritura esta uniformemente distribuido en el alfabeto de la maquina Como consecuencia una maquina de Turing probabilistica puede a diferencia de una maquina de Turing tener un resultado estocastico Dada una entrada y un programa para la maquina puede ejecutar el programa en tiempos variables de ejecucion o puede no parar mas aun puede aceptar una entrada en una ejecucion y no aceptarla en la siguiente Se desprende que la aceptacion de una cadena de entrada en una maquina de Turing probabilistica puede ser definida de varias formas Y a esas formas de terminar corresponden diferentes clases de complejidad que incluyen RP Co RP BPP y ZPP Al restringirse la maquina a solo usar espacio logaritmico en lugar de tiempo polinomico se definen las clases analogas RL Co RL BPL y ZPL Al incluir ambas restricciones se obtienen las clases RLP Co RPL BPLP y ZPLP Los computadores cuanticos son otro modelo de calculo que es inherentemente probabilistico Vease tambien EditarMaquina de Turing Maquina universal de Turing Maquina de Turing alternante Alan TuringEnlaces externos EditarNIST Pagina sobre maquinas de Turing probabilisticas Datos Q1191836 Obtenido de https es wikipedia org w index php title Maquina de Turing probabilistica amp oldid 128466739, wikipedia, wiki, leyendo, leer, libro, biblioteca,
