Математическая логика и теория алгоритмов

15. Построить нормальный алгоритм для умножения на фикси­ рованное число п. 16. Пусть А='{\,*,а,Ь}. Показать, что следующий нормальный алгоритм bl-^\b *1->* а\-^\Ьа д—>Л Ь-^\ производит умножение двух чисел п и т , записанных в алфавите в виде одного слова * 111...1, п т 17. Построить нормальный алгоритм F над алфавитом А такой, что для любого слова Р в А было F ( P ) = P P . 18. Построить нормальный алгоритм для получения целой части при делении а) на 3; б) на п. 19. Построить схему нормального алгоритма, равного компози­ ции нормальных алгоритмов F и G в алфавите ^={ 1 ,*}: * 1 —> 1 ^ F = { l l l - 4 . A ; G = J *-^e l Л -> * Затем применить полученный алгоритм к слову; а) Р==1111111; б) Р=*1111; в) Р=1*111; г) Результат проверить, последователь­ но применяя к заданному слову алгоритм F , затем G. 20. Пусть имеем нормальный алгоритм F над алфавитом А, схе­ ма которого записана с использованием букв из А и произвольного конечного числа букв, не принадлежащих А . Обозначим эти буквы, не принадлежащие Д через 81,82, т.е. 81,82, Тогда алгоритм F над алфавитом А можно считать заданным в алфавите В. Показать, что для рассматриваемого алгоритма F существует вполне эквивалентный ему в алфавите А нормальный алгоритм, схема которо- 269