Вариант 7 . ЗАДАЧИ МАТЕМАТИКА (Теория вычислительных алгоритмов или теория дискретных функций)
Вариант 7
1) Даны два целых положительных числа в десятичной системе счисления, разделенных знаком “+”. Построить машину Тьюринга, вычисляющую сумму этих чисел. Начальное положение – стандартное.
2) Построить машину Тьюринга, правильно вычисляющую функцию 𝑓(𝑥) = 5 − 𝑥.
3) Используя машины Тьюринга: левый сдвиг Б- , правый сдвиг Б+, транспозицию В, удвоение Г и обнуление Z, - построить машину Тьюринга, переводящую конфигурацию 𝑞101 𝑥01 𝑦01 𝑧 в конфигурацию 𝑞001 𝑧01 𝑦01 𝑧01 𝑦01 𝑧01 𝑦 .
4) Какой аналитический вид имеет функция, являющаяся результатом применения операции рекурсии: f(x,0)=g(x), f(x,y+1)=h(x,y,f(x,y)), если g(x)=x; h(x,y,z)=x+3z.
5) Какой аналитический вид имеет функция, являющаяся результатом применения оператора минимизации по z к функции h(x,y,z)=x-yz.
6) Получить из исходных функций с помощью основных операций функцию f(x,y)=(x+y) 2
