Машина Тьюринга

 1.     Создать опорный конспект/лист/схему по теме, отражающий следующие вопросы:

• неформальное описание машины Тьюринга;
• внешний алфавит, алфавит состояний, функциональная схема, принцип работы машины Тьюринга.

2.      Ознакомьтесь с принципами работы в эмуляторе Машины Тьюринга (https://kpolyakov.spb.ru/prog/turing.htm).

3. В пособии (Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) - М.: МГУ, 2006. – 47 с.) изучить материал параграфа 1.2. 

4. На основе изученного материала решить задачу в эмуляторе машины Тьюринга:  Дано натуральное число 1>n . Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было "100", то выходным словом должно быть "99", а не "099". Автомат в состоянии q1 обозревает правую цифру числа.