1. Эвристические соображения о недостаточности арифметики для целей теории алгоритмов

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

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

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

Теперь немного разъясню сказанное в 2х предыдущих абзацах.

Стандартная интерпретация – это представление чисел в виде «счётных палочек», где число 10 выглядит примерно так:

11111111111

Записано, кстати, при помощи 11 (Одиннадцати) единиц, потому что для нуля тоже необходимо какое-то видимое изображение.

В основе всех чисел лежит именно стандартная интерпретация. Арифметика является теорией для чисел в любых формах – в том числе и в стандартной интерпретации. И арифметика описывает те свойства чисел, которые общие для всех их представлений. Ничего от специфического представления (от позиционного представления, например) в арифметике – нет. Иначе она не годилась бы для стандартной интерпретации. Мы – можем записать в позиционном десятичном представлении число 10 таким образом:

10

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

Казалось бы, мы можем представить число как сумму степеней 10. Например, число 2361 можно записано так:

2 × 10^3 + 6 × 10^1 + 1 + 3 × 10^2

Но и это тоже аналог записи позиционным образом. Потому что в стандартной интерпретации мы имеем дело с «кучками счётных палочек». 

Да, мы можем записывать числа в виде 2 × 10^2 + 3 × 10^3 + 6 × 10^1 + 7 × 10^4 даже при помощи определяемых внутри теории Пеано функций – есть там (можно определить) и функция возведения в степень, а как записано 10 в таком случае – пусть в виде счётных палочек – это не меняет в принципе степень сжатости данного представления. Вот как число 

2 × 10^2 + 3 × 10^3 + 6 × 10^1 + 7 × 10^4 

тогда будет выглядеть (цифра n обозначена строкой из n+1 символов «1»):

111 × 11111111111^{111} + 1111 × 11111111111^{1111} + 1111111 × 11111111111^{11} + 11111111 × 11111111111^{11111} 

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

Если у нас определена в арифметике функция f(i), то значение переменной i не может передаваться в виде представления через сумму степеней 10 с коэффициентами. У нас нет на уровне объекта (числа) внутри арифметики способа его передачи в готовом «сжатом» виде.

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

А если мы запишем десятичное представление числа i в виде другого числа j, которое является гёделевым номером десятичного представления, но записано тоже «кучей счётных палочек», то это число j не будет, в общем случае, меньше числа i и ничего не «сожмёт», вообще говоря.

Сказанное выше создаёт впечатление (правильное, как мы убедимся в этой статье), что гёделевы номера не годятся в качестве «слов» для теории алгоритмов. Гёделевы номера имеют свойства «куч счётных палочек» и не более, потому что формализованы в рамках арифметики. 

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

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

Поэтому теория строк нам необходима уже по той причине, что иначе нет инструмента для формализации понятия «слово» и свойств этих «слов», делающих возможными обычные операции с этими объектами.

Поэтому приступим к построению теории строк (слов), а уже на базе построенной теории строк будет доказана (вместо приведённых сейчас эвристических соображений) недостаточная выразительность арифметики (и гёделевых номеров) для решения задач теории алгоритмов.