Siguiente: . Un nivel arriba: Máquinas-p Anterior: .

Computabilidad con mTp's

Dada una $\frac{1}{2}$-mTp M para una entrada $x\in \Sigma^*$ a M(x) la podemos considerar como una variable aleatoria

$$M(x):[1,n]^*\rightarrow \Sigma^*.$$

La función calculada por M es la función

$$f_M:x\mapsto\left\{\begin{array}{ll} y &\mbox{\rm si Prob}\... ... \perp &\mbox{\rm si no existiera tal $y$.} \end{array}\right.$$

Recíprocamente, f es computable probabilísticamente si existe una $\frac{1}{2}$-mTp M tal que f=f_M.