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

Алфавит называется расширением алфавита В, если ВсЛ. Если алфавит А есть расширение алфавита В, то, очевидно, всякое слово в алфавите В является также словом и в алфавите А, обратное верно не всегда. Будем говорить, что слово Р входит в слово Q, если Q=RiPR2, где Rj и R2 любые, может быть и пустые слова. Слово Р может входить в слово Q несколько раз, первым вхождением будем считать самое левое вхождение. Под алгоритмом в алфавите А понимается алгоритм, входами и выходами которого являются слова в алфавите А. Таким образом, алгоритм в алфавите А представляет собой потенциально осуществимое преобразование слов в данном алфавите А. Алгоритмы обозначаются жирными заглавными буквами {А, В, С,...). Пусть Р - слово в алфавите А. Говорят, что алгоритм А применим к слову Р, если применение его к слову Р приводит через конечное число шагов к некоторому слову Q. При этом слово Q обозначается через А {Р). Если процесс переработки (преобразования) слова Р бесконечен, то считается, что алгоритм неприменим к этому слову. Два алгоритма Л и в в одном и том же алфавите С называются вполне эквивалентными в алфавите D (D с С), если для любого слова Р в алфавите D оба алгоритма либо неприменимы к Р, либо применимы и их результаты совпадают: А (Р) = В (Р). То, что алгоритмы А и В вполне эквивалентны в алфавите D, обозначается следующим образом: VP в D: А (Р) =В (Р). § 3. Нормальный алгоритм (алгоритм А. А. Маркова) Опыт изучения и применения математики показывает, что все известные алгоритмы можно разбить на простейшие шаги - элементарные операции. В качестве элементарной операции, на базе которой будут строиться нормальные алгоритмы, выделим подстановку одного слова вместо другого. Пусть задан алфавит А, не содержащий в качестве букв символов и и пусть Р vi Q - слова в алфавите А. Тогда выражения P^Q, P^*Q называются формулами подстановки в алфавите^. Формула подстановки P —>Q называется простой подстановкой и означает, что вместо Р нужно подставить слово Q и перейти к следующей подстановке. Формула подстановки P —>»Q называется заключительной подстановкой и означает, что вместо Р нужно подставить Q и закончить процесс преобразования. Пусть Р—>( •)Q означает любую из формул подстановки P —>Q или P —>»Q. Нормальный алгоритм в алфавите А считается заданным, если задана конечная таблица (схема) формул подстановок слов алфавита^: 148