|
Теорема о правильной вычислимости суперпозиции функций. ⇐ ПредыдущаяСтр 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) являются примитивно рекурсивными, так как их представляющие функции являются ПРФ.
Теорема о правильной вычислимости функции, полученной примитивной рекурсией. Функция Аккермана. Функция Аккермана определяется рекурсивно для неотрицательных целых чисел Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение Оператор минимизации. Оператор минимизации аргумента. Пусть
Теорема о правильной вычислимости функции, полученной с помощью оператора минимизации. Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента. Оператор минимизации аргумента. Пусть Тезис Чёрча. физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга; Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством. ![]() ![]() Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... ![]() ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ![]() Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... ![]() ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|