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

а) {л •Л б) {л •а а^*В Л^а а^а Л^а л) [Л ^ а 10. Показать, что алгоритм: е) {Л •Q ах ха ж) < a^*Q{a^ А,хе А) з) {х • У 1( Х GА ) и) {х «(xG А,а^ а) аа^ р f5x xf5 f5a^ р {а,Р € А,х,уе А) сосу уоос Л^а V преобразует любое слово в алфавите А в слово, образованное из тех же букв, но в обратном порядке. 11. Пусть А - некоторый алфавит, А^А; B ,C ,D, - заданные слова в алфавите А. Рассмотреть нормальный алгоритм над алфавитом ^4 хсх —^ оос осх—^а Вх а{а € А,хе А). хВ —^ ос В ^•С <. Показать, что этот алгоритм F применим к любому слову в алфавите А, причем F (P) =D, F (B) =С. 12. Пусть A={a,b,c}. Построить нормальный алгоритм, который к любому слову в алфавите А будет приписывать справа слово abb. 13. Пусть А ={1 } и В={1, *}. Для всякого натурального числа п определим F по индукции 0 = 1 и п + 1 = п1. Таким образом, 1 = 11, 2 = 111 и т.д. Слова п называются цифрами. Поставим теперь в соответствие всякому вектору (^>77,...где « 7 , - натуральные числа, слово которое обозначим через Так, например, [2,1,2] обозначает слово 1111*11*111: 180