210
правок
Изменения
м
Нет описания правки
'''Замечания''':
# <tex> V </tex> и <tex> P </tex> по очереди становятся активными. <tex> V </tex> активизируется первым. В течение работы <tex> V </tex> выполняет вычисления, используя вход, очередные данные с вероятностной ленты и сообщение, пришедшее от <tex> P </tex>, и пишет запрос <tex> P </tex>. Как только <tex> V </tex> написал сообщение, он дизактивируется, и <tex> P </tex> становится активным, если протокол не завершился. Любая машина может завершить выполнение протокола просто не посылая сообщение во время своей активной фазы. <tex> V </tex> принимает (или отвергает) вход, выводит '''true''' (или '''false''') и завершает выполнение протокола. Время работы <tex> V </tex> {{---}} это сумма времен работы, затраченных <tex> V </tex> в течение активной фазы, и это время ограничено полиномом от длины входа.
# <tex>V</tex>, обменивающийся сообщениями с фиксированным <tex>P</tex>, обозначим <tex>V_{P}</tex>.
# <tex> P </tex> может быть и вероятностной и детерминированной машиной Тьюринга. Так как он имеет неограниченные вычислительные ресурсы, то на каждом ходу он может выбрать такие вероятностные данные и произвести вычисления с ними, что они максимизируют вероятность принятия слова <tex> V </tex>.
