Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

а). Показать, что схема f G all^al al ^*1 л^а V определяет нормальный алгоритм F над алфавитом В, применимый только к тем словам в алфавите В, которые являются цифрами, и такой, что р{п) = 0 для любого п. б) Показать, что нормальный алгоритм G над алфавитом В, определяемый схемой al •!!, л^а применим только к тем словам в алфавите В, которые суть цифры, причем G( «)= п +1 для любого п. в). Построить схему нормального алгоритма в алфавите В, перерабатывающего («;,«2) в {rij -П2). г). Построить нормальный алгоритм умножения на 2. 14. Построить нормальный алгоритм над алфавитом В={1,*} для арифметических операций сложения и вычитания. 15. Построить нормальный алгоритм для умножения на фиксированное число п. 16. Пусть А={1, *,а,Ь}. Показать, что следующий нормальный алгоритм bl —>lb *1^* al—>lba * —>Л CI — b —-^1 1 * —>*a производит умножение двух чисел пит, записанных в алфавите В={1,*}ъ виде одного слова 111...1* 111...1. п т 17. Построить нормальный алгоритм F над алфавитом А такой, что для любого слова Р ъА было F(P) =РР. 18. Построить нормальный алгоритм для получения целой части при делении: а) на 5; б) на «. 19. Построить схему нормального алгоритма, равного композиции нормальных алгоритмов F иG в алфавите /7, *}\ 181