Логический блок МТ имеет конечное число состояний {q_i} i=1..m.

Знаки R, L, N, q₁,..,q_mобразуют внутренний алфавит машины.

Переработанный знак s_j, записываемый в просматриваемую ячейку, состояние, которое примет машина Тьюринга в следующем такте q(t+1) и выполняемая в данном такте операция перехода к следующей ячейке P(t+1) являются функцией анализируемого в данном такте символа и текущего состояния машины s_i и q(t):

s_i(t+1)=f₁(s_i,q(t));

q(t+1)=f₂(s_i,q(t));

P(t+1)=f₃(s_i,q(t)).

Программа для МТ определяется тройкой {s_i, P, q}_t.

Пример записи программы вычисления логической функции "неравнозначность" для машины Тьюринга представлен ниже.

Символ (si)	Состояние
	q1	q2	q3	q4
0	0, R, q1	0, N, q4	1, N, q4	0, N, q4
1	1, R, q3	1, N, q4	0, N, q4	1, N, q4

Перед началом работы машина Тьюринга находится в состоянии q1 считывания первого операнда.

Данная МТ применима к исходной информации. Останов – состояние q4. Значение s_i в ячейке y не меняется (сохраняется результат).

Если программа для МТ будет определена таблицей переходов

Символ (si)	Состояние
	q1	q2	q3	q4
0	0, R, q2	0, N, q4	1, N, q4	1, N, q4
1	1, R, q3	1, N, q4	0, N, q4	0, N, q4

то данная МТ будет не применима к исходной информации, поскольку в состоянии q4 значение s_i в ячейке y постоянно меняется на противоположное.

Рекурсивные функции

Теория рекурсивных функций, являясь частью теории алгоритмов представляет собой разветвленную математическую дисциплину с собственной проблематикой и с приложениями в других разделах математики. Понятие «рекурсивной функции» может быть положено в основу конструктивного определения исходных математических понятий. Понятие примитивно рекурсивной функции лежит в основе первоначального доказательства знаменитой теоремы Гёделя о неполноте формальной арифметики, а понятие «рекурсивной функции» в его полном объёме было использовано С. К. Клини для интерпретации интуиционистской арифметики (исследование это составило целую эпоху в области семантики). Аппарат теории рекурсивных функций используется также в теории вычислительных машин и программирования.

Рекурсивные функции были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков. Исследования показали, что все известные уточнения общего понятия алгоритма, в том числе рекурсивные функции, взаимно моделируют друг друга и, следовательно, ведут к одному и тому же понятию вычислимой функции.

Определение 4 Рекурсивные функции (от позднелатинского recursio — возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. 

Каждая рекурсивная функция задаётся конечной системой равенств точно охарактеризованного типа в том смысле, что её значения вычисляются с помощью этой системы равенств по точно формулируемым правилам, причём таким образом, что в итоге для вычисления значений заданной рекурсивной функции получается алгоритм определённого типа.

Арифметические функции, для вычисления значений которых имеются какие-либо алгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется несколько расплывчатым. Рекурсивные функции уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории рекурсивных функций под названием тезиса Чёрча по имени американского математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметической функции точный математический смысл и подвергнуть это понятие изучению при помощи точных методов.

Рекурсивные функции являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Рекурсивные функции, определённые при любых значениях аргументов, называют общерекурсивными функциями.

Определению рекурсивной функции может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда рекурсивные функции определяются как такие функции, которые можно получить из исходных в результате конечного числа применений упомянутых выше операций.

Оператор подстановки сопоставляет функции f от n переменных и функциям g₁, . . ., g_n от m переменных функцию h от m переменных такую, что для любых натуральных чисел x₁, .., x_m

h(x₁, .., x_m)  f (g₁(x₁, .., x_m), ..., g_m(x₁, .., x_m))

(здесь и ниже условное равенство  означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).

Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x₁, .. .., x_n, y

h(x₁, .., x_n ,0)  f(x₁, .., x_n),

h(x₁, .., x_n, y + 1)  g(x₁, .., x_n, y, h(x₁, .., x_n, y )).

Оператор минимизации сопоставляет функции f от n переменных функцию h от n переменных такую, что для любых натуральных чисел x₁, .., x_n

h(x₁, .., x_n)  f(x₁, .., x_n-1, y)

где у таково, что f(x₁, .., x_n-1, y-1) определены и отличны от x_n, а f(x₁, .., x_n, y) определена и равна x_n, если же у с указанными свойствами не существует, то значение h(x₁, .., x_n) считается не определённым.

Важную роль в теории рекурсивных функций играют т. н. примитивно рекурсивные функции — рекурсивные функции, получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме рекурсивные функции могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и T_n от n + 2 переменных, что для любой рекурсивной функции  от n переменных и для любых натуральных чисел x₁, . . ., x_n имеет место равенство (x₁, ..., x_n)  U(y), где у есть наименьшее из чисел z таких, что T_n(, x₁, ..., x_n,z) = 0 (здесь  представляет собой т. н. геделев номер функции  — число, которое эффективно строится по системе равенств, задающей функцию ). Из этой теоремы, в частности, вытекает, что для Рекурсивной функции от п переменных может быть построена универсальная рекурсивная функция от n+1 переменных, т. е. такая рекурсивная функция Ф_n, что для любой рекурсивной функции  от n переменных и для любых натуральных чисел x₁, . . ., x_n имеет место условное равенство

( x₁, . . ., x_n)  Ф_n( , x₁, . . ., x_n).

  Это — один из центральных результатов общей теории рекурсивных функций.

Контрольные вопросы:

15