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

го построена только с использованием букв алфавита C=yiu{a,p | (а,ргВ). Можно ли исключить одну из букв а или Р, если п>\1 21. Для каждого из приведенных далее алгоритмов над алфавц, том А = { а , Ь } найти вполне эквивалентный ему нормальный алгоритти^ схема которого записана только с использованием букв а, Ь. а , (3: аа—> ае аа-^Р ^b-^by р2=-уЬ~^Ъ Fy= у а А—^CL F x - ab ba а PY хр рл;(х е А ) Р ад у -^bb Л - ^ а а а аЬ р а р -> у уу -т»' 8 5 оЬ у -> а 22. Пусть А ~ некоторый алфавит. Составьте нормальный алго­ ритм над А, позволяющий для произвольных слов Р иQ B алфавите А выяснять, одинаковы эти слова или нет. (Указание: рассмотрите слово ?*Й(гдв * ^ А ) и постройте алгоритм, сравнивающий в словах Р и Q буквы, стоящие первыми слева и справа от *, затем вторыми от * ит.д.) 23. Пусть Л={0,1,2,...,9}. Составьте нормальный алгоритм н а д А , который любое число п, записанное в десятичной системе счисле­ ния, преобразует в «+1. 24. Будем рассматривать нормальные алгоритмы в алфавите А . До сих пор мы применяли для их задания «схемы» - столбцы формул подстановок. Однако можно задавать каждый нормальный алгоритм в виде одного слова, которое получается следующим образом. Пусть а,р,у^^. Выпишем друг за другом в порядке очередности формулы подстановок алгоритма F заменой стрелки знаком а, точки - знаком р и присоединением после каждой подстановки знака у. Получаемоет а к слово будем называть изображением алгоритма F и обозначать симво­ лом F*. Алгоритм F называется самоприменимым, если он применим к своей собственной записи, т.е. к слову F ' , и несамоприменимым в обратном случае. 270