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

F = {111^A, * 7 ^ 7 * G = < Затем применить полученный алгоритм к слову: а) Р=1111111; б) Р=*1111; в) Р=1 Р=**. Результат проверить, последовательно применяя к заданному слову алгоритм F, затем G. 20. Пусть имеем нормальный алгоритм F над алфавитом А, схема которого записана с использованием букв из ^ и произвольного конечного числа букв, не принадлежащих А. Обозначим эти буквы, не принадлежащие А, через Si,S2, ••• ,S „, т.е. В=Аи{ Si,S2,...,S „}. Тогда алгоритм F над алфавитом А можно считать заданным в алфавите В. Показать, что для рассматриваемого алгоритма F существует вполне эквивалентный ему в алфавите А нормальный алгоритм, схема которого построена только с использованием букв алфавита C=Au {(X ,f5} (а,р^В). Можно ли исключить одну из букв аили Д если п>11 21. Для каждого из приведенных далее алгоритмов над алфавитом ^4 =/а,/?} найти вполне эквивалентный ему нормальный алгоритм, схема которого записана только с использованием букв а, Ь, а, f5\ аа^ ае аа р РЬ ^ by yb ; y^a a^a fi = л); f2 = рз = Q —^ (X ob ^ (5 ap yy^ s 5 ^ •b y^a oi) ^ba a ^ Py xp Px{xi p ^aa y^bb a ^ a 22. Пусть A - некоторый алфавит. Составьте нормальный алгоритм над А, позволяющий для произвольных слов и в алфавите А выяснять, одинаковы эти слова или нет. (Указание: рассмотрите слово P*Q{Tji,Q *^А) и постройте алгоритм, сравнивающий в словах Р я Q буквы, стоящие первыми слева и справа от затем вторыми от ^и т.д.) 23. Пусть А={0,1,2,... ,9}. Составьте нормальный алгоритм над который любое число п, записанное в десятичной системе счисления, преобразует в п+1. 24. Будем рассматривать нормальные алгоритмы в алфавите^. До сих пор мы применяли для их задания «схемы» - столбцы формул подстановок. Однако можно задавать каждый нормальный алгоритм в виде одного слова, которое получается следующим образом. Пусть a,p,Y^A. Выпишем друг за другом в порядке очередности формулы подстановок алгоритма F заменой стрелки знаком а, точки - знаком Р и присоединением после каждой подстановки знака Y Получаемое так слово будем называть изображением алгоритма F и 182