15-§. Структура примитино рекурсивных функций. Реализация алгоритма на машине Тьюринга

Задачи и задания для самостоятельного выполнения.

1. 
   Рекурсивные функции.
   

1. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
2. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
3. 
   Применяя примитивной рекурсивной схемы определить функцию из функции = 1 и .
   
4. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
5. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
6. 
   Применяя примитивной рекурсивной схемы определить функцию из функции = 3 и .
   
7. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
8. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
9. 
   Применяя примитивной рекурсивной схемы определить функцию из функции и .
   
10. 
    Применяя примитивной рекурсивной схемы определить функцию из функции = 2 и .
    

2. Реализация алгоритма на машине Тьюринга.
1. Реализовать функцию арифметическое вычитание в унарном коде.
2. Реализовать функцию выбор максимального из двух чисел над числами в унарном коде.
3. Реализовать функцию над числами в унарном коде.
4. Реализовать функцию над числами в унарном коде.
5. Реализовать функцию над числами в унарном коде.
6. Реализовать функцию над числами в унарном коде.
11. Реализовать алгоритм в алфавите , меняющий местами первую и последнюю буквы слова.
12. Реализовать алгоритм над алфавитом , меняющий местами первый ноль и последнюю единицу.
13. Реализовать операцию копирование в алфавите , то есть получить из слова слово .
14. Реализовать алгоритм над алфавитом , который выдает единицу, если в исходном слове только парные нули и ноль в противном случае.
15. Реализовать алгоритм в алфавите , который переставляет буквы в слове так, чтобы сначала шли все нули, потом – единицы.
16. Реализовать алгоритм, конструирующий в алфавите слова вида , где - произвольное натуральное число.
17. Реализовать алгоритм, реализующий функцию циклический сдвиг двоичного числа на одну ячейку.
18. Реализовать алгоритм в алфавите , анализирующий последовательность цифр в слове и выдающий «+», если цифры образуют неубывающую последовательность, и «–» в противном случае.
19. Реализовать выделение подстроки, заключенной между двумя символами (первая пара) в алфавите . Если последовательность отсутствует на ленте, стереть все.
20. В слове в алфавите стереть все, кроме . Если такой последовательности нет, все стереть.
21. Реализовать алгоритм над алфавитом , переставляющий буквы в обратном порядке.
22. Реализовать предиката «в слове  в алфавите есть пара букв » .
23. Реализовать алгоритм в алфавите , производящий в слове  алфавита замену всех вхождений буквы а на букву б.
24. Реализовать алгоритм в алфавите для вычисления логической функции , где принимают значение 0 или 1.
25. Реализовать алгоритм в алфавите для вычисления логической функции , где принимают значение 0 или 1.
26. Составить композиция машины и по паре состояние ( _, ) и проверит применимости машины к слову К. Здесь, _- конечное состояние машины , - начальное состояние, - конечное состояние машины _.

27. Определить применимости машины к заданному слову К. Здесь, – конечное, - начальное состояние машины , – конечное, - начальное состояние машины , - конечное состояние, - начальное состояние машины .

28. 
    Построить машины на основе схемы U. Проверить применимости машины к заданному слову. Здесь, и начальные и заключительное состоянии машин соответственно.
    

1. =[10]²0011;
2. =[01]²0011;
3. =[101]²0011;
4. =1³0³[01]²;
5. =1² 0²[01]²;
6. =1⁵[01]²;
7. =100 [10]²;
8. =0011[01]²;
9. =0011 [101]²;
10. =[01]²1³0³;
11. =[01]²1² 0²;
12. =[01]²1⁵;
13. =[110]²0011;
14. =[011]²0011;
15. =[11]²0011;
16. =1³0³[11]²;
17. =1² 0²[11]²;
18. =1⁵[11]²;
19. =100 [11]²;
20. =1011[10]²;
21. =1010 [10]²;
22. =[10]²1³0³;
23. =[10]²1² 0²;
24. =[10]²1⁵;
25 =[101]²1⁵;