Контрольная работа

Контрольная работа по теории алгоритмов.
Выбор варианта по зачетной книжке – 4 цифра
Задание 1
А) Построить машину Тьюринга, применимую ко всем словам x1 x2…xn в алфавите {a,b,λ} .
В) Проверить работу машины Тьюринга над некоторыми словами. Варианты задания приведены в таблице
№ α
1 x1 x2…xn-1xn λxn
2 x1 λ x3…xn-1, если x2=a, x3x4…xn, если x2=b
3 x1 x2…xn , если в данном слове количество букв а нечетно, bb, если четно.
4 x1λx3λ…λxn, если n нечетно, x1 x2…xn , если n четно.
5 x2ax1
6 x1 x2… xn-1xnxn-1…x1
7 baba, если слово начинается на ba, x1 x2…xna в других случаях
8 bx1 x2…xn, если xn=a, bb, если xn=b
9 ab, если n четно, xn, если n нечетно
10 a x1 x2…xn-2b

Задание 2
А) Построить машину Тьюринга, вычисляющую числовую функцию f(x1,x2,…xn).
В) Проверить работу построенной машины над некоторыми наборами значений переменных . Варианты задания приведены в таблице
№ f(x1,x2,…xn).
1 f(x,y,z)=x+y
2 f(x,y,z)=y+3
3 f(x,y,z,w)=4
4 f(x,y,z,w)=y+z+1
5 f(x,y)={0,если x≥y, 1, если x3
2 aa, если в данном слове число букв b нечетно, x1 x2…xn-1, если четно
3 x1 x2…xn-1xnxn , если x2=a, x1 x2…xnb, если x2=b
4 Abb, если слово начинается на ab, x1x2, в остальных случаях
5 x1…xnb, если n-четно, b x1…xn, если n-нечетно
6 ab, если x2=a, x1 x2…xn-1, если x2=b
7 a^n, если x1=a, x2, если x1=b
8 x1 x2…xna^n
9 X1xnx2x3…xn-1xn
10 B^n x1 x2…xn