dmitgu

Category:

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

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

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

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

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

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

1111111111

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

10

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

Казалось бы, мы можем представить число как сумму степеней 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 

тогда будет выглядеть:

11*1111111111^11 + 111*1111111111^111 + 111111*1111111111^1 + 1111111*1111111111^1111 

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

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

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

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

Можно ли сопоставить элементы структуры позиционной записи чисел и вычисляемые (средствами теории Пеано) разряды числа? Да. Но это разные объекты. Они отличаются, как количество товара на складе от числа, записанного в инвентаризационной ведомости. Одно дело то, что основано на арифметических операциях (в основе которых 0 и увеличение на 1) и другое – то, что основано на операциях строковых. 

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

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

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

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

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

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

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

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

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.