Контрольные вопросы и задания

1. Из каких элементов состоит команда машины Тьюринга? Что собой представляет программа машины Тьюринга?

2. Где и в какой форме записываются исходные данные для работы машины Тьюринга?

3. Каковы условия остановки – прекращения работы машины Тьюринга? Где и в какой форме записан результат работы машины Тьюринга?

4. Может ли машина Тьюринга никогда не останавливаться? Как интерпретировать бесконечную работу машины Тьюринга?

5. В какой форме представлены исходные данные и результаты работы нормального алгорифма Маркова?

6. Может ли процесс подстановок при работе алгорифма Маркова никогда не завершаться?

7. Могут ли метасимволы встречаться в словах – исходных данных и результатах работы нормальных алгорифмов Маркова? Какова роль метасимволов в описании алгорифма?

Задачи для самостоятельного решения

1. Напишите программу машины Тьюринга для вычисления функции f(x) = x + 2 в алфавите A = {e, 0, 1}. Код числа x размещен на ленте перед началом вычислений. Незначащих нулей слева нет. Начальное положение головки машины – напротив первой слева значащей цифры 1. Конечное положение – стандартное, напротив первой слева цифры 1. Незначащих нулей результата по окончании программы не образуется.

2. Напишите программу машины Тьюринга для вычисления функции f(x₁ , x₂) = x₁ + x₂ в алфавите A = {e, 1}. Коды чисел x₁ и x₂ размещены на ленте перед началом вычислений и разделены одним пустым символом e. Начальное положение головки машины – напротив первой слева цифры числа x₁ .

3. Напишите программу машины Тьюринга для вычисления функции f(x) = 2  x в алфавите A = {e, 1}. Код числа x размещен на ленте перед началом вычислений. Конечное положение – стандартное, напротив первой слева цифры 1.

4. Выведите формулу для сложности программы машины Тьюринга, вычисляющей значение функции f(x) = x + 1 в алфавите A = {e, 0, 1}. За единицу времени выполнения берется время выполнения одной команды, включая изменение состояния, запись символа на ленту и сдвиг головки (если требуется).

5. Напишите семейство программ машины Тьюринга для вычисления функции f(x) = k  x в алфавите A = {e, 1}. Здесь k – некоторая константа, не размещаемая на ленте машины. Оцените сложность как функцию двух параметров k и x.

6. Напишите программу машины Тьюринга для вычисления функции f(x) = 3  x в алфавите A = {e, 0, 1, 2}.

7. Разработайте нормальный алгорифм Маркова для вычисления функции f(x) = x + 1 в алфавите A = {1}. Исходное значение x задано словом W, представляющим собой код x в единичной системе счисления.

8. Разработайте нормальный алгорифм Маркова для вычисления функции f(x₁ , x₂) = x₁ + x₂ в алфавите A = {1, +}. Исходное слово W представляет собой последовательность кодов x₁ и x₂ в единичной системе счисления, разделенных символом «+». Результат работы должен представлять собой код суммы чисел x₁ и x₂.

9. Разработайте нормальный алгорифм Маркова, инвертирующий слово W, т.е. записывающий символы, входящие в слово W, в обратном порядке. При необходимости введите дополнительные (вспомогательные) символы в алфавит A.

10. Оцените сложность нормальных алгорифмов Маркова из задач 8 и 9.

11. Разработайте программу машины Тьюринга для инвертирования слова, записанного на ленте. Проведите сравнение с алгорифмом Маркова.