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

слово в алфавите В является также словом и в алфавите А, обратное верно не всегда. Будем говорить, что словоР входит в слово Q, если Q-R1PR2, где R] и i?2 любые, может быть и пустые слова. Слово Р может входить в слово Q несколько раз, п е р в ы м в х о ж д е н и е м будем считать самое левое вхождение. Под алгоритмом в алфавите А понимается алгоритм, входами и выходами которого являются слова в алфавите А . Таким образом, алгоритм в алфавите А представляет собой потенциально осущест­ вимое преобразование слов в данном алфавите А. Алгоритмы обозначаются заглавными жирными буквами {Л,В,С,...). Пусть Р - слово в алфавите А . Говорят, что алгоритм А применим к слову Р, если применение его к слову Р приводит через конечное число шагов к некоторому слову Q. При этом слово Q обозначается через А (Р). Если процесс переработки (преобразования) слова Р бесконечен, то считается, что алгоритм не применим к этому слову. Два алгоритма/4 и В в одном и том же алфавите С называются вполнеэквивалентнъши в алфавитеD (D q С), если для любого слова Р в алфавите D оба алгоритма либо не применимы к Р , либо применимы и их результаты совпадают; А (Р) - В {Р). То, что алгоритмы А и В вполне эквивалентны в алфавите D , обозначается следующим образом: \/PBD: А( Р ) = В (Р). Введение подходящих абстракций - этодля нашей мысли единственный способ органи­ зовать сложное иуправлять им. Э, Дейкстра § 3. Нормальный алгоритм (алгоритм А. А. Маркова) Опыт изучения и применения математики показывает, что все известные алгоритмы можно разбить на простейшие шаги - элемен­ 220