What are the relation between Probabilistic Turing Machine and Turing Machine of every hierarchy, for instance, are the Probabilistic PDA and NPDA equivalent? the Probabilistic LBA and LBA equivalent?etc. please give me the reference which prove those result, thanks in advance.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Simultaneously cross-posted at cstheory.stackexchange.com/questions/46681/… . $\endgroup$– Emil JeřábekCommented Apr 20, 2020 at 6:39
-
$\begingroup$ @EmilJeřábek thank you for your reminding, deleted the one of cstheory $\endgroup$– XL _At_Here_ThereCommented Apr 20, 2020 at 11:21
Add a comment
|