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

Показать, что этот алгоритм F применим к любому слову в алфавите А, причем F(P)=D, F(B)=C. 12. Пусть A = { a , b , c } . Построить нормальный алгоритм, который к любому слову в алфавите А будет приписывать справа слово abb. 13. Пусть ^={1} и 5={1,*}. Для всякого натурального числа п определим по индукции 0 = 1 и п + \ ~ п 1 . Таким образом, 1 = 11, 2 = 111 и т.д. Слова п называются цифрами. Поставим теперь в соот­ ветствие всякому вектору где пь...,пк- натуральные числа, слово , которое обозначим через Например, [3,1,2) обозначает слово 1111*11*111; а) Показать, что схема „ a l l a l a l -> el A —> cx определяет нормальный алгоритм F над алфавитом В, применимый только к тем словам в алфавите В, которые являются цифрами, и та­ кой, что о для любого п. б) Показать, что нормальный алгоритм G над алфавитом В, оп­ ределяемый схемой * —> * G= - a l - ^ » l l [ А - > а применим только к тем словам в алфавите В, которые суть цифры, причем с(и) = п + 1 для любого и. в) Построить схему нормального алгоритма в алфавите В, пере­ рабатывающего ( «i,«2) ^ ("l~""2)- г) Построить нормальный алгоритм умножения на 2. 14. Построить нормальный алгоритм над алфавитом В={ 1,*} для арифметических операций сложения и вычитания. 268