Введение в задачу 0:11 Казбек представляет задачу увеличения натурального числа на единицу с помощью машины Тьюринга. Машина Тьюринга - абстрактная машина с бесконечной лентой и программируемым автоматом.
Описание машины Тьюринга 0:48 Машина Тьюринга состоит из бесконечной ленты, программируемого автомата и головки. Головка может перемещаться вправо, влево или оставаться на месте, записывать символы на ленту и менять состояние автомата.
Пример задачи 3:02 Машина Тьюринга должна увеличить число на единицу, за исключением числа 9, которое должно стать 0. Головка в состоянии К1 обозревает правую цифру числа и увеличивает её на единицу.
Программирование машины Тьюринга 5:45 Машина Тьюринга начинается с состояния К1 и завершает работу в состоянии К0. Головка записывает символ на ленту и может перемещаться вправо, влево или оставаться на месте.
Пример работы программы 8:00 Программа увеличивает число на единицу, за исключением числа 9, которое становится 0. Головка перемещается влево и увеличивает предыдущее число на единицу.
Обработка пустых символов 10:15 Если головка попадает на пустой символ, программа записывает единицу. Это происходит только при числе, состоящем из одних девяток.
Тестирование программы 11:54 Казбек демонстрирует работу программы на примерах чисел 1000, 1999 и 9999. Программа увеличивает число на единицу и завершает работу.
