|
Теорема о правильной вычислимости суперпозиции функций. ⇐ ПредыдущаяСтр 2 из 2 Оператор примитивной рекурсии. Оператор, сопоставляющий функции 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). В данном определении переменную можно понимать как счётчик итераций, — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций переменных, начинающуюся с, и — как оператор, принимающий на вход переменных, номер шага итерации, функцию на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.
Примитивно-рекурсивные функции. Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса базовых примитивно рекурсивных функций и двух операторов (суперпозиции и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся. К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов: · Нулевая функция · Функция следования · Функции
Примитивная рекурсивность предикатов. Определение. Предикат р(х) называется примитивно рекурсивным, если его представляющая функция является примитивно рекурсивной функцией.
Например, следующие предикаты p1(x,y) = (x=y); p2(x,y) = (x<y) являются примитивно рекурсивными, так как их представляющие функции являются ПРФ.
Теорема о правильной вычислимости функции, полученной примитивной рекурсией. Функция Аккермана. Функция Аккермана определяется рекурсивно для неотрицательных целых чисел Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение Оператор минимизации. Оператор минимизации аргумента. Пусть
Теорема о правильной вычислимости функции, полученной с помощью оператора минимизации. Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента. Оператор минимизации аргумента. Пусть Тезис Чёрча. физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга; Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством. ![]() ![]() Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... ![]() Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ![]() Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... ![]() Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|