Распознавание языков на конечных вероятностных многоленточных и многоголовочных автоматах

М. О. Рабин [1] доказал, что на конечных вероятностных автоматах с изолированной точкой сечения можно распознавать только те языки, которые распознаваемы на конечных детерминированных автоматах. В настоящей работе для конечных автоматов со многими лентами или со многими головками на одной ленте доказан противоположный результат: существует язык, распознаваемый с вероятностью $1-\varepsilon$ для любого $\varepsilon>0$, но не распознаваемый детерминированно.