Теорема о правильной вычислимости суперпозиции функций.

Оператор примитивной рекурсии.

Оператор, сопоставляющий функции n переменных j ( x1, x2, …, xn) и функции (n+2)-х переменных g(x1, x2, …, xn, y, t) некоторую новую функцию h() удовлетворяющую условиям:

h(x1, x2, …, xn, 0)=j ( x1, x2, …, xn),

h(x1, x2, …, xn, y+1)=g( x1, x2, …, xn, y, h(x1, x2, …, xn, y)),

(xkÎ N0, k=1, 2, …, n).

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

Примитивно-рекурсивные функции.

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

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

· Нулевая функция — функция без аргументов, всегда возвращающая 0.

· Функция следования одного переменного, сопоставляющая любому натуральному числу непосредственно следующее за ним натуральное число .

· Функции , где , от n переменных, сопоставляющие любому упорядоченному набору натуральных чисел число из этого набора.

Примитивная рекурсивность предикатов.

Определение. Предикат р(х) называется примитивно рекурсивным, если его представляющая функция является примитивно рекурсивной функцией.

Например, следующие предикаты p1(x,y) = (x=y); p2(x,y) = (x<y) являются примитивно рекурсивными, так как их представляющие функции являются ПРФ.

Теорема о правильной вычислимости функции, полученной примитивной рекурсией.

Функция Аккермана.

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел и следующим образом:

Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение , или значение сохраняется, но уменьшается значение . Это означает, что каждый раз пара уменьшается с точки зрения лексикографического порядка, значит, значение в итоге достигнет нуля: для одного значение существует конечное число возможных значений (так как первый вызов с данным был произведён с каким-то определённым значением , а в дальнейшем, если значение сохраняется, значение может только уменьшаться), а количество возможных значений , в свою очередь, тоже конечно. Однако, при уменьшении значение, на которое увеличивается , неограничено и обычно очень велико.

Оператор минимизации.

Оператор минимизации аргумента. Пусть — функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции называется функция от переменной, задаваемая следующим определением: , при условии То есть функция возвращает минимальное значение последнего аргумента функции , при котором её значение равно 0.

Теорема о правильной вычислимости функции, полученной с помощью оператора минимизации.

Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента. Оператор минимизации аргумента. Пусть — функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции называется функция от переменной, задаваемая следующим определением: , при условии То есть функция возвращает минимальное значение последнего аргумента функции , при котором её значение равно 0.

Тезис Чёрча.

физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;

Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: