304
правки
Изменения
→Примеры машин Тьюринга: добавил пример с палиндромом, неформальное описание
== Примеры машин Тьюринга ==
=== Прибавление единицы ===
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
* в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
** <tex>\delta(R, 1) = \langle R, 1, \leftarrow \rangle</tex>
** <tex>\delta(R, B) = \langle Y, B, \rightarrow \rangle</tex>
=== Проверка того, является ли слово палиндромом ===
В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом <tex>\{0, 1\}</tex>. Алгоритм следующий:
* если строка на ленте — пустая, то перейти в допускающее состояние
* надо запомнить первый символ слова в состоянии автомата,
* стереть его,
* перейти в конец ленты:
** если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
** если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
** в случае несовпадения перейти в отвергающее состояние
