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

Этот алгоритм в любом слове Р (алфавита А ) все встреча­ ющиеся там буквы a\,a%...,ak заменяет на слова Q\,Qb-,Qk соответственно. Если же в Р букв 01,02,....Ок нет, то оставляет его без изменения. Пусть М={1,*}. Любое неотрицательное целое (натуральное) число можно записать (обозначить) в алфавите М словом, состоящим из и+1 букв 1: число О обозначим словом 0=1, число! обозначим словом 1=11, число п обозначим словом п = 111...1 . п+1единиц Слова п будем называть цифрами. Поставим теперь в соот­ ветствие всякому "вектору где щ,пъ...,Пк - натуральные числа, слово в алфавите М , которое обозначим через АА — («1,«2 • Например, (1,2,3) обозначает слово 11*111*1111. 4. Нормальный алгоритм: * —> * a l 1 -> a l a l —> »1 Л а как легко убедиться, применим только к тем словам в алфавите М, которые суть цифры, и переводит любое слово п в О , т.е. Ао ( Я ) = О для любого натурального п. Заметим, что алгоритм Ло не применим к пустому слову. 5. Нормальный алгоритм: a l -> ®11 А а очевидно, тоже применим только к тем словам в алфавите М, которые суть цифры, и преобразует любое слово п в слово и + 1, т.е. Al 224