Что такое рекурсивные функции? Душкин объяснит
Вставка
- Опубліковано 6 лют 2025
- Очередная вычислительная модель - рекурсивные функции Курта Гёделя (примитивно рекурсивные, общерекурсивные и частично рекурсивные функции). Изучим эту модель во всех подробностях.
Заходите на мой ТГ-канал: t.me/drv_official - на нём много всего интересного: анонсы видео, истории и всякий сторителлинг, объявления о мероприятиях и всякое такое разное.
Курс «Основы искусственного интеллекта» на Udemy: bit.ly/3BD2I4W
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Все видео канала по искусственному интеллекту: ua-cam.com/video/n3wEM7P11kI/v-deo.html
Вы всегда можете обратиться к нам за консультациями.
И, кроме того, вы всегда можете написать мне в ТГ: @rdushkin
Изображение с доски: disk.yandex.ru/i/lpYJHZ8ppg2p8w
Ящик in не работает. (писал на info, но и оттуда вы не ответили)
@@alexanderskusnov5119, это странно. Сейчас направлю людей разбираться.
В книге Колмогорова "Математика-наука и профессия" (п.5.4) приведена другая система примитивно рекурсивных функций. Там тоже есть S(n)=n+1, но константы 0 нет. Зато есть довольно необычная функция q(n)=n-[sqrt(n)]. К функциям можно применять операции: 1) сложение f(x)+g(x) , 2) подстановку f(g(x)) и 3)итерирование h(0)=0, h(n+1)=f(h(n)). Интересно, как это соотносится с ПРФ Гёделя? Например, константу 0 можно получить итерированием q(n). Потом применяя k раз S(x) получим константу k. Вроде бы, если у функции 1 аргумент, что все ПРФ Геделя можно вычислить и через ПРФ Колмогорова.
А вот насколько существенно, что функции у Гёделя могут иметь разное кол-во аргументов, а у Колмогорова - все функции имеют ровно 1 натуральный аргумент? Ведь можно придумать способ закодировать несколько аргументов в один и наоборот. Например, записать аргументы в 9-ной системе , поставить между ними 9 и прочитать это как 10-е число. А вот даже с учетом такого кодирования, эквивалентны ли по вычислительным возможностям ПФР этих двух систем? Хватит ли у ПФР Колмогорова "мощи" еще и выполнять раскодирование аргументов?
Так можно придумать сколько угодно различных систем ПФР. Главное, чтобы они были Тьюринг-полны. Если у нас есть две Тьюринг-полные системы ПФР, то с очевидностью одну можно выразить через другую.
@@dushkin_will_explain, Но примитивно рекурсивные функции не являются Тьюринг-полными. Тьюринг-полны частично рекурсивные функции. Однако, можно говорить об эквивалентных (с точки зрения вычислимости) системах ПРФ: что можно вычислить в одной системе ,можно вычислить и в другой, пусть даже обе системы не Тьюринг-полны.
@@olegkomlev, а, ну да. Тьюринг-полны, конечно же, частично рекурсивные функции.
Спасибо большое!
Пожалуйста. Мы стараемся :)
Хорошо бы сюда добавить Haskell-оптимизацию foldr-build (получение результата без построения списка), а то вещь хорошая, а до примера как-то руки не доходят.
Вещь хорошая, но тема сложноватая. Но когда-нибудь рассмотрим.
Письмо ваше, кстати, получили же. Я же вам даже отвечал про грант. Если не получили ответ - тоже посмотрите в спаме.
Про оператор минимизации сказано настолько мало, что не понятно, как он работает и зачем нужен.
Где сказано про оператор минимизации?
@@dushkin_will_explain16:21, также называется мю-оператор
@@dushkin_will_explain на 16:21.
@@dushkin_will_explain почему-то оба мои комментария с таймкодом были удалены. Про оператор минимизации сказано на 16 минуте 20 секунде.
@@0xfeedfeed, Ютуб иногда тупит. Сейчас гляну...
Like, we need more
- Больше, нам нужно больше золота!
- А что если золота будет слишком много?
- Глупое животное. Разве золота может быть слишком много?
В итоге, кто ввел понятие "частично рекурсивная функция", Алонзо Чёрч или Курт Гёдель? В видео о лямбда-исчислении вы говорите о первом математике 🤔
Что другие источники на эту тему говорят?
Наверное, правильнее было бы перевести "частично определенные РФ" и "всюду определенные РФ", но сейчас менять уже поздно. Вон "множество" - тоже термин неудачный, уж насколько оно множество, если там может быть и 3 элемента и 1, а то и вообще пусто.
Да, увы. Традиционные некорректные названия сложно извести, так как они везде.
подсказок нету на которые ты указываешь
Уже есть.
"Вы" - епта)
@@bubamumuba Вы сер!