ТМВ-2020-Лекция-21.04.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Ограниченность ПРФ. Функция Аккермана.

Необходимая информация с предыдущих лекций

ПРФ:

-\(0:0(x)=0\)

-\(s(x)=x+1\)

-\(P^{i}_k(x_1,...,x_k)=x\)

Подстановка

\(F(x_1,...,x_n) = f(g_1(x_1,...x_n),...,g_k(x_1,...x_n))\)

Примитивная рекурсия

\(F(x_1,...x_k,0)=f(x_1,...,x_k)\)

\(F(x_1,...x_k,y+1)=g(x_1,...,x_k,y,F(x_1,...,x_k,y))\)

Утверждение для ПРФ

Мы хотим определить некоторую последовательность функций:

\(a_0,a_1,...,a_n,...\)

Определяем их рекурсивно:

\(a_0(x)=x+1\)

\(a_{i+1}(x)=a_i[x+2](x)\) //\(f[n](x)=f(f(...(f(x))...))\) - повторяется n раз, например, \(f[1](x)=f(x)\), f[2](x)=f(f(x))

что такое \(a_1(x)=a_0[x+2](x)=x+x+2=2x+2\) //значение функции \(a_1\) уже в 2 раза больше, чем значение функции \(a_0\)

что такое \(a_2(x)=a_1[x+2](x)=2(2(...(2x+2)+2)...)+2)+2\) //1 член вида \(2^{x+2}x\)

Важно, что нулевая функция - линейная функция по \(x\), вторая - линейная функция по x, 3-я уже примерно экспоненциальная. Таким образом, функция невероятно быстро растёт. Для 4-й будет очень сложно вычислить.

Полезные свойства функций:

1) \(a_i(x)>x\), так как \(a_0(x)\) строго монотонна по \(x\), а любая другая функция - так или иначе многократно применённая \(a_0\) к своему аргументу

2) \(a_{i+1}(x)=a_i[x+2](x) > a_i(x)\) // монотонна по номеру

3) \(a_{i+1}(x) \ge a_i[2](x)=a_i(a_i(x))\)

Утверждение:

Если \(f:N^{k}_0 \rightarrow N\) - ПРФ, то \(\exists n \in N_0: f(x_1,...,x_k)<a_n(max(x_1,...,x_k))\)

Пояснение некоторых моментов:

Во первых, номера зависят от функции, вообще говоря, то есть нет такого номера \(n\), который больше, чем любая ПРФ.

Во вторых, довольно типичный используется приём: когда у нас есть функция \(k\) аргументов, мы делаем функцию одного аргумента: мы использовали функцию \(max\) (могли использовать среднее, но в данном случае максимум намного удобнее).

Доказательство:

ПРФ - либо базисная функция, либо набор базисных функций, к которым применены операторы. Таким образом докажем утверждение сначала для базисных функций, потом докажем, что утверждение сохраняется при применении операторов.

1) Рассмотрим все базисные функции:

  • \(0(x)=x<a_0(x)\) //номер n = 0
  • \(s(x)=x+1=a_0(x)<a_1(x)\)
  • \(P^{i}_k(x_1,...,x_k)=x_i \le max(x_1,...,x_k) \lt 1+max(x_1,...,x_k)=a_0(max(x_1,...,x_k))\)

2) Сделаем то же самое для операторов:

  • Подстановка \(F(x_1,..,x_n)=f(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))\)

Предполагаем, что \(f,g_1,...,g_k < a_m\)

\(f(g_1,...,g_k)<a_m(max(g1,...,g_k))\) < {подставим \(g_i(x_1,...,x_n)<a_m(max(x_1,...,x_n))\) в аргументы функции \(max\)} < \(a_m[max(a_m(max(x_1,...,x_n)), a_m(max(x_1,...,x_n)), ..., a_m(max(x_1,...,x_n)))]\)=\(a_m(a_m(max(x_1,...,x_n))) \le a_{m+1}(max(x_1,...,x_n))\)

Таким образом, \(f(g_1,...,g_k) \le a_{m+1}(max(x_1,...,x_n))\)

  • Примитивная рекурсия

\(F(x_1,...,x_k,0) = f(x_1,...,x_k)\)

\(F(x_1,...,x_k,y+1) = f(x_1,...,x_k, y, F(x_1, ..., x_k))\)

Предполагаем, что \(f,g < a_m\)

\(F(x_1,...,x_k,0)=f(x_1,...,x_k) < a_m(max(x_1,...,x_k))=a_m[1](max(x_1,...,x_k))\)

\(F(x_1,...,x_k,1)=g(x_1,...,x_k,0,F(x_1,...,x_k,0))\) < {мы мажорируем это, так как функция \(g\) сама по себе мажорирует с функцией \(a_m\)} < \(a_m(max(x_1,...,x_k,0,F(x_1,...,x_k,0)))<\)

\(a_m(max(x_1,...,x_k)) >x_i\)

\(a_m(max(x_1,...,x_k)) >0\)

\(a_m(max(x_1,...,x_k)) >F(x_1,...,x_k,0)\)

\(<a_m(a_m(max(x_1,...,x_k)))=a_m[2](max(x_1,...,x_k))\)

\(F(x_1,...,x_k,y+1) < a_m[y+2](max(x_1,...,x_k)) \le\)

Пусть \(max(x_1,...,x_k,y+1)=\xi\)

\(\le a_m[\xi + 2](\xi)\)

\(F(x_1,...,x_k,y+1)=g(x_1,...,x_k,y,F(x_1,...,x_k,y))<a_m(max(x_1,...,x_k,y,F(x_1,...,x_k,y))) < \)

\(F(x_1,...,x_k,y) < a_m[y+2](max(x_1,...,x_k))\)

\(F(x_1,...,x_k,y) < a_m[\xi+2](\xi)\)

\(a_m(a_m[y+2](\psi))=a_m[y+3](\psi) \le a_m[\xi +3][\psi]\)

Таким образом: \(F(x_1,...,x_k,y) < a_m[max(x_1,...,x_k,y)+2](max(x_1,...,x_k,y))=a_{m+1}(max(x_1,...,x_k,y))\) ∎

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

Введем функцию \(A(n)=a_n(n)\)

Пусть \(A\) - ПРФ, тогда \(\exists M: A(x)<a_m(x)\)

\(A(M+1)=a_{M+1}<A_M(M+1)\), но \(a_{M+1}>A_M(M+1)\), следовательно, \(A\) не является ПРФ. Таким образом мы построили функцию, которая не является ПРФ.

Осталось сказать, что \(A\) является функцией Аккермана.

\(n!\) - ПРФ

\(n^n\) - ПРФ

Любая из этих функций будет расти медленнее, чем функция Аккермана.

Обратная функции Аккермана - константа.

Выше мы доказали, что функция Аккермана не является ПРФ.

Функция Аккермана всюду определена (на любом возможном входе), но при этом она не является ПРФ.

Полезная информация о функции Аккермана

https://habr.com/ru/post/486548/