Формальные модели алгоритмов и алгоритмически исчисляемых функций часть 2, сайт

ставит в соответствие V-квазиарну функцию f, значение f (d) которой для каждого d VN определяется как первый элемент аm последовательности a0 = d (v), a1 = f (d vaa0), a2 = f (d vaa1),., ak = f (d vaak-1),. такой, что (d vaam) = 0 и для всех ky программируемый.
Действительно, такой предикат моделируется функцией.
Пример 5. Предикаты xy, x = y и xy программируемые.
Предикат xy моделируется функцией; предикат x = y моделируется функцией 1- | x-в |, его же можно представить в виде (xy) функцию N (, g, h) можно получить из базовых функций в, Sх, "v, xy, и функций, gih с помощью операций N?v и S.
Пример 8. Функции min (x, y) и max (x, y) программируемые.
Действительно, функции min (x, y) и max (x, y) можно представить в соответствии операторных термами N (, 'а,' х) и N (, 'х,' у). Такие термы соответственно обозначать mипxy и mахxy.
Пример 9. Функция mod (x, y) программируемая.
Действительно, функцию mod (x, y) можно представить операторным термо N?х (Sх (, Sх),). Такой терм обозначим modxy.
Пример 10. Функция программируемая.
Действительно, функцию можно представить операторным термо Sу (N?в (Su, v (, Sх, Su, v (uv, sy, sy), sy), 0).
Пример 11. Функция [x, y] программируемая.
Действительно, функцию [x, y] можно подать операторным термо Sz (N?z (Su, v (, Sх, Su (uy, sz), sz), 0).
Пример 12. Функция HCK (x, y) программируемая.
Действительно, функцию HCK (x, y) можно представить операторным термо Sz (N?z (Su, v (+ uv, modzx, modzy), sz), maxxy).
Пример 13. Функция HCD (x, y) программируемая.
Действительно, функцию HCD (x, y) можно представить операторным термо Sz (N?z (Su, v (+ uv, modxz, modyz), Su (, 1), minxy).
Для случая п-арных функций N операции суперпозиции, цикла и ветвления уточним следующим образом.
Операция N? n-арным функциям g и ставит в соответствие n-Арну функцию f, значение f (x1,., xn) которой для каждого набора значений x1,., xn определяется как первый элемент аm последовательности a0 = x1, a1 = f (a0, x2,., xn), a2 = f (a1, x2,., xn),., ak = f (ak-1, x2,., xn),. такой, что (am, x2,., xn) = 0 и для всех kx2, x1 x2, x1 = x2 и x1 x2 программируемые.
предикат x1> x2 моделируется функцией. Предикат x1 x2 моделируется функцией, предикат x1 = x2 можно представить в виде (x1 x2)
2) класс программируемых на N п-арных функций;
3) класс МНР-вычислительных функций;
4) класс функций, вычисляемых по Тьюринг;
5) класс функций, вычисляемых по Марковым;
6) класс функций, вычисляемых по Постом
Итак, рассмотренные нами формализм задают один i тот же класс п-арных функций на N. При этом сами определения формалiзмiв гарантируют эффективную обчислюванiсть описываемых ими функций.
сайт
Поэтому есть все основания считать, что такие формализм является различными математическими уточнениями интуитивно понятие алгоритмического вычислительной функции (АОФ). Впервые такое утверждение относительно рекурсивных функций было выдвинуто в 1936 году А. Черча, так достало название «тезис Черча». Обобщение тезисы Черча в случае частичных функций в этом же году предложил С. Клiнi. В таком расширенном виде тезис Черча формулируется следующим образом:
Tеза Черча. Класс ЧРФ совпадает с классом п-арных АОФ, заданных на множестве натуральных чисел.
Понятие АОФ не является строго определенным математическим понятием, поэтому тезис Черча математическом доведению Не подлежит. Тезис Черча является природно-научным фактом, удостоверяющий адекватность формальных моделей интуитивного понятия АОФ.
С тезисы Черча как следствие следует:
класс РФ совпадает с классом полных АОФ, заданных на множестве натуральных чисел.
Значение тезисы Черча (сокращенно ТВ) заключается в следующем.
1) Принятие тезиса Черча превращает iнтуитивнi понятие алгоритма, обчислюваностi, розвьязностi в объекты математического изучения.
2) Использование тезисы Черча как своеобразной аксiомы позволяет во многих случаях заменить формальные задачи алгоритмов на неформальной их описания. Это дает существенное упрощение доказательств, освобождая его от лишних деталей. Однако доказательства на основе тезиса Черча должно быть тщательно аргументированным! При возникновении сомнений надо уметь провести чисто формальное доказательство.
Рассмотрим пример использования тезиса Черча. Пусть функция f является ЧРФ. Докажем, что функция h (x) = тоже есть ЧРФ. Для этого рассмотрим процесс глобального вычисления всех значений функции f. Такой процесс разобьем на этапы. На каждом етапипочинаемо вычисления для следующего значения аргумента. На этапе 0 делаем 1-й шаг вычисления f (0). На этапе 1 делаем 1-й шаг вычисления f (1) и 2-й шаг вычисления f (0) и т.д. На этапе п делаем 1-й шаг вычисления f (п), 2-й шаг вычисления f (п-1), ..., (n + 1) -й шаг вычисления f (0). Если на каком-то этапе вычисления определенного f (т) завершается, сравниваем f (т) и х. При условии f (т) = х процесс глобальных вычислений заканчивается, ведь тогда х Ef, поэтому результатом нашей работы будет число 1. При условии f (т) х продолжаем процесс глобальных вычислений. Таким образом, описан алгоритм для вычисления функции h (x), откуда по тезисом Черча функция h (x) является ЧРФ.

Комментирование и размещение ссылок запрещено.

Комментарии закрыты.