dmitgu

Category:

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 и ничего не «сожмёт», вообще говоря.

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

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

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

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

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

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.