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

как легко убедиться, применим только к тем словам в алфавите М, которые суть цифры, и переводит любое слово п ъ О, т.е. Ао {п)=0 для любого натурального п. Заметим, что алгоритмов не применим к пустому слову. 4. Нормальный алгоритм: Ai = \al • 11 Л ^ а очевидно, тоже применим только к тем словам в алфавите М, которые суть цифры, и преобразует любое слово п в слово п +1, т.е. Ai{n )=п + 1 для любого натурального п. Алгоритм Aj, как и Ао, не применим к пустому слову. § 4. Функции частично вычислимые и вычислимые по Маркову Напомним, что функция f(x) называется частично определенной на множестве М, если значения этой функции определены не для всех х из М. Функция / называется арифметической, если ее значения и значения её аргументов являются целыми неотрицательными числами, т.е. область определения аргументов и область значений функции есть множество натуральных чисел. Положим, как и раньше, алфавитМ={7,*}. Пусть (р - частично определенная арифметическая функция от п аргументов. Положим, что существует некоторый алгоритм (не обязательно нормальный) в алфавите М, позволяющий вычислять значения этой функции всякий раз, когда значение функции существует, т.е. Agl{ki,k2,...,kn))"" (p(kj,k2,...,kn) тогда и только тогда, когда хотя бы одна из частей этого равенства определена. При этом считаем, что алгоритм А^ не применим к словам, отличным от слов вида {к\,к2,...,кп)- Назовем функцию (р частично вычислимой по Маркову функцией, если существует нормальный алгоритм В надМ, вполне эквивалентныйЛ ^относительно алфавитам. Иными словами, и-аргументная частично определённая функция (р частично вычислима по Маркову тогда и только тогда, когда существует нормальный алгоритм, позволяющий вычислить значение (p{ki,k2,...,kn) для любых совокупностей значений ху =^7, Х2=к2,..., = кп, при которых (p{ki,k2,...,kn) существует. Если функция определена всюду, т.е. определена для любой совокупности значений своих аргументов и является частично вычислимой по Маркову, назовем ее вычислимой по Маркову. Таким образом, и-аргументная функция (р вычислима по Маркову тогда и только тогда, когда существует нормальный 151