к Оглавлению
2.1. Говоря «число» мы обычно подразумеваем десятичную запись числа, а для компьютера –2^8-ричную или 2^{16}-ричную. И со всеми нашими правилами «сложения столбиком», «умножения столбиком» и т.п. все эти объекты полностью соответствуют аксиомам математики о числах. Назовём «обычную» модель интерпретации «интерпретация C» (компьютерная интерпретация), а стандартную модель интерпретации – «интерпретация S».
Разумеется, между этими моделями интерпретации есть связь. Когда я в бухгалтерской программе считаю приходы и расходы единиц товара на складе по документам, то я (и компьютер) использую модель интерпретации C. Но когда я иду на склад и провожу там инвентаризацию, то считаю я – каждую единицу. И вот в процессе подсчёта единиц товара я опираюсь на интерпретацию S, хотя записи в «чистовик» инвентаризационной ведомости я вношу в интерпретации C.
И представлять логические формулы и программные тексты для алгоритмов мы будем в рамках интерпретации C. То есть так, как это делают компьютеры – где для разных символов (цифр, букв, знаков препинания, математических символов и др.) есть свои числа, записанные либо байтом (кодировка ASCII) или парой байт (кодировка UTF-8) или аналогичным образом. А из этих символов составляются числа и тексты – путем записи символов в определенном порядке в последовательности «друг за другом».
Разумеется, все теоремы, доказанные в эпоху Гильберта, остаются в силе и для интерпретации C, потому что она полностью соответствует тем аксиомам Пеано (например), которые применялись для интерпретации S.
Вспоминается известная шутка математиков того времени, что в геометрии вместо понятия «прямые» можно использовать и пивные кружки. Главное – чтоб они соответствовали аксиомам геометрии.
Таким образом, можно считать, что как формулы и числа записаны в данной работе – так же они представлены и в нашей интерпретации – где каждый символ формулы/программы/доказательства представлен соответствующим кодом на соответствующем месте строки. И этими строками будут оперировать наши логические формулы и алгоритмы.
Замечу, что я не «открываю Америку» и аналог «строкового представления» для формул/программ/доказательств вместо нумерации Гёделя имеется и в книге «Вычислимость и логика» Дж. Булоса и Р. Джеффри. С момента написания той книги произошел огромный скачок в компьютерных технологиях, во многих языках программирования оперируют как текстами программ – генерируя их, так и логическими текстами – и вовсе не в формате «гёделевых номеров».
Тем не менее, в математической логике возник не просто застой, но существенный откат от достигнутого уровня развития – а в теории алгоритмов даже не сформировались полиномиальные – в смысле распознавания – стандарты в представлении логических формул и алгоритмов. У меня есть мнение, почему сложилась подобная ситуация, и я его выскажу (см. конец подраздела 8.3 «Рефлексия» раздела 8 «Приложения») когда доберёмся до тех важных аспектов реального мира, которые не были формализованы в математике.
2.2. И ещё одно существенное усложнение в разбираемых тут вопросах: мы различаем алгоритмы между собой по их внутреннему устройству (исключая незначимые символы в программном коде – пробелы, комментарии и т.п.). Даже если алгоритмы выдают одни и те же результаты за одинаковое время, но «программный код» у них разный – то это разные алгоритмы и разными будут соответствующие им задачи.
2.3. Машина Тьюринга – также не является адекватным отражением методов вычисления, производимых в реальном мире. Машина Тьюринга придумывалась для анализа логических проблем, а мы разбираем вопросы теории алгоритмов – где вопросы времени и размеров являются принципиальными – в отличие от логики.
В частности, аргументы в реальном мире часто передаются «по ссылке» - то есть не всё значение аргумента передаётся байт за байтом – передаётся только адрес, начиная с которого располагаются данные, соответствующие данному аргументу.
Это значит, что аргументы в оптимально построенном алгоритме расположены «на соседних лентах» рядом. И для доступа к одному аргументу нет нужды «проехать на тележке» всю длину другого аргумента. А другой аргумент может быть неполиномиально велик в сравнении с нужным нам аргументом. Например – слишком большое доказательство для малозначимой теоремы, которое должно быть отвергнуто в силу его размера (есть, например, менее громоздкие альтернативные решения). И это очень важный момент – возможность избегать перебора/передачи ненужных данных при доступе к нужным данным. И этой возможностью мы ещё воспользуемся, так как она имеется в реальном мире – пусть её и нет в модели «машина Тьюринга».
Это замечание делается к тому, что привязанность к созданным человеком формализмам может превращать мышление в бессмысленное занятие, когда эти формализмы перестают отвечать реальности. Какой смысл рассуждать о медленных алгоритмах, если они медленные только в неадекватном формализме? И если мы видим, как обстоят дела в реальном мире, то и формализм свой мы должны приводить в соответствие с ним. Назову условно этот довод - «довод божьего творения» или «довод реальности» - кому как нравится. Мы его часто используем – пусть и неявно. А пренебрежение им в итоге заводит в тупик бессмысленности.
