Участник:Темирлан/Машина Тьюринга. Количество

Материал из DISCOPAL
< Участник:Темирлан
Версия от 12:44, 23 марта 2017; Темирлан (обсуждение | вклад) (Новая страница: «Определение из wiki: Конкретная машина Тьюринга задаётся перечислением элементов множест…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение из wiki: Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Для выбора начального и конечного состояния есть способ выбора. Для каждой конфигурации (кроме конфигураций с конечным состоянием)- пары буква-состояние - есть способ выбора следующей конфигурации. Значит, есть всего ДТМ.