2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Рекурсия
Сообщение17.02.2014, 17:34 
Заслуженный участник
Аватара пользователя


27/04/09
23059
Уфа
MestnyBomzh в сообщении #827694 писал(а):
arseniiv
так я же ничего не говорил про неопределенность частично-рекурсивной функции
Это я на всякий случай добавил: вдруг вы решили, что это разные классы, потому что все примитивно рекурсивные функции общерекурсивны. :-)

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 17:47 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 17:54 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MestnyBomzh в сообщении #827742 писал(а):
если спрашивается "Будет ли функция рекурсивной?", то имеется в виду: "Является ли функция примитивно-рекурсивной или частично-рекурсивной или общерекурсивной?" То есть эти три типа вместе образуют класс рекурсивных функций?

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

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 18:20 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 18:25 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MestnyBomzh в сообщении #827760 писал(а):
А функция $y=\sqrt{x^2-5}$ не будет примитивно-рекурсивной, так как не везде определена?

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 22:22 
Аватара пользователя


17/10/13
726
Деревня
nikvic в сообщении #827762 писал(а):
Гм, термин рекурсивный применИм только для отображения целых неотрицательных в себя :facepalm:

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 09:28 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MestnyBomzh в сообщении #827892 писал(а):
А здесь же, функция при $x=1,2,$ будет невычислима

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 09:51 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 11:29 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MestnyBomzh в сообщении #828022 писал(а):
А как доказать, что без оператора минимизации тут никак?

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 12:02 
Аватара пользователя


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

-- 18.02.2014, 13:16 --

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 12:22 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MestnyBomzh в сообщении #828040 писал(а):
я написал для целой части....она и рекурсивной не будет??

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 12:32 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение18.02.2014, 12:39 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MestnyBomzh в сообщении #828044 писал(а):
Ну на Бейсике возможно, язык я этот не изучал. А с точки зрения дискретной математики нет?

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение19.12.2014, 20:48 
Модератор


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group