Введение в машину Тьюринга 0:07 Машина Тьюринга состоит из бесконечной ленты, алфавита языка и таблицы состояний. Лента может сдвигаться в обе стороны бесконечно. Алфавит должен быть конечным, например, десятичный или русский.
Структура таблицы состояний 1:18 Таблица состояний содержит индексы и элементы алфавита. Пример программы взят с сайта Константина Полякова.
Задача замены символов 1:58 Задача: заменить все нули на единицы и все единицы на нули в двоичной записи числа. Каретка стоит слева от числа. Алфавит состоит из нуля, единицы и пробела.
Реализация программы 3:07 В таблице указываются три параметра: замена символа, сдвиг вправо или влево, переход в новое состояние. Пробел не заменяется, сдвигается вправо и переходит в состояние ку-2. Нолик заменяется на единицу, единица — на ноль.
Завершение программы 6:19 Если встречен пробел, программа останавливается. Нулевое состояние означает «стоп».
Усложнение задачи 7:19 Добавление состояния ку-3 для возврата каретки к левому символу. При встрече пробела в конце программа возвращается к началу.
Заключение 8:28 Демонстрация работы машины Тьюринга. Приглашение к дальнейшему изучению более сложных задач.
