В машинах Тьюринга «каждая инструкция машины Тьюринга детерминирована: учитывая внутреннее состояние и сканируемый символ, ближайшая следующая операция полностью и однозначно определена» (Ким 2011, стр. 143).
Однако вероятностная автоматизация не является детерминированной. Это значит, что
«текущее внутреннее состояние машины и символ, который она сканирует, не определяют — во всяком случае, не всегда — вместе однозначно определяют, что машина будет делать дальше». (Ким 2011, стр. 144).
Что здесь подразумевается под вероятностной автоматизацией в машинах Тьюринга?
Означает ли это, что вероятностные автоматы могут решить сложную задачу несколькими способами? Что нельзя определить, как автоматы решат задачу, а можно только рассчитать вероятность того, каким способом автоматы достигнут результата?
Ким, Дж. (2011) Философия разума [электронный ресурс] / Джегвон Ким. 3-е изд. Боулдер, Колорадо: Боулдер, Колорадо: Westview Press.
См. Вероятностную машину Тьюринга :
— недетерминированная машина Тьюринга, которая выбирает между доступными переходами в каждой точке в соответствии с некоторым распределением вероятностей.
Как следствие, вероятностная машина Тьюринга может (в отличие от детерминированной машины Тьюринга) иметь стохастические результаты; на данном автомате ввода и инструкции он может иметь разное время выполнения или вообще не останавливаться; кроме того, он может принять ввод в одном исполнении и отклонить тот же ввод в другом выполнении.
С другой стороны, машина Тьюринга может запускать программу, «поведение» которой мы не можем определить не потому, что она не детерминирована, а потому, что нам чрезвычайно трудно ее понять либо потому, что она сложна, либо потому, что мы не понимали последствий программы. когда мы его запрограммировали.
Конифолд