Целью данного занятия является закрепление знаний по построению и работе машин Тьюринга, которые являются математическими (формальными) моделями алгоритмов.

Задание 1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.

Задание 2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.

Задание 3. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если число единиц в записи числа нечетное, и в состоянии NO – в противном случае.

Задание 4. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если в записи числа имеется три подряд идущих единицы, и в состоянии NO – в противном случае.

Задание 5. Построить машину Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.

Задание 6. Построить машину Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.

Общий вопрос. Оценить, как изменяется число тактов (по какому закону), совершаемых машиной при линейном увеличении размерности входного слова. В качестве примера взять Задание 1 и Задание 2. (Следует показать, что время работы также возрастает линейно).

[остальное в файле ниже]