dmitgu

Categories:

IV. Рекурсивные функции-удачный для своего времени паллиатив правильной модели исполнения алгоритмов

. К оглавлению . Показать весь текст .

Возникает вопрос – почему логики в первой половине 20 века не воспользовались методикой перенесения исполнения программ машиной Тьюринга в некоторую функцию арифметики, подобно тому, что описана в начале данной статьи? Пусть у них не было теории строк, пусть для арифметики выполнен примат целостности относительно строк многосимвольного алфавита (пока это гипотеза), пусть строгие доказательства в арифметике получаются неполиномиально большими относительно размеров чисел в позиционном представлении. Но для конечных данных методика с «протоколом исполнения», вроде, позволяет перенести – пусть со всеми указанными издержками и неформальным использованием логики строк – исполнение программы машиной Тьюринга на уровень доказательств арифметики о некоторой функции. 

Я пишу «вроде позволяет» только потому, что не реализовывал весь этот гипотетический план, и не могу быть вполне уверен, что не встретил бы в процессе реализации принципиальные трудности в построении логических выводов. Но если верить собственной интуиции, то таких трудностей там я не вижу. К тому же все перечисленные издержки переноса алгоритмов в арифметику есть и для рекурсивных функций.

Я думаю, логики до 1940-х годов просто не знали, что алгоритмы – это тексты. В смысле, алгоритмы можно записывать как программные тексты. Первые ЭВМ, насколько я читал, стали применятся только в 1940-х, ещё очень мало. А к началу 1940-х ключевое для логических исследований в то время математическое сообщество – немецкое – было, фактически, уничтожено в фашистской Германии. Не столько физически (хотя Давид Гильберт не пережил разгром своего института и немецкой математики, и умер в 1943 г.), сколько как сообщество, как сформировавшийся за долгие годы коллектив профессионалов, общающихся свободно о математике, а не запуганных людей, думающих о выживании своём и тех, кто им дорог.

Бывают незаменимые люди – одним из которых был Гильберт. И без него уже не нашлось после 2-й мировой войны того, кто смог бы увидеть принципиальную важность построения теорий для строк и алгоритмов на базе строк. А сейчас мне легко, конечно, замечать «невнимательность» других, когда перед моими глазами изменившийся от программных текстов и заполнившийся «живущими» алгоритмами мир. Тот мир, которого не было перед их глазами.

Конечно, остался Гёдель, который был гениален в способности находить решения в математике – даже при минимальных теоретических ресурсах. Но самые принципиальные задачи, достойные Гёделя, уже не ставил Гильберт. Удивительно, что 2 таких человека жили в одно время, а в том математическом сообществе было много выдающихся людей, но и задачи были такие, что без одного Гильберта продолжение столь же принципиального и продуктивного движения вперёд стало невозможным. 

И Гёдель далеко не был счастлив в США, без «своего» австрийского математического сообщества, которого больше не было. И конец его жизни был печальным, хоть и умер он в пожилом возрасте – дело ведь далеко не только в формальном статусе и материальном достатке для таких людей.

И Тьюринг, имя которого тут постоянно упоминается («машина Тьюринга») был подвергнут по сути калечащему наказанию из-за обвинения в гомосексуализме, и умер слишком рано в своей Англии. Поэтому кто бросит камень в то математическое сообщество, что оно не сделало больше? Только не я. А то математическое сообщество сделало беспрецедентно много, для краткого периода, пока оно было живо как сообщество. 

Возвращаясь к рассмотрению вопроса о причинах появления рекурсивных функций в качестве модели, отметим, что едва ли математики могли тогда рассматривать алгоритмы (для машины Тьюринга, например) как тексты. Они совсем недавно придумали рассматривать математические формулы как тексты и ставить им в соответствие гёделевы номера. Теория Пеано была лишь недавно сформулирована. И недавно у них появилось понимание о формулах – «представляющих» функции. Даже в классических «Основаниях математики» Гильберта и Бернайса ещё используется вместо соответствующих формул йота-правило (значок ι «тот, который») и доказательства о том, как этот значок устранять. А тогда ведь уже доказаны с формальными строгостями теоремы Гёделя о неполноте (во втором томе).

Поэтому математикам была нужна модель, построенная из математических формул – столь же универсальная для вычислений, что и машина Тьюринга. В плане «столь же универсальная» они немного ошиблись (как мы знаем из предыдущей статьи и примата целостности для рекурсивных функций), но ошибка не касалась интересных им алгоритмов, работающих с конечными гёделевыми номерами формул. А модель рекурсивных функций уже понятно как «представить» (значение этого термина мы разбирали в разделе II данной статьи) в арифметике. А вот в арифметике математики уже умели работать с записью формул как с данными (гёделевы номера формул). 

Поэтому и появилась – как мне думается – такая «не реалистичная» модель, как рекурсивные функции. Обычно модели опираются на реальность, поэтому обычно они имеют более обширную логику, чем теории, для которых они являются интерпретациями (машина Тьюринга, абак и т.п.) А здесь мы видим в качестве модели вообще формулы – даже не понятно (нет реалистических подробностей) с какими данными эти формулы имеют дело. Но зато это те формулы, которые можно рассматривать как тексты, ставить им в соответствие гёделевы номера и включить исследование алгоритмов по методике работы с гёделевыми номерами как часть реализации программы Гильберта.

Таким образом, то, какие требования к теориям и моделям должны предъявляться – не является каким-то бесспорным абсолютом. Сумели же решить самые принципиальные вопросы в Истории математики, имея лишь «скрипку с одной струной». Но нет смысла продолжать играть на «скрипке с одной струной», когда уже доступны отличные «скрипки» со всеми «струнами».

Пример удобства строк – для конкретных значений – у этих объектов есть внутренняя структура. Даже если мы пользуемся арифметическим способом записи для чисел, то и в этом случае конкретные строки могут быть записаны в формулах в пределах линейной зависимости размера данной записи от размера «обычной» записи строк:

Chr(0′′′′) ⋅ Chr(0′′) ⋅ Chr(0′′′′′′′′′′′′′′) ⋅ Chr(0′′′′′′) ⋅ Chr(0′) 

Дело в том, что под знаком Chr() находится ноль с ограниченным количеством операций увеличения на 1 – количество операций ограничено размером алфавита. А для пустой строки у нас есть специальная предметная константа – ⊖.  

Когда я приступал к написанию данной статьи, то не знал, что обнаружу использование логики строк, без которого нельзя обойтись, в доказательствах самых принципиальных теорем логики. Хотя эти доказательства я читал, и знал уже не один десяток лет. 

Конечно, алгоритмы имеют гораздо большее практическое значение и именно из-за них я начал исследование в направлении теории компьютерных строк. Но теория в истории науки (тем более в истории математики) ничуть не менее значима, чем практика. Иметь основания для развития теории компьютерных строк не только в прикладной плоскости, но и в логическом «сердце» математики – более принципиальный аргумент для теоретиков, на мой взгляд.

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

Error

default userpic

Your reply will be screened

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.