0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
1 | |
Доказать, что функция примитивно рекурсивна24.05.2018, 17:25. Показов 16177. Ответов 16
Метки высшая математика (Все метки)
Здравствуйте,нужна помощь: Доказать, что функция f(x,y)=2^{x^2+y}+y^{x!} примитивно рекурсивна.
Как я делал: f(x,0)=2^(x^2) f(x,y+1)=2^(x^2+y+1)+(y+1)^x!,=2*2^(x^2)+y^x!+1, а что делать дальше? ,я не совсем понимаю этот материал,я делаю по примерам(,очень нужна ваша помощь
0
|
24.05.2018, 17:25 | |
Ответы с готовыми решениями:
16
Доказать, что функция примитивно рекурсивна Доказать, что функция примитивно рекурсивна Доказать, что функция примитивно рекурсивна Доказать, что функция примитивно рекурсивна |
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
24.05.2018, 22:09 | 2 |
Почему бы вам не доказать, что каждая используемая функция — x^2, x+y, 2^x, x!, x^y — примитивно рекурсивны? Тогда f будет п.р. как композиция п.р. функций.
0
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
24.05.2018, 22:18 [ТС] | 3 |
А можно мне отправить вам своё решение и вы посмотрите,верно ли я решил или нет
0
|
Модератор
5239 / 4025 / 1385
Регистрация: 30.07.2012
Сообщений: 12,279
|
|
24.05.2018, 22:20 | 4 |
Darkyn555, можно, но с учетом этого пункта Правил форума...
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
24.05.2018, 22:20 | 5 |
Пишите ваше решение в эту ветку.
0
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
24.05.2018, 22:28 [ТС] | 6 |
Вот решение:
f(x,y)=2x2+y+yx! f(x,y)=2x2+y f(x,0)=2x2 f(x,y+1)=2*2x2+y=h(y, f(y)) f(x,y)=yx! u(y,x)=yx - примитивно рекурсивна, c(x)=x! - примитивно рекурсивна, значит u(y, c(x)) примитивно рекурсивна, а значит вся функция примитивно рекурсивна
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
24.05.2018, 22:33 | 7 |
0
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
24.05.2018, 22:35 [ТС] | 8 |
ну то есть тут нужно исправить на любую другую букву просто,верно?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
24.05.2018, 22:38 | 9 |
Может быть. Я предложил свой способ: доказать примитивную рекурсивность каждой входящей маленькой функции (сложения, возведения в степень, факториала и т.д.), а не доказывать примитивную рекурсивность сразу всей f. Вы можете делать своим способом.
0
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
25.05.2018, 16:26 [ТС] | 10 |
Моё решение не приняли,вы можете показать своё? Если вам несложно?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
26.05.2018, 00:51 | 11 |
Сообщение было отмечено Mikl___ как решение
Решение
Пусть доказано, что функции сложения a(x, y) = x + y и умножения m(x, y) = xy примитивно рекурсивны.
Определение функции f(x) = x! f(0) = 1 f(x+1) = (x+1)f(x) Если писать более точно, пусть базовые функции из определения примитивно рекурсивных функций следующие: s(x) = x+1, константа 0 и проекции для всех . Пусть схема суперпозиции (подстановки) выглядит так. В этом случае говорим, что h получена из g и с помощью суперпозиции. Здесь может требоваться, чтобы все имели одинаковое количество аргументов. Наконец, пусть схема примитивной рекурсии выглядит следующим образом: Здесь . Функция h имеет k+1 аргументов, f имеет k аргументов, а g — k+2 аргументов. Тогда говорим, что h получена из f и g с помощью примитивной рекурсии. Подобные определения даны в следующей книге: Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3: Вычислимые функции. Изд. 4-е. М.: МЦНМО, 2012. С. 132. Применяя схему примитивной рекурсии с k = 0, получаем f(0) = s(0) f(x+1) = g(x, f(x)) где g(x, y) = m(s(x), y). Еще более формально определение g(x, y) записывается так. То есть из и s(x) = x+1 с помощью суперпозиции мы получили функцию , а из m(x,y), j(x,y) и c помощью суперпозиции мы получили g(x, y). Проекции и используются, чтобы у внутренних функций в операции суперпозиции было одинаковое количество аргументов. Если базовая функция 0(x) = 0 является не константой, а функцией одного аргумента (зависит от определения п.р.ф., которое может быть слегка разным в разных учебниках), то в f можно добавить фиктивный первый аргумент. f(z, 0) = s(0(z)) (правая часть есть суперпозиция s(x) и 0(x)) f(z, x+1) = g(z, x, f(x)) где . После этого определяем f'(x) = f(x, x). Эти подробности с использованием проекций при необходимости нужно проделать пару раз, но потом можно писать просто f(0) = 1 f(x+1) = (x+1)f(x), как в начале. Еще нужна Тогда .
2
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
27.05.2018, 11:46 [ТС] | 12 |
Спасибо вам большое,я сейчас бду разбираться,хочу сам понять,не списывать тупо решение,если что,то можно я вам задам пару вопросов по вашему решению?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
27.05.2018, 11:53 | 13 |
Да, конечно, пишите в эту тему.
0
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
27.05.2018, 14:24 [ТС] | 14 |
Вот я понимаю всё,выучил теорию,я понимаю как получается вот это
f(0) = s(0) f(x+1) = g(x, f(x)) для f(x)=x!, но я не понимаю как вы получаете вот это где g(x, y) = m(s(x), y). Еще более формально определение g(x, y) записывается так. g(x, y) = m(s(I12(x,y)), I22(x,y)) , у нас ведь f(x+1) = g(x, f(x)) от 1 переменной,почему у вас потом идёт g(x, y)?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
27.05.2018, 19:52 | 15 |
Это не определение, пока вы не скажете, что такое g. Две функции, которые вы используете в схеме примитивной рекурсии (в базовом случае и в шаге) должны быть определены перед применением этой схемы.
Я определяю g так, чтобы f(x) получился равным факториалу. Ведь f(x+1) = s(x)*f(x), не так ли? Но g-то должна быть от двух аргументов. Если функция, определяемая по схеме примитивной рекурсии, имеет n+1 аргументов (n параметров и один счетчик), то функция в правой части второго равенства схемы (g в данном случае) имеет n+2 аргументов (те же параметры, счетчик и значение рекурсивного вызова). В случае факториала n = 0 (функция зависит только от счетчика). А вы не можете определить функцию g двух аргументов так: g(x, x) = ... Это будет неполное определение. В полном определении между двумя аргументами функции не должно предполагаться никакой связи, они должны быть независимыми.
0
|
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 31
|
|
27.05.2018, 21:18 [ТС] | 16 |
А почему мы представлляем f(x)=x! в виде f(x)=(x,x)?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,649
|
|
27.05.2018, 22:19 | 17 |
Я такого не делал. Читайте внимательнее.
Если базовая функция ноль не является константой, а зависит от одного фиктивного аргумента (так может говориться в некоторых учебниках), то все все п.р.ф. зависят по крайней мере от одного аргумента. Тогда без введения фиктивного аргумента во вспомогательную функцию для факториала, я не знаю, как иначе выразить первое равенство из определения, то есть f(0) = 1.
0
|
27.05.2018, 22:19 | |
27.05.2018, 22:19 | |
Помогаю со студенческими работами здесь
17
Доказать , что данная функция примитивно-рекурсивная f(x,y)=3x! Примитивно-рекурсивная функция Доказать, что функция примитивно рекурсивная Доказать, что функция f инъективна Как доказать, что функция нелинейна Доказать, что функция примитивно рекурсивна Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |