для функции копирования, не увеличивая
Задача 9.1. Постройте м.Т. для функции копирования, не увеличивая исходный алфавит ?.
Задача 9.2. Постройте программу м.Т., которая выполняла бы перенос непустого слова в заданное место ленты, т.е. для любого слова w
Задача 9.3. Достройте программу м.Т.
Задача 9.4. Докажите, что односторонняя м.Т.
Задача 9.5. Другой, по сравнению с конструкцией леммы 9.2, подход к моделированию двухсторонней ленты на односторонней заключается в том, чтобы содержимое правой полуленты
Задача 9.6. Достройте программу м.Т.
Задача 9.7. Построить программы машин Тьюринга, вычисляющих следующие функции.
- Перевод из двоичной системы в унарную: fbu(n(2))= |n.
- Сложение и вычитание в двоичной системе: sum(n*m)=n+m и совпадает с - при n
m и
при m > n).
- Умножение в двоичной системе: mul(n*m)= n ? m. ( Реализуйте алгоритм умножения "в столбик".)
- Возведение в степень: exp(n*m)= nm.
- Извлечение квадратного корня: .
- Логарифмирование: log(n)=log2n
.
- Деление:
- Остаток от деления: rest(n*m) = n mod m.
- Функция выбора аргумента: .
Задача 9.8. Используя машины Тьюринга из предыдущей задачи, построить программы машин Тьюринга, вычисляющих следующие функции.
Задача 9.9. Докажите, что всякую арифметическую функцию f(x), вычислимую на некоторой м. Т. M = <Q, ?, P,q0, qf>, можно также вычислить на м. Т. M',, алфавит ленты которой содержит лишь два символа
Задача 9.10.
Построить машину Тьюринга, определяющую по слову x в алфавите {1, 2} симметрично ли оно, т. е. вычисляющую функцию:
Задача 9.11.
Построить машину Тьюринга, сравнивающую два слова x=x1x2… xn и y=y1y2… ym в алфавите {1, 2, 3} лексикографически:
