Рекурсия

[arseniiv]

MestnyBomzh в сообщении #827694 писал(а):

arseniiv
так я же ничего не говорил про неопределенность частично-рекурсивной функции

Это я на всякий случай добавил: вдруг вы решили, что это разные классы, потому что все примитивно рекурсивные функции общерекурсивны.

[MestnyBomzh]

Maslov
хорошо, а если спрашивается "Будет ли функция рекурсивной?", то имеется в виду: "Является ли функция примитивно-рекурсивной или частично-рекурсивной или общерекурсивной?" То есть эти три типа вместе образуют класс рекурсивных функций?

[nikvic]

MestnyBomzh в сообщении #827742 писал(а):

если спрашивается "Будет ли функция рекурсивной?", то имеется в виду: "Является ли функция примитивно-рекурсивной или частично-рекурсивной или общерекурсивной?" То есть эти три типа вместе образуют класс рекурсивных функций?

Рекурсивная = частично-рекурсивная, или алгоритмическая. Этот класс содержит множество общерекурсивных функций, которое содержит класс примитивно-рекурсивных.

Термин удобно использовать, когда доказывается нерекурсивность какой-либо функции.

[MestnyBomzh]

nikvic
Спасибо, понял. А функция $y=\sqrt{x^2-5}$ не будет примитивно-рекурсивной, так как не везде определена?

[nikvic]

MestnyBomzh в сообщении #827760 писал(а):

А функция $y=\sqrt{x^2-5}$ не будет примитивно-рекурсивной, так как не везде определена?

Гм, термин рекурсивный применИм только для отображения целых неотрицательных в себя
В широком смысле - к т.н. конструктивным объектам.

[MestnyBomzh]

nikvic в сообщении #827762 писал(а):

Гм, термин рекурсивный применИм только для отображения целых неотрицательных в себя

А здесь же, функция при $x=1,2,$ будет невычислима

[nikvic]

MestnyBomzh в сообщении #827892 писал(а):

А здесь же, функция при $x=1,2,$ будет невычислима

Неправильно используете термин.
Функция неопределена для этих значений аргумента, но это не мешает её быть вычислимой.

[MestnyBomzh]

Аа, то есть так сказать, что она не будет примитивно-рекурсивной нельзя. А как доказать, что без оператора минимизации тут никак? Взять $x+1$ и показать, что зависимости от предыдущего элемента не будет?

[nikvic]

MestnyBomzh в сообщении #828022 писал(а):

А как доказать, что без оператора минимизации тут никак?

Без минимизации получаются только всюду определённые функции.

[MestnyBomzh]

nikvic
А у нас не всюду определенная=>она не примитивно рекурсивна.
И она рекурсивна, так как $y=\mu _{y}(y^2>x^2-5)-1$

-- 18.02.2014, 13:16 --

А, или это тоже неверно, потому что я написал для целой части....она и рекурсивной не будет??

[nikvic]

MestnyBomzh в сообщении #828040 писал(а):

я написал для целой части....она и рекурсивной не будет??

Будет, будет...
Например, на Бейсике

[MestnyBomzh]

nikvic
Ну на Бейсике возможно, язык я этот не изучал. А с точки зрения дискретной математики нет?

[nikvic]

MestnyBomzh в сообщении #828044 писал(а):

Ну на Бейсике возможно, язык я этот не изучал. А с точки зрения дискретной математики нет?

Любой полный алгоритмический язык годится для представления рекурсивных функций. Отдельно их изучают только из уважения к авторитетам (и штоп не выкидывать готовые лекционные материалы) - и это, по-моему, анахронизм

[Lia]

arhimedius
Сообщение отделено в «Примитивно-рекурсивная функция». Кнопка есть, в другой раз ищите лучше.