Siguiente: . Un nivel arriba: Computabilidad con mTp's Anterior: Computabilidad con mTp's

.

Proposición: Una función es computable probabilísticamente si y sólo si es computable Turing. Dem: ``si'': Las mT's son casos particulares de mTp's. Luego toda función computable Turing es computable probabilísticamente. ``sólo si'': Si f es computable probabilísticamente entonces para cada x puede encontrarase algorítmicamente a la y correspondiente tal que y=f(x). Este procedimiento atestigua a f como computable Turing.