Máquina de Turing probabilística

Máquina de Turing probabilística

En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad.

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 pude 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 sólo 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 yZPLP.

Los computadores cuánticos son otro modelo de cálculo que es inherentemente probabilístico.

Enlace externo


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Máquina de Turing probabilística — En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad. Una Máquina de Turing probabilística es una Máquina de Turing no determinista que selecciona aleatoriamente… …   Enciclopedia Universal

  • Turing (desambiguación) — Turing puede referirse a: Alan Turing. Fue un matemático, informático teórico, criptógrafo y filósofo inglés. Es considerado uno de los padres de la Ciencia de la computación siendo el precursor de la informática moderna. Test de Turing. Es una… …   Wikipedia Español

  • PP (clase de complejidad) — En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión, resoluble por una máquina de Turing probabilística, diferente de la máquina de Turing general o determinística… …   Wikipedia Español

  • Algoritmo no determinístico — Saltar a navegación, búsqueda En Ciencias de la computación, un algoritmo no determinístico es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un… …   Wikipedia Español

  • Algoritmo no determinista — En Ciencias de la computación, un algoritmo no determinístico es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinístico. Uso… …   Wikipedia Español

  • Teoría de la computabilidad — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Teorema de la jerarquía temporal — En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede …   Wikipedia Español

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

  • Inteligencia artificial — «IA» redirige aquí. Para otras acepciones, véase IA (desambiguación). Inteligencia artificial TOPIO, un robot humanoide, jugando tenis de mesa en Tokio International Robot Exhibition (IREX) 2009 …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”