Университет XXI века: научное измерение

Университет XXI века: научное измерение – 2022 191 Например, для функции сложения имеем х + 0 = х и х + (у + 1) = (х + у)+1 , то есть она может быть определена при помощи оператора примитивной рекур- сии и исходных функций индивидуализации и следования. Нормальные алгоритмы советского математика Маркова А.А. (1903- 1979), также уточняющие понятие алгоритма, основаны на марковской подста- новке при преобразовании слова в некотором алфавите (при этом предполага- ется наличие пустого символа ∆ в любом месте слова), то есть замене самого левого вхождения подслова на некоторое слово. При этом последовательность подстановок (формул), образующая нормальный алгоритм, является упорядо- ченной и всегда преобразования начинаются с первой (если возможно) форму- лы. Например, обращение слова в некотором алфавите А можно осуществить при помощи следующей схемы нормального алгоритма Маркова: ⎩⎪ ⎨ ⎪ ⎧ → , , ∈ , → , → , , ∈ , → , → ∙ ∆, ∆ → . Например, 12345 преобразуется в ∙ 54321. Имеются и другие уточнения определения понятия алгоритма, но все они описывают одни и те же классы вычислимых функций, что является косвенным подтверждением точности определения алгоритма. Литература 1. Марков А. А., Нагорный Н. М. Теория алгорифмов. – М. : Наука, 1984. 2. Мендельсон Э. Введение в математическую логику / пер. с англ. – М. : Наука, 1976. 3. Чёрч А. Введение в математическую логику / пер. с англ. – М. : Иностр. лит., 1960.