Еще одна задачя по дискре

akv3986

Как я заметил мало еще кто решил задачи те что были предложены мной вот еще одна из моих задач:
Доказать примитивную рекурсивность функции f(x)=(x+1)-му десятичному знаку после запятой в разложении е( е - это всем известная константа)
предложу еще одну задачу которую еще никто не решил :
Д-ть, что при любом К>=3 в Р_к имеется континуум замкнутых классов не имеющих базиса.

v1160908

Первая задача.
Ясно, что нужная цифра равна остатку от деления на 10 числа [e*10^(x+1)]. А это равно [A(x)], где
A(x)=10^(x+1)*(1/0!+1/1!+...+1/10^(x+1!).
Докажем это. Ясно, что e*10^(x+1)=A(x)+B(x где B=10^(x+1)*(1/(10^(x+1)+1)!+1/(10^(x+1)+2)!+...) (разложение Тэйлора). Ясно, что B<1/(10^(x+1!. С другой стороны, A(x)=n(x)/(10^(x+1!, где n(x) - целое число. Поэтому [A(x)]=[A(x)+B(x)]. Примитивная рекурсивность [A(x)] очевидна.
Про вторую надо книжку читать.

akv3986

Может кто-нибудь показать очевидность примитивной рекурсивности [A(x)]?

v1160908

Ну ладно.
Предположим, что уже доказана примитивная рекурсивность функций x+y,x*y,[x/y],констант (если все-таки не доказана, то читай книжку).
Функцию x^y можно получить такой примитивной рекурсией::
x^0=1
x^(y+1)=x^y*x
функцию x! такой рекурсией:
0!=1
(x+1)!=x!*(x+1)
Функцию f(x,y)=[(10^(x+1!/0!]+[(10^(x+1!/1!]+...+[(10^(x+1!/y!] вот такой:
f(x,0)=10^(x+1
f(x,y+1)=f(x,y)+[(10^(x+1!/(y+1)!].
И [A(x)] вот так:
[A(x)]=[10^(x+1)*f(x,10^(x+1/(10^(x+1!].
Везде используются только операции суперпозиции и примитивной рекурсии.
А вообще, есть известные теоремы, позволяющие очень легко доказывать примитивную рекурсивность. Например: множество примитивно рекурсивных функций совпадает с множеством функций, вычислимых за не более, чем примитивно рекурсивное время (в качестве модели вычислений подойдет практически все что угодно: все разновидности машин Тьюринга, нормальные алгоритмы Маркова, языки программирования высокого уровня, в том числе самые извращенные). То есть можно написать прогу, вычисляющую [A(x)] за время, не превосходящее например 2^(2^(2^x+1000 и доказать примитивную рекурсивность 2^(2^(2^x+1000 (а это уже очевидно).
А еще есть такая теорема: функция примитивно рекурсивна тогда и только тогда, когда ее можно реализовать на паскале (потому что в паскале цикл for не такой извращенный, как в си-подобных языках) без использования goto, while, repeat-until, рекурсии. То есть, только циклами for, условными операторами, стандартными последовательными операциями. Я думаю, не составит труда написать прогу с такими ограничениями, вычисляющую [A(x)].

CokpaT

Д-ть, что при любом К>=3 в Р_к имеется континуум замкнутых классов не имеющих базиса.
Именно не имеющих базиса (не со счетным?). Пусть k >=3. Рассмотрим последовательность функций, как в примере Янова: f_0 = 0,
f_i(x_1, ..., x_i) = 1, если x_1=x_2=...=x_i=2, и f_i=0 в противном случае.
Рассмотрим класс F, который получается из всех функций {f_0, f_1, ....} путем переименования переменных. Это замкнутый класс, и известно (можно посмотреть в книге что он не имеет базиса.
Как получить континуум классов такого же типа: берем любое бесконечное подмножество из {f_0, f_1, .....}, и рассматриваем соответствующий класс, полученный из функций нашего подмножества путем переименования переменных. Так же, как и для основного класса F, доказывается, что этот класс не имеет базиса. Число бесконечных подмножеств счетного множества - континуум. Конец.
Оставить комментарий
Имя или ник:
Комментарий: