- •Вопросы для подготовки к экзамену
- •Интуитивное определение алгоритма и вычислимой функции
- •Частично и примитивно рекурсивные функции
- •Вычислимость рекурсивных функций. Тезис Черча
- •Определение оператора подстановки, примеры применения
- •Определение оператора примитивной рекурсии, примеры применения
- •Определение оператора минимизации, примеры применения
- •Построение одноместных рекурсивных функций
- •Построение двухместных рекурсивных функций
- •Машины Тьюринга. Команды в виде четверок и в виде пятерок
- •Функции, вычислимые по Тьюрингу. Тезис Тьюринга
- •Одноместные функции, вычислимые по Тьюрингу
- •Двухместные функции, вычислимые по Тьюрингу
- •Машины с неограниченными регистрами
- •Нормальные алгоритмы Маркова
- •Машины Поста. Функции, вычислимые по Посту
- •Нумерация множества упорядоченных пар натуральных чисел
- •Нумерация машин Тьюринга и вычислимых функций
- •Существование функции, невычислимой по Тьюрингу
- •Разрешимые отношения: определение и примеры
- •Свойства дополнения, объединения и пересечения разрешимых функций
- •Неразрешимость проблемы остановки
- •Универсальные функции
- •Теорема о параметризации
- •Меры сложности алгоритмов
Вопросы для подготовки к экзамену
-
Интуитивное определение алгоритма и вычислимой функции
Алгоритм T над множеством A – это точное предписание, определяющее для любого xA вычислительный процесс – последовательность действий, происходящих по отдельным шагам, так, что каждый последующий шаг однозначно зависит от результатов предшествующих, этот вычислительный процесс либо никогда не завершается, либо завершается в конечное число шагов с получением результата или без результата.
Чтобы убедиться, что данная инструкция является алгоритмом, мы должны проверить выполнение следующих основных общих черт алгоритмов:
1) (массовость) вычислительный процесс, определяемый алгоритмом, может начинаться с любого элемента некоторого потенциально бесконечного множества;
2) (дискретность) вычислительный процесс, определяемый алгоритмом, происходит в дискретном времени, по отдельным моментам времени;
3) (детерминированность) в любой момент времени вычисляется величина, однозначно зависимая от величин, полученных в предшествующие моменты времени;
4) (направленность) вычислительный процесс, определяемый алгоритмом, имеет целью найти некоторый заключительный результат;
5) (элементарность) закон вычисления последующей величины из предшествующих величин должен быть простым и понятным любому вычислителю.
Пусть A, B – два потенциально бесконечных множества. Функция f:AB называется эффективно вычислимой, если существует алгоритм, определяющий для любого xA вычислительный процесс, который
-
заканчивается с результатом f(x)B, если значение f(x) определено, и
-
не заканчивается или заканчивается без результата, если f(x) не определено.
В теории алгоритмов множество натуральных чисел N рассматривается как множество целых неотрицательных чисел: N{0,1,2,…,n,…}.
Функция f(x1,…,xn)y называется числовой, если x1,…,xn,yN. Эффективно вычислимая числовая функция просто называется вычислимой.
-
Частично и примитивно рекурсивные функции
Операции над числовыми функциями называются операторами.
Числовая функция называется частично рекурсивной, если получается из функций o, s, применением конечного числа операторов S, R и M. Используя интуитивное определение алгоритма, можно доказать следующее утверждение:
Теорема 1. Любая частично рекурсивная функция является вычислимой.
Утверждение, обратное к теореме 1, не является ни теоремой, ни аксиомой, а является законом, наблюдаемым на практике:
Тезис Чёрча. Любая вычислимая функция является частично рекурсивной.
Существует не всюду определенные частично рекурсивные функции. Например, функция h(x)y[s(y)x] является частично рекурсивной, но не является всюду определенной: эта функция h(x)x1 не определена при x0.
Числовая функция называется примитивно рекурсивной, если получается из функций o, s, применением конечного числа операторов S и R. Используя интуитивное определение алгоритма, можно доказать следующее утверждение:
-
Вычислимость рекурсивных функций. Тезис Черча
-
Определение оператора подстановки, примеры применения
Говорят, что функция h получена из функций f и m функций g1, …, gm при помощи оператора суперпозиции Sm1 и пишут hSm1(f,g1,…,gm), если h(x1,...,xn)f(g1(x1,...,xn),…,gm(x1,...,xn)) для всех x1,...,xnN (m1, n0).
Когда определено значение функции h(x1,...,xn)?
h(x1,...,xn) определено и равно z, если
g1(x1,...,xn) определено и равно y1,
………………………………………,
gm(x1,...,xn) определено и равно ym,
f(y1,…,ym) определено и равно z;
иначе h(x1,...,xn) не определено.
Если m1, то hS2(f,g) является обычной композицией функций g и f.
При помощи оператора подстановки доказывается, что постоянные функции примитивно рекурсивны. Доказательство приведем, без потери общности, на примере функции f(x,y)3: f(x,y)ssoI12(x,y).
Еще одно применение оператора подстановки: если функция получена из ПРФ перестановкой, повторением или удалением аргументов, то тоже будет ПРФ. Доказательство приведем, без потери общности, на примере функции g(x,y,z)f(y,x,z), где f(x,y,z) есть ПРФ: gS4(f,I23,I33,I13).