dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 2, п. 2. Программа Гильберта …

к Оглавлению

2.1. Говоря «число» мы обычно подразумеваем десятичную запись числа, а для компьютера –2^8-ричную или 2^{16}-ричную. И со всеми нашими правилами «сложения столбиком», «умножения столбиком» и т.п. все эти объекты полностью соответствуют аксиомам математики о числах. Назовём «обычную» модель интерпретации «интерпретация C» (компьютерная интерпретация), а стандартную модель интерпретации – «интерпретация S».

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

И представлять логические формулы и программные тексты для алгоритмов мы будем в рамках интерпретации C. То есть так, как это делают компьютеры – где для разных символов (цифр, букв, знаков препинания, математических символов и др.) есть свои числа, записанные либо байтом (кодировка ASCII) или парой байт (кодировка UTF-8) или аналогичным образом. А из этих символов составляются числа и тексты – путем записи символов в определенном порядке в последовательности «друг за другом».

Разумеется, все теоремы, доказанные в эпоху Гильберта, остаются в силе и для интерпретации C, потому что она полностью соответствует тем аксиомам Пеано (например), которые применялись для интерпретации S.

Вспоминается известная шутка математиков того времени, что в геометрии вместо понятия «прямые» можно использовать и пивные кружки. Главное – чтоб они соответствовали аксиомам геометрии.

Таким образом, можно считать, что как формулы и числа записаны в данной работе – так же они представлены и в нашей интерпретации – где каждый символ формулы/программы/доказательства представлен соответствующим кодом на соответствующем месте строки. И этими строками будут оперировать наши логические формулы и алгоритмы.

Замечу, что я не «открываю Америку» и аналог «строкового представления» для формул/программ/доказательств вместо нумерации Гёделя имеется и в книге «Вычислимость и логика» Дж. Булоса и Р. Джеффри. С момента написания той книги произошел огромный скачок в компьютерных технологиях, во многих языках программирования оперируют как текстами программ – генерируя их, так и логическими текстами – и вовсе не в формате «гёделевых номеров».

Тем не менее, в математической логике возник не просто застой, но существенный откат от достигнутого уровня развития – а в теории алгоритмов даже не сформировались полиномиальные – в смысле распознавания – стандарты в представлении логических формул и алгоритмов. У меня есть мнение, почему сложилась подобная ситуация, и я его выскажу (см. конец подраздела 8.3 «Рефлексия» раздела 8 «Приложения») когда доберёмся до тех важных аспектов реального мира, которые не были формализованы в математике.

2.2. И ещё одно существенное усложнение в разбираемых тут вопросах: мы различаем алгоритмы между собой по их внутреннему устройству (исключая незначимые символы в программном коде – пробелы, комментарии и т.п.). Даже если алгоритмы выдают одни и те же результаты за одинаковое время, но «программный код» у них разный – то это разные алгоритмы и разными будут соответствующие им задачи.

2.3. Машина Тьюринга – также не является адекватным отражением методов вычисления, производимых в реальном мире. Машина Тьюринга придумывалась для анализа логических проблем, а мы разбираем вопросы теории алгоритмов – где вопросы времени и размеров являются принципиальными – в отличие от логики.

В частности, аргументы в реальном мире часто передаются «по ссылке» - то есть не всё значение аргумента передаётся байт за байтом – передаётся только адрес, начиная с которого располагаются данные, соответствующие данному аргументу.

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

Это замечание делается к тому, что привязанность к созданным человеком формализмам может превращать мышление в бессмысленное занятие, когда эти формализмы перестают отвечать реальности. Какой смысл рассуждать о медленных алгоритмах, если они медленные только в неадекватном формализме? И если мы видим, как обстоят дела в реальном мире, то и формализм свой мы должны приводить в соответствие с ним. Назову условно этот довод - «довод божьего творения» или «довод реальности» - кому как нравится. Мы его часто используем – пусть и неявно. А пренебрежение им в итоге заводит в тупик бессмысленности.


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

Recent Posts from This Journal

  • Post a new comment

    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.
  • 0 comments