IV. Рекурсивные функции-удачный для своего времени паллиатив правильной модели исполнения алгоритмов
. К оглавлению . Показать весь текст .
Возникает вопрос - почему логики в первой половине 20 века не воспользовались методикой перенесения исполнения программ машиной Тьюринга в некоторую функцию арифметики, подобно тому, что описана в начале данной статьи? Пусть у них не было теории строк, пусть для арифметики выполнен примат целостности относительно строк многосимвольного алфавита (пока это гипотеза), пусть строгие доказательства в арифметике получаются неполиномиально большими относительно размеров чисел в позиционном представлении. Но для конечных данных методика с «протоколом исполнения», вроде, позволяет перенести - пусть со всеми указанными издержками и неформальным использованием логики строк - исполнение программы машиной Тьюринга на уровень доказательств арифметики о некоторой функции.
Я пишу «вроде позволяет» только потому, что не реализовывал весь этот гипотетический план, и не могу быть вполне уверен, что не встретил бы в процессе реализации принципиальные трудности в построении логических выводов. Но если верить собственной интуиции, то таких трудностей там я не вижу. К тому же все перечисленные издержки переноса алгоритмов в арифметику есть и для рекурсивных функций.
Я думаю, логики до 1940-х годов просто не знали, что алгоритмы - это тексты. В смысле, алгоритмы можно записывать как программные тексты. Первые ЭВМ, насколько я читал, стали применятся только в 1940-х, ещё очень мало. А к началу 1940-х ключевое для логических исследований в то время математическое сообщество - немецкое - было, фактически, уничтожено в фашистской Германии. Не столько физически (хотя Давид Гильберт не пережил разгром своего института и немецкой математики, и умер в 1943 г.), сколько как сообщество, как сформировавшийся за долгие годы коллектив профессионалов, общающихся свободно о математике, а не запуганных людей, думающих о выживании своём и тех, кто им дорог.
Бывают незаменимые люди - одним из которых был Гильберт. И без него уже не нашлось после 2-й мировой войны того, кто смог бы увидеть принципиальную важность построения теорий для строк и алгоритмов на базе строк. А сейчас мне легко, конечно, замечать «невнимательность» других, когда перед моими глазами изменившийся от программных текстов и заполнившийся «живущими» алгоритмами мир. Тот мир, которого не было перед их глазами.
Конечно, остался Гёдель, который был гениален в способности находить решения в математике - даже при минимальных теоретических ресурсах. Но самые принципиальные задачи, достойные Гёделя, уже не ставил Гильберт. Удивительно, что 2 таких человека жили в одно время, а в том математическом сообществе было много выдающихся людей, но и задачи были такие, что без одного Гильберта продолжение столь же принципиального и продуктивного движения вперёд стало невозможным.
И Гёдель далеко не был счастлив в США, без «своего» австрийского математического сообщества, которого больше не было. И конец его жизни был печальным, хоть и умер он в пожилом возрасте - дело ведь далеко не только в формальном статусе и материальном достатке для таких людей.
И Тьюринг, имя которого тут постоянно упоминается («машина Тьюринга») был подвергнут по сути калечащему наказанию из-за обвинения в гомосексуализме, и умер слишком рано в своей Англии. Поэтому кто бросит камень в то математическое сообщество, что оно не сделало больше? Только не я. А то математическое сообщество сделало беспрецедентно много, для краткого периода, пока оно было живо как сообщество.
Возвращаясь к рассмотрению вопроса о причинах появления рекурсивных функций в качестве модели, отметим, что едва ли математики могли тогда рассматривать алгоритмы (для машины Тьюринга, например) как тексты. Они совсем недавно придумали рассматривать математические формулы как тексты и ставить им в соответствие гёделевы номера. Теория Пеано была лишь недавно сформулирована. И недавно у них появилось понимание о формулах - «представляющих» функции. Даже в классических «Основаниях математики» Гильберта и Бернайса ещё используется вместо соответствующих формул йота-правило (значок ι «тот, который») и доказательства о том, как этот значок устранять. А тогда ведь уже доказаны с формальными строгостями теоремы Гёделя о неполноте (во втором томе).
Поэтому математикам была нужна модель, построенная из математических формул - столь же универсальная для вычислений, что и машина Тьюринга. В плане «столь же универсальная» они немного ошиблись (как мы знаем из предыдущей статьи и примата целостности для рекурсивных функций), но ошибка не касалась интересных им алгоритмов, работающих с конечными гёделевыми номерами формул. А модель рекурсивных функций уже понятно как «представить» (значение этого термина мы разбирали в разделе II данной статьи) в арифметике. А вот в арифметике математики уже умели работать с записью формул как с данными (гёделевы номера формул).
Поэтому и появилась - как мне думается - такая «не реалистичная» модель, как рекурсивные функции. Обычно модели опираются на реальность, поэтому обычно они имеют более обширную логику, чем теории, для которых они являются интерпретациями (машина Тьюринга, абак и т.п.) А здесь мы видим в качестве модели вообще формулы - даже не понятно (нет реалистических подробностей) с какими данными эти формулы имеют дело. Но зато это те формулы, которые можно рассматривать как тексты, ставить им в соответствие гёделевы номера и включить исследование алгоритмов по методике работы с гёделевыми номерами как часть реализации программы Гильберта.
Таким образом, то, какие требования к теориям и моделям должны предъявляться - не является каким-то бесспорным абсолютом. Сумели же решить самые принципиальные вопросы в Истории математики, имея лишь «скрипку с одной струной». Но нет смысла продолжать играть на «скрипке с одной струной», когда уже доступны отличные «скрипки» со всеми «струнами».
Пример удобства строк - для конкретных значений - у этих объектов есть внутренняя структура. Даже если мы пользуемся арифметическим способом записи для чисел, то и в этом случае конкретные строки могут быть записаны в формулах в пределах линейной зависимости размера данной записи от размера «обычной» записи строк:
Chr(0′′′′) ⋅ Chr(0′′) ⋅ Chr(0′′′′′′′′′′′′′′) ⋅ Chr(0′′′′′′) ⋅ Chr(0′)
Дело в том, что под знаком Chr() находится ноль с ограниченным количеством операций увеличения на 1 - количество операций ограничено размером алфавита. А для пустой строки у нас есть специальная предметная константа - ⊖.
Когда я приступал к написанию данной статьи, то не знал, что обнаружу использование логики строк, без которого нельзя обойтись, в доказательствах самых принципиальных теорем логики. Хотя эти доказательства я читал, и знал уже не один десяток лет.
Конечно, алгоритмы имеют гораздо большее практическое значение и именно из-за них я начал исследование в направлении теории компьютерных строк. Но теория в истории науки (тем более в истории математики) ничуть не менее значима, чем практика. Иметь основания для развития теории компьютерных строк не только в прикладной плоскости, но и в логическом «сердце» математики - более принципиальный аргумент для теоретиков, на мой взгляд.
Но, в любом случае, у нас теперь есть и практические, и теоретические предпосылки для развития теории компьютерных строк.