Siguiente: . Un nivel arriba: Máquinas probabilísticas Anterior: Máquinas del tipo 1

Máquinas-p

Sea $p\in [0,1]$. Una p-máquina de Turing probabilística, (p-mTp), es una mTnd M modificada de manera que en su árbol de computaciones:

• cada nodo no terminal posee exactamente dos hijos,
• cada arista tiene uno de dos pesos numéricos $p,1-p\in [0,1]$, y la suma de los pesos de las aristas que emanan de cada nodo es 1,
• el conjunto de nodos terminales es la unión disjunta de nodos de aceptación y de nodos de rechazo,
  
  $$\mbox{\rm Terminales} = \mbox{\rm Aceptantes}\cup\mbox{\rm Rechazantes},$$
  
  
  y
• toda computación es terminal.

El lenguaje reconocido por M es L si y sólo si

$$\begin{array}{rrcl} \bullet & \forall \mbox{\bf x}&:& \mbox{... ...htarrow\; \rho_M(\mbox{\bf x})\leq 1-p,\vspace{2ex} \end{array}$$

Escribiremos L=L(M).