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

в pa f5b Pc P Л ap bp cp • a (1) (2) (2) (4) (5) Это таблица, очевидно, задает нормальный алгоритм над алфавитом А, ибо Р € А. Если взять произвольное слово Rq В ТО К нему сначала подстановки (1),(2) и не применимы, так как слов ра, РЬ ж Рсъ слове Ro быть не может. Подставив вместо самого левого пустого слова {Л) в Ro слово Рш (5), имеем PRo. Если первой в Ro стоит буква а, то применяем подстановку (1), если же первая буква - Ь, то применяем подстановку (2), а если первая с, то применяем (3) и перемещаем Рза первую букву в слове Ro. Повторяя этот процесс столько раз, сколько букв в слове Ro, получим RoP. По подстановке (4) окончательно имеем RoO, т.е. этот алгоритм приписывает к произвольному слову Ro в алфавите А справа от RO букву А. В рассмотренном алгоритме В подстановки (1),(2) и (3) служат для перестановки местамиР и а или РиЬ илиРяс , т.е. для перестановки Р с любой буквой алфавита^. Тогда можно ввести для нашего алгоритма в более краткую форму записи: рх ^ хР fxeAJ (1^) В'=\р (•)а ^2*; Л ^ р (З"") Здесь запись (1^): рс -^хР применена для обозначения подстановок (1)-(3) в В. Пусть М={7,*}. Любое неотрицательное целое (натуральное) число можно записать (обозначить) в алфавитеМ словом, состоящим из п+\ букв 7: число О обозначим словом О =1, число 1 обозначим словом 1 =11, число п обозначим словом п = 777...7 . п+1единиц Слова п будем называть цифрами. Поставим теперь в соответствие всякому вектору {п1,п2,...,щ), где П1,П2,..,щ - натуральные числа, слово П\^П2^ в алфавите М, которое обозначим через (п1,п2,...,щ) . Например, (1,2,3) обозначает слово 77*777*7777. 3. Нормальный алгоритм ^0 - all al Л al •7 а 150