Практика преподавания и изучения программирования преимущественно на базе императивных языков (включая объектно-ориентированные императивные языки) приводит к тому, что такой фундаментальный алгоритмический механизм, как рекурсия, остаётся плохо понятным многими программистами и порождает заблуждения, транслируемые в популярной культуре. Попытаемся внести в вопрос немного ясности и изложить некоторые свои мысли по этому поводу.
Что такое рекурсия?
Что такое рекурсия в бытовом понимании? Это решение задачи через сведение её к самой себе в более простых условиях.
Допустим, мы туристы, и перед нами стоит задача попытаться найти в доставшемся нам рюкзаке с едой банку тушёнки. Проверим, пустой ли рюкзак. Если пустой, задача решена, тушёнки нет. Иначе вынимаем из рюкзака первый попавшийся предмет. Если это банка тушёнки, задача решена, тушёнка найдена. Иначе повторяем весь наш алгоритм для имеющегося теперь у нас полегчавшего рюкзака с оставшимся содержимым, и результат решения задачи при этом откладывается на следующий шаг.
Этот пример рекурсии поймёт и маленький ребёнок, а программисты заметят, что это по существу задача поиска элемента в односвязном списке.
Рекурсия сама по себе представляет просто один из возможных способов описания повторяющихся действий. Цикл всегда может быть описан в виде рекурсии. Рекурсия может быть описана в виде конечного числа циклов, но это иногда может потребовать дополнительной структуры данных, хранящей последовательность рекурсивных вызовов.
Определения
Формально введём некоторые определения. Вопрос далеко не нов, поэтому возьмём определения из достаточно академичных источников, таких как [Friedman1975] и [Хювёнен1990]. В математике рекурсия рассматривается в теории рекурсивных функций, являющейся одним из формализмов теории алгоритмов, поэтому определения многих терминов имеют базу в виде очень чётко заданных математических понятий.
Рекурсия – использование самого себя. Также для простоты словом рекурсия называют рекурсивный вызов.
Рекурсивный вызов – прямой или опосредованный вызов функцией самой себя.
Простая рекурсия – рекурсивный вызов, встречающийся не более одного раза в каждой ветви кода функции. Чандра в [Chandra1972] показал, что простая рекурсия всегда может быть сведена компилятором к итеративному циклу, в дальнейшем этот результат был улучшен, что описано ниже.
Терминальная ветвь – ветвь кода рекурсивной функции, завершающая его без дальнейших рекурсивных вызовов.
Бесконечная рекурсия – последовательность рекурсивных вызовов, никогда не выходящая на терминальную ветвь.
Параллельная рекурсия – рекурсия, встречающаяся несколько раз в одной ветви кода функции.
Взаимная рекурсия – вызов двумя или более функциями друг друга.
Рекурсия по значению – рекурсивный вызов, определяющий результат функции.
Рекурсия по аргументам – рекурсивный вызов, участвующий в вычислении аргументов функции.
Рекурсия высокого порядка – случай, когда в определении функции рекурсивный вызов является аргументом вызова этой же самой функции. Обратите внимание, что рекурсия высокого порядка не имеет никакого отношения к функциям высокого порядка. При помощи рекурсии порядка N могут быть описаны вычисления в N+1 вложенных циклах, однако обратное не всегда верно.
Порядок рекурсии – уровень, на котором находится вызов в рекурсии высокого порядка. Обычные используемые на практике случаи рекурсии содержат рекурсивные вызовы нулевого порядка.
Стилизованная рекурсивная функция – некий специальный вид рекурсивной функции нулевого порядка, более общий, чем простая рекурсия, и удовлетворяющий семи довольно замысловато сформулированным требованиям, описанным в статье [Friedman1975] (желающие могут прочитать их по ссылке ниже, страницы 4-5 статьи). Авторы показывают, что стилизованная рекурсивная функция всегда может быть сведена компилятором к итеративному циклу.
Далее приведены строго не определённые понятия.
Хвостовая рекурсия – простая рекурсия, рекурсивный вызов в которой находится в конце кода функции. Многие источники в интернете называют хвостовой рекурсией только такие вызовы, которые непосредственно предшествуют возврату из функции (назовём это хвостовой рекурсией I), в то время как другие интерпретируют хвостовую рекурсию более широко, понимая её как однократный рекурсивный вызов где-либо в последней линейной ветке кода (назовём это хвостовой рекурсией II), или как простую рекурсию. По любому определению, хвостовая рекурсия является частным случаем простой рекурсии.
Оптимизация хвостовой рекурсии, или оптимизация хвостового вызова – преобразование транслятором хвостового вызова функции (необязательно рекурсивного) в линейный (циклический) код. Здесь опять-таки широк диапазон интерпретаций, начиная от простой замены пары команд call/ret на jmp (которая в том числе устраняет хвостовую рекурсию I) и заканчивая более сложными оптимизациями хвостовой рекурсии II и простой рекурсии.
Применение определений
Наш бытовой пример с тушёнкой в рюкзаке представлял собой простую рекурсию с двумя терминальными ветвями и хвостовой рекурсией. Заметим, что рекурсивный код всегда начинается с терминальных ветвей, иначе исполнение программы погрузится в бесконечную рекурсию и никогда до них не дойдёт.
Напишем псевдокод на языке Лисп для наших туристов, чтобы они точно понимали, что делать, проснувшись утром голодными и не помнящими, что у них в рюкзаках:
(defun ищемТушёнку (рюкзак)
(cond
((null рюкзак) nil)
((тушёнка? (car рюкзак)) (car рюкзак))
(t (ищемТушёнку (cdr рюкзак)))))Здесь мы определили функцию ищемТушёнку от параметра-списка рюкзак. Её тело состоит из условного оператора cond, имеющего две терминальные и одну рекурсивную ветку. Рюкзак проверяется на пустоту, затем первый элемент рюкзака (car рюкзак) проверяется специальным предикатом, не тушёнка ли это, затем по третьей ветви, которая предваряется тождественно истинным к этому моменту условием t, уходим на рекурсивный вызов с остатком списка (cdr рюкзак).
Если есть желание довести дело до компьютерного исполняемого кода, определим также наш предикат:
(defun тушёнка? (x) (eq x 'тушёнка))Прямо в таком виде это можно ввести в GNU Common Lisp или SBCL и искать тушёнку.
(ищемТушёнку '(носки хлеб учебникЛиспа штопор
тушёнка смартфон ноутбук
шишка шишка кирпич носовойПлаток
нож кредитка конфета бумажка
зубочистка непонятныйМусор))
ТУШЁНКАКод здесь написан в чисто функциональном стиле, не содержит переменных и присваиваний, что эффективно с точки зрения распределения памяти в статической секции и в куче.
Эффективность рекурсии
Многие программисты считают, что рекурсия неэффективна, так как поедает место на стеке, и ей не место в продуктовом коде. Так ли это?
Безусловно, всякий инструмент нужно применять по назначению, и для перебора чисел от 1 до N, наверное, не надо использовать рекурсивный вызов. Тем не менее, так ли ужаcна рекурсия по сравнению с итерированным циклом?
Современные 64-разрядные системы программирования обычно без труда позволяют распределять до гигабайтов адресного пространства в стековой памяти. Этого хватит буквально на миллиарды вложенных рекурсивных вызовов. Вряд ли когда-нибудь вам понадобится рекурсия такой глубины, и даже если да, то основной проблемой, скорее всего, станет процессорное время, а не стековая память. Цикл с содержательным смыслом на миллиард итераций – это дело серьёзное. Тем не менее, проблема со стеком всё-таки есть, и о ней необходимо помнить.
Однако, как следует из приводившихся выше определений, всякая стилизованная рекурсия и тем более всякая простая рекурсия приводима к виду итеративного цикла. Многие трансляторы об этом знают, в большем или меньшем объёме.
Часто использующимся в компиляторах приёмом оптимизации является оптимизация хвостовой рекурсии, или tail call (tail recursion) optimization. Многим программистам известно, что обычно трансляторы преобразуют хвостовую рекурсию I в эквивалентный цикл, поэтому такая задача, как наш поиск в рюкзаке, после оптимизации не будет занимать место на стеке по мере продвижения в глубины рюкзака.
Однако, интернет полон мнений, что способность компилятора к оптимизации хвостовой рекурсии исчерпывается заменой пары команд call/ret на команду jmp. Поэтому, якобы, даже обычная функция факториала в виде
(defun fact (n)
(cond
((zerop n) 1)
(t (* n (fact (- n 1))))))непригодна к оптимизации и вызовет разрушительный рост стека, так как после рекурсивного вызова остаётся выполнить ещё умножение, и код функции, таким образом, не представляет собой хвостовую рекурсию I. Дальше разделяющие такое мнение люди предлагают "оптимизировать" этот факториал, передавая умножаемые значения вторым параметром.
В действительности, например, у [Penman2018] разобран пример компиляции соответствующего кода в C/C++ и показано, что хвостовая рекурсия II оптимизируется и заменяется на цикл современным компилятором. Попытки выполнить такую оптимизацию вручную ни к чему не приводят на уровне машинного кода и только затрудняют понимание исходного текста.
В общем-то, уже на уровне здравого смысла понятно, что вычисления, записанные в коде после вызова хвостовой рекурсии II, можно переместить из эпилога получаемого цикла в пролог его следующей итерации, чем свести задачу к хвостовой рекурсии I.
На практике оказывается, что компиляторы популярных для вычислений языков (Си/Си++, Фортран) как правило, обеспечивают глубокую оптимизацию хвостовой рекурсии при включённой оптимизации. Трансляторы Лиспа оптимизируют хвостовую рекурсию в разной степени. Трансляторы Джавы и Питона не оптимизирует хвостовую рекурсию по принципиальным соображениям, так как разработчики считают важным сохранять исходную трассировку вызовов.
Оптимизация некоторых рекурсивных вычислительных процессов также может может быть достигнута путём применения механизма мемоизации.
Наконец, вновь надо вернуться к обстоятельству, что уже значение (fact 1000) занимает целый экран цифрами получившегося числа, а в стеке набирается всего 1000 элементов.
Кошмары высокого порядка
Рассмотрим теперь действительно не оптимизируемую автоматически рекурсивную функцию, например, крайне вычислительно ёмкую функцию Аккермана с рекурсией первого порядка, быстро уходящей на огромную глубину. Цитируется по [Хювяйнен1990]:
(defun аккерман (m n)
(cond
((= m 0) (+ n 1))
((= n 0) (аккерман (- m 1) 1))
(t (аккерман (- m 1) (аккерман m (- n 1))))))Значение (аккерман 4 1) считается на моём компьютере в SBCL за 16 секунд с занятым стеком менее 4 мегабайт, то есть стек расходуется со скоростью 256 килобайт в секунду. Таким образом, 4-гигабайтного стека хватило бы на 4.5 часа вычислений рекурсивной функции, ничего по существу не делающей, кроме углубления своей рекурсии. (Для завершённости заметим, что значение (аккерман 4 2) вычислить брутфорсом через её рекурсивное определение пока не в человеческих силах, хотя имеется более быстрый альтернативный алгоритм [Grossman1988]; и полагаем совершенно невероятным, чтобы кому-либо в практических целях понадобился вычислительный процесс, описываемый рекурсией второго и более порядка).
Вывод
Так как это статья о рекурсии, то вывод заключается в том, что выводы представлены в самой этой статье о рекурсии.
Литература
[Хювёнен1990] Э. Хювёнен, Й. Сеппянен. Мир Лиспа. М.: Мир, 1990.
[Chandra1972] A. Chandra. Efficient compilation of linear recursive programs. Stanford AI project, STAN‑CS-72–282, 1972.
Комментарии (46)
gleb_l
00.00.0000 00:00+7
Сэр, не желаете ли с рюкзаком попутешествовать по этой блок-схеме? ;)
Мне кажется, более удачную иллюстрацию отличия одного от другого в мире вряд ли найдёте..
vadimr Автор
00.00.0000 00:00-2Схема отличная! Но, справедливости ради, на ней нарисовано понятие фрактала.
csharpreader
00.00.0000 00:00+6Эмммм... Фрактал ведь и рядом не стоял с рекурсией, да? Только рюкзак, только хардкор.
vadimr Автор
00.00.0000 00:00Фрактал - это всё-таки результат применения очень специфичного рекурсивного алгоритма, бесконечное самоподобие. В то время как практически применяемые рекурсивные алгоритмы, во-первых, всегда конечны, а во-вторых, часто ведут себя по-разному на разных шагах. Поэтому мне кажется существенным, что когда на шаге тушёнка вытягивается, когда штопор, а когда шишка.
aamonster
00.00.0000 00:00+1Спасибо за этот коммент, кстати: что-то в словах "бесконечное самоподобие" вызвало сомнения (ну, я просто помню, что это не основной признак фрактала, название как бы намекает) и я стал гуглить "несамоподобные фракталы". Результаты оказались весьма интересными, вплоть до утверждения, что большинство фракталов не является самоподобными.
gleb_l
00.00.0000 00:00У Вас в статье все правильно описано, кроме примера с рюкзаком - это классический плоский цикл с пост-условием. Как агитплакат на чиновничьи деньги в современном мире - плакат “за Родину”, а картинка из Интернета сами понимаете с кем.
vadimr Автор
00.00.0000 00:00Когда я в школе изучал рекурсию, я не знал про циклы. Возможно, поэтому я в описанной ситуации вижу в первую очередь рекурсию.
klvov
00.00.0000 00:00+3Да уж, дочитав до первой вставки "псевдокода на языке Лисп" я понял, что эту вставку никто никогда не поймет, если он не изучал тему символьного программирования ранее, а кто изучал, уже, скорее всего, будет иметь хотя бы приблизительное представление о том, что такое рекурсия. Чтобы понять, что в ней написано, надо уже знать, что такое S-выражения, скобочная нотация, defun, cond, null, и t. И даже если до этих перечисленных понятий еще можно как-то догадаться, то что такое car и cdr - надо только знать. Что ж, вот как они расшифровываются: "car" расшифровывается как "content of address register", а "cdr" - "content of decrement register", а семантика их, соответственно, исторически значит "первый элемент списка" и "остаток списка". Скорее всего, в первых LISP-машинах в этих регистрах хранились соответствующие указатели (но это не точно).
vadimr Автор
00.00.0000 00:00Справедливое замечание, но я постарался семантику объяснить сразу после кода.
Язык Лисп нравится мне тем, что он очень формален и математичен. Код программы сам представляет собой те самые списки символов, которые он и обрабатывает. Этим он по своей глубокой структуре подобен машинному коду, позволяя программам полностью рефлектировать самих себя. В этом тоже есть рекурсия :)
Всё-таки другие языки по сравнению с Лиспом уродливы для объяснения вопросов вычислимости. Хотя гораздо более практичны.
aamonster
00.00.0000 00:00+1Хе-хе, вот с последним утверждением можно поспорить – см. вторую теорему Чёрча-Россера, она же теорема о стандартизации.
Корявый пересказ с минимумом терминов: если записать какое-то лямбда-выражение (лисповская запись вполне подойдёт: первый элемент списка – функция, дальше аргументы) и это выражение в принципе можно вычислить – то есть определённый порядок вычисления ("нормальный порядок редукции"), который точно подойдёт. Но Лисп использует не его, а аппликативный порядок.
Пример: пусть есть функция, которая возвращает бесконечный список чисел. Надо найти, в какой позиции встречается число 13. На Лиспе такое не прокатит (ну, в лоб), для Хаскеля – просто ищем по результату функции)))
vadimr Автор
00.00.0000 00:00Хаскель интересный язык, но он ушёл от идеи вычислимости текста программы.
Надо сказать, что и в Common лиспе с этим не то чтобы совсем здорово на практике, но как концепция срабатывает. И есть Scheme.
aamonster
00.00.0000 00:00Забавно, но Хаскель только и занимается что вычислением тела программы). Такой трюк, чтобы в рамках чисто функционального языка (без side-эффектов, присваивания и т.п.) взаимодействовать с внешним миром: просто пишем функцию, которой можно скормить в качестве аргумента что-то из внешнего мира и получить как результат новую функцию.
vadimr Автор
00.00.0000 00:00Хаскель позволяет писать функции высших порядков, выводя семантику новых функций, но работой с текстом программы он не занимается. А это важно для ряда вопросов, связанных с формальными грамматиками.
Поправьте меня, если я ошибаюсь, но я не представляю, как реализовать, например, такую вот штуку на Хаскеле. Не именно обеспечить мемоизацию, а построить подобный алгоритм преобразования текста функции.
Кстати, забавно, что некоторые наиболее идеологические чистые трансляторы Лиспа оказалось невозможно портировать на Apple Silicon из-за неотключаемого W^X.
aamonster
00.00.0000 00:00Ну, такая штука на Хаскеле бессмысленна, проблема будет не в том, чтобы мемоизировать, а в том, чтобы
отключитьобойти имеющуюся мемоизацию).Ну а в плане работы с исходниками – теоретически, можно было бы преобразовывать thunks (недовычисленные хаскелевские выражения) обратно в код. По сути, они очень похожи на лисповские выражения, только порядок вычисления другой (что позволяет, к примеру, сделать if и cond обычными функциями, а не специальными конструкциями, как в lisp)
0xd34df00d
00.00.0000 00:00+1Зачем для формальных грамматик работать с текстом программы?
Олсо, есть template haskell, там как раз можно на хаскеле работать с текстом самой программы.
Олсо, для мемоизации есть такое, например.
vadimr Автор
00.00.0000 00:00А что такое формальная грамматика, как не порождающая сама себя последовательность символов?
Конечно, на практике обычно отделяют порождаемый код от исполняемого. Но в теоретических моментах полезно иметь удобную абстракцию.
Код реализации Лиспа, написанный на Лиспе, занимает две страницы. Я помню, ещё на 8-разрядной машине работал с транслятором Лиспа, у которого загрузочный модуль был килобайт эдак 30, из которых значительную часть занимала реализация большинства функций просто в виде текстового лисповского кода, определяющего их через основные функции. Язык определяет сам себя.
В практическом плане это позволило окончательно зафиксировать стандарт Лиспа в 1994 году и все дальнейшие изменения проводить библиотеками в исходном коде.
0xd34df00d
00.00.0000 00:00А что такое формальная грамматика, как не порождающая сама себя последовательность символов?
Она не порождает сама себя. Её порождают некоторые правила. И эти правила вполне себе можно удобно описывать и в негомоиконных языках.
Конечно, на практике обычно отделяют порождаемый код от исполняемого. Но в теоретических моментах полезно иметь удобную абстракцию.
В теоретических моментах тоже удобно разделять language и metalanguage. Более того, не могу придумать ситуацию, в которой совпадение описываемого грамматикой языка и метаязыка, описывающего грамматику, было бы удобно.
Код реализации Лиспа, написанный на Лиспе, занимает две страницы.
Очень круто, но ≥99.9% программистам в ≥99.9% ситуаций не нужно.
vadimr Автор
00.00.0000 00:00Она не порождает сама себя. Её порождают некоторые правила. И эти правила вполне себе можно удобно описывать и в негомоиконных языках.
Эти правила в общем случае могут сами состоять из используемых грамматикой символов. В связи с чем строится понятие самоприменимых грамматик.
В теоретических моментах тоже удобно разделять language и metalanguage. Более того, не могу придумать ситуацию, в которой совпадение описываемого грамматикой языка и метаязыка, описывающего грамматику, было бы удобно.
Например, чтобы далеко в теорию не зарываться, доказательство теоремы останова, которое является частным случаем решения проблемы самоприменимости.
Очень круто, но ≥99.9% программистам в ≥99.9% ситуаций не нужно.
На самом деле, вся идеология работы в Лиспе построена на динамической модификации кода и расширении языка проблемно-ориентированными конструкциями.
0xd34df00d
00.00.0000 00:00+1Эти правила в общем случае могут сами состоять из используемых грамматикой символов. В связи с чем строится понятие самоприменимых грамматик.
И часто вы работаете с грамматиками, где терминалы влияют на применимые правила?
Но это, впрочем, неважно. Вам для этого всё ещё не нужна гомоиконность языка.
Например, чтобы далеко в теорию не зарываться, доказательство теоремы останова, которое является частным случаем решения проблемы самоприменимости.
…и где метаязык, на котором строится доказательство, не является языком, о котором вы рассуждаете.
Но, впрочем, если мы говорим именно о формальных грамматиках в смысле, ну, всяких там контекстно-свободных языков и прочего подобного, то это всё тоже неважно: на этом этапе у вас нет семантики. И, кстати, теорема останова тут неприменима просто потому, что она говорит о семантике, а не о синтаксисе, и та же более общая теорема Райса говорит о нетривиальных семантических свойствах программ, инвариантных относительно языка выражения.
Если же мы вернёмся к грамматикам, то лично мне куда интереснее доказать, например, что данный парсер всегда завершается. И тут снова языки из ML-семейства с более продвинутыми типами уделывают лисп.
На самом деле, вся идеология работы в Лиспе построена на динамической модификации кода и расширении языка проблемно-ориентированными конструкциями.
Проблемно-ориентированные конструкции можно добавлять и в не-лисповых языках, где статичнее некуда, и при этом синтаксис не будет вырвиглазным, а будет очень близок к математической нотации:
Любая же динамическая модификация затрудняет рассуждения о коде. Чем больше вещей вы делаете статически, тем лучше.
vadimr Автор
00.00.0000 00:00Если вы внимательно посмотрите на доказательство теоремы останова, оно как раз оперирует написанием программы, анализирующей свой собственный код. Само доказательство написано на метаязыке, так как доказательство - это не алгоритм, но используемый в нём алгоритм самоприменяется. И оно оперирует чисто синтаксическим алгоритмом, вынося семантику останова, если так можно выразиться, в свободный параметр синтаксиса.
Любая же динамическая модификация затрудняет рассуждения о коде.
Чего тут думать, тут трясти надо. В смысле, динамический подход построен на автоматическом анализе и преобразовании кода.
Проблемно-ориентированные конструкции можно добавлять и в не-лисповых языках, где статичнее некуда, и при этом синтаксис не будет вырвиглазным, а будет очень близок к математической нотации:
Посмотрите, как происходит разработка на Лиспе. Я примерно об этом говорю:
Наша дискуссия, однако, напомнила мне "Анафем" Стивенсона.
0xd34df00d
00.00.0000 00:00Если вы внимательно посмотрите на доказательство теоремы останова, оно как раз оперирует написанием программы, анализирующей свой собственный код.
Не нужен в доказательстве никакой анализ собственного кода. Ну только если вы, упрощая, вызов функции и рекурсию не считаете анализом собственного кода.
Там обычный диагональный метод — предполагаем, что есть алгоритм (нам совершенно наплевать, как он работает), по номеру алгоритма i и номеру входа j определяющий, завершается ли i-ый алгоритм на j-ом входе, строим табличку, и строим алгоритм A, на j-ом входе выдающий отрицание¹ значения в ячейке (j, j) в табличке (и нам тут снова наплевать на исходный код — это просто композиция функций). Ну и получаем очевидное противоречие.
¹ например,
if (Table[i, j] == halts) { return 0; } else { while (true) {} }Здесь нет ничего принципиально нового по сравнению с доказательством, например, несчётности множества вещественных чисел. Но я бы не сказал, что вещественные числа анализируют свой исходный код.
В смысле, динамический подход построен на автоматическом анализе и преобразовании кода.
Кто мешает это делать статически, как это делает, например, template haskell?
Посмотрите, как происходит разработка на Лиспе. Я примерно об этом говорю:
Я не люблю смотреть (тем более, видео на час в 360p/10fps), я люблю читать. Можно почитать исходники, где строится адекватный, удобный и читабельный eDSL для какой-либо данной задачи?
vadimr Автор
00.00.0000 00:00Там обычный диагональный метод
Диагональный метод является только заключительным шагом доказательства. Основная идея – это как раз выяснение значений, которые вы назвали Table [i, j], предполагающее, что программа анализирует исходный текст программ, в том числе и самой себя.
(нам совершенно наплевать, как он работает)
Вовсе не наплевать. Для начала, нам надо ещё доказывать, что любой вообще возможный конечный алгоритм имеет конечную запись на используемом языке (это не тривиальное утверждение).
Ну и почему для нас вообще важна эта программа и откуда она возникла в доказательстве? Потому что она представляет собой неподвижную точку. А дальше уже от понятия неподвижной точки идём к самоприменимым грамматикам.
Здесь нет ничего принципиально нового по сравнению с доказательством, например, несчётности множества вещественных чисел.
Множество вещественных чисел вполне представимо актуально. Множество алгоритмов конструируется только потенциально. Хотя множество цепочек с текстами программ актуально.
Я не люблю смотреть (тем более, видео на час в 360p/10fps), я люблю читать. Можно почитать исходники, где строится адекватный, удобный и читабельный eDSL для какой-либо данной задачи?
Вопрос-то здесь не в исходниках, а в технологии процесса программирования. Конечно, перемотав ролик в конец вы увидите исходники (я его, впрочем, до конца не смотрел), но дело не в этом.
0xd34df00d
00.00.0000 00:00Основная идея – это как раз выяснение значений, которые вы назвали Table [i, j], предполагающее, что программа анализирует исходный текст программ, в том числе и самой себя.
Зачем? Вам не нужно «анализировать текст», вы просто занумеровываете все возможные тексты программ (их счётное число) и радуетесь жизни. Как именно алгоритм что-то там решает, вам тоже неважно — доказательство его несуществования не опирается на какие-либо детали его работы.
Для начала, нам надо ещё доказывать, что любой вообще возможный конечный алгоритм имеет конечную запись на используемом языке
Вообще это зависит от конкретного формализма, но это может следовать напрямую из определений.
Ну и почему для нас вообще важна эта программа и откуда она возникла в доказательстве?
Какая именно — эта? Выдающая ответ, завершается ли другой алгоритм или нет? Ну, потому, что мы именно про эту программу хотим что-то доказать.
Программа-контрпример? Потому, что это контрпример.
Множество вещественных чисел вполне представимо актуально. Множество алгоритмов конструируется
Множество вещественных чисел, которые вы можете алгоритмически сконструировать, тоже счётно, если что. Откуда следует, что «неконструируемых» вещественных бесконечно больше, чем вычислимых.
только потенциально. Хотя множество цепочек с текстами программ актуально.
Множество алгоритмов является подмножеством (собственным или нет — здесь неважно) множества текстов программ.
vadimr Автор
00.00.0000 00:00Множество алгоритмов является подмножеством (собственным или нет — здесь неважно) множества текстов программ.
Это очень спорное утверждение и, по-видимому, неверное. На самом деле, все обычные теоремы о вычислимости оперируют дискретными последовательными операциями, равномощными смене состояний машины Тьюринга. А никто ведь не обещал, что любой алгоритм можно так сериализовать. Я не уверен, что, например, квантовый компьютер равномощен машине Тьюринга. То есть я хочу сказать, что не вижу, почему бы не существовать алгоритму, непредставимому в виде текста.
Для начала, нам надо ещё доказывать, что любой вообще возможный конечный алгоритм имеет конечную запись на используемом языке
Вообще это зависит от конкретного формализма, но это может следовать напрямую из определений.
Например, определим язык Лисп++, отличающийся от Лиспа всего двумя деталями:
(1) Программа на Лисп++ состоит ровно из одного S-выражения (это чисто стилистическое преобразование, которое не умаляет возможностей Лиспа, так как любую последовательность S-выражений можно объединить в одно при помощи PROGN).
(2) Грамматика Лисп++ содержит правило, согласно которому к любой программе необходимо добавить в конец правую скобку.
Таким образом, язык Лисп++ будет иметь следующие особенности:
a) любая программа на Лисп++ имеет бесконечную длину, так как заканчивается бесконечным количеством правых скобок, возникающих от бесконечно рекурсивного применения правила (2);
б) на Лисп++ можно написать любую программу, которую можно написать на Лисп, и она будет исполнена и завершится за конечное время, если это происходит с прообразом программы на Лиспе (на самом деле транслятору Лисп++ в силу свойства (1) неинтересны символы после S-выражения).
Очевидно, что к языку Лисп++ неприменимо доказательство теоремы останова, хотя в смысле способности к останову он ничем не отличается от языка Лисп.
0xd34df00d
00.00.0000 00:00А никто ведь не обещал, что любой алгоритм можно так сериализовать.
Обещали по любому определению языка записи алгоритмов.
Я не уверен, что, например, квантовый компьютер равномощен машине Тьюринга.
Причём тут вообще квантовые компьютеры? Если там используются какие-то строки из каких-то алфавитов для записи тамошних программ, и здесь используются какие-то строки из каких-то алфавитов, то их непустое пересечение ни о чём не говорит. Язык — это просто синтаксис и средство выражения.
Кстати, у меня есть чувство, что квантовые компьютеры вычисляют вещи, являющиеся подмножеством выразимых на классической машине Тьюринга, но я недостаточно хорошо разбираюсь в квантах, чтобы это строго доказать. Разница там, по идее, только в сложности вычислений и асимптотиках её роста с ростом входа.
Очевидно, что к языку Лисп++ неприменимо доказательство теоремы останова, хотя в смысле способности к останову он ничем не отличается от языка Лисп.
Он отличается хотя бы тем, что вы за конечное время не распознаете программу на Лисп++.
Я бы сказал, что для языка Лисп++ неприменимо не то что доказательство, а сама формулировка этой теоремы.
vadimr Автор
00.00.0000 00:00> А никто ведь не обещал, что любой алгоритм можно так сериализовать.
Обещали по любому определению языка записи алгоритмов.
Это утверждение (о представлении любого интуитивно возможного алгоритма в виде машины Тьюринга, лямбда-выражения и т.п.) известно как тезис Чёрча-Тьюринга. Оно представляет собой эмпирическое оценочное суждение, которое не имеет формальных оснований, и которое большинство математиков приняло просто для удобства (хотя, например, Гёдель и Пост возражали).
Сам Тьюринг в поздние годы изобрёл машину Тьюринга с оракулом – одну из формально возможных моделей машины, которая решает задачи, нерешаемые для классической машины Тьюринга (т.е. гиперкомпьютера), но такой гиперкомпьютер, как он предложил, представляется физически невозможным построить. (В принципе, и так интуитивно понятно, что если бы Бог в ответ на молитву сообщал верные ответы на программно неразрешимые вопросы, то это бы сильно нас продвинуло в практическом решении вычислительных задач).
Что касается квантовых компьютеров, то в используемой сейчас конструкции они сводимы к машине Тьюринга, но есть научные предположения, что можно было бы на квантовомеханических принципах построить гиперкомпьютер.
vadimr Автор
00.00.0000 00:00Тут, конечно, можно придраться к определению алгоритма, который часто понимается именно как последовательность действий. Но в проблеме останова по её смыслу речь идёт об алгоритме как просто о способе.
0xd34df00d
00.00.0000 00:00Рекурсия хороша, когда она фундирована. Ну и структуры в голом бестиповом лямбда-исчислении мало, это неинтересный объект.
Голая рекурсия, кстати, примерно похожа на goto — можно выразить все, но в этом и проблема. Интереснее ограничивать выразительность и пользоваться схемами.
csharpreader
Вы точно сами понимаете, что такое рекурсия?
vadimr Автор
Я точно сам понимаю, что такое рекурсия. В процитированных вами полутора терминальных ветвях алгоритма её нет.
Что вы хотели сказать своим вопросом?
csharpreader
Вы сами написали, что это пример рекурсии, понятный даже ребёнку.
На мой скромный взгляд, в рюкзаке должен быть рюкзак. В котором (внезапно!) может быть и тушёнка. Или снова рюкзак, etc.
vadimr Автор
Никогда в жизни не встречал туристов, носящих рюкзак в рюкзаке. Не думаю, что запутывание модели предметной области таким образом способно что-то прояснить.
Рекурсивен в данном случае алгоритм наших действий, а не структура рюкзака.
csharpreader
Здрасьте-приехали. А как же «решение задачи через сведение её к самой себе»? Что-то в копошении в рюкзаке нет подобия задачи «самой себе». Простой поиск.
vadimr Автор
Задача поиска тушёнки в рюкзаке с N предметами сводится к задаче поиска тушёнки в рюкзаке с N-1 предметами, если первый вынутый предмет не тушёнка и есть ещё предметы. Там же код написан ниже.
csharpreader
Так-то да. Но метафора с рюкзаком по-прежнему кажется мне неудачной.
vadimr Автор
По-моему, метафора с рюкзаком обладает двумя полезными свойствами:
Это реальная жизненная ситуация, которая точно показывает, что происходит, когда мы вынимаем предметы из рюкзака по одному.
После понимания этой ситуации в жизни она позволяет написать рекурсивный код, понятный ребёнку, явным образом отображающий рассмотренные ранее действия.
Конечно, можно было бы происходящее с тем же успехом объяснить и циклом, поскольку простая рекурсия вообще эквивалентна циклу. В этом смысле нельзя сказать, что поиск в рюкзаке сам по себе рекурсивен. Но он может быть описан рекурсивным алгоритмом, что я и имел в виду.
csharpreader
Мне кажется, для «понимания ребёнком» гораздо нагляднее работают метафоры матрёшки или рекурсивного вызова по вытягиванию репки. Всё-таки, это точнее «по духу» рекурсии.
Ладно, я понял вас, рюкзак – так рюкзак.
vadimr Автор
Вытягивание репки в моём понимании вообще не является примером рекурсии, это суперпозиция семи разных функций.
Что касается матрёшки, то для меня этот пример не очень очевиден. Видимо, у вас в голове рекурсия каким-то образом разворачивается в пространстве (то же и в вопросе с фракталом), а у меня – во времени.
csharpreader
Невероятно интересно (я искренне). Никогда не думал об этом в таком ключе. Ради одной этой формулировки стоило затеять эту ветвь обсуждения.
aamonster
С матрёшкой в качестве примера получилась бы абсолютно прекрасная статья, если взять матрёшки 90-х, с генсеками и т.п. (Ленин, в нём Сталин и так далее до Горбачёва). А на КДПВ поставить кадр из Ширли-Мырли с Табаковым – "Я этого [] в Химках видел. Деревянными членами торгует!" (Деревянные члены тут – это матрёшки с членами ПолитБюро)
aamonster
Да не, приемлемо. Тем более на лиспе, где основная структура данных – пара car.cdr, и представление рюкзака будет именно таким: в car первый предмет, в cdr рюкзак со всеми остальными.
Upd: Язык диктует мышление. Было бы интересно, как тот же автор написал бы эту статью, если бы был привычен к простой императивщине. Или, напротив, если бы для него родным языком был Хаскель (ленивое вычисление сильно меняет мышление – можно использовать бесконечные списки и всякое такое, что сильно упрощает и сокращает код, делая его очень читабельным, зато оценить требования по времени и памяти на порядок сложнее).
0xd34df00d
Рюкзак — это просто мутабельная ссылка на иммутабельный список.
vadimr Автор
Довольно сложно проинтерпретировать такое понимание в реальном мире.
dreesh
Почему это? Если рюкзак из статьи, то как раз содержимое изменяется, а рюкзак тот же.
0xd34df00d
Да, поэтому сама ссылка на содержимое рюкзака та же, и она не меняется.
Условно, у вас есть
из которого вы можете достать предмет
backpackне меняется, меняется его содержимое.