dmitgu

Category:

Теория строк (слов). Недостаточная выразительность арифметики для теории алгоритмов.

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

Оглавление 

0. Оглавление, введение и предисловие

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

2. Теория строк

0. Общая информация и свод результатов

I. Разбиение строк

II. Алфавит строк

III. Концы строк, соединение строк, равенство строк

IV. Равенство строк

V. Сравнение, поиск, вставка

VI. Алгоритмы, не сводимые к рекурсивным функциям и арифметике

VII. Критерий локального изменения данных

VIII. Критерий локального извлечении данных

3. Числа в теории строк

4. Приложение. Логика теорий первого порядка с равенством

Предыдущая версия 1.0 – Программа Гильберта-1 для теории алгоритмов: теория слов (строк)

Текущая версия – 2.0. Копия на ЕДРИДе

Следующая статья: 

Программа Гильберта-2 для теории алгоритмов: модель работы алгоритмов

Введение

С момента формулировки гипотезы NP ≠ P (1971 г.) прошло без малого полвека, со времени создания первой ЭВМ (1941 г) – почти 80 лет. Но математической теории (первого порядка) в том смысле, как понимал это Гильберт и другие логики первой половины 20 века – такой теории для изучения алгоритмов не было создано до сих пор. Понять, что нужной теории нет – было очень неожиданным открытием для меня. 

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

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

Это и многое другое выяснилось, когда я разбирался с вопросом о NP ≠ P и отвечал в дискуссиях на вопросы о времени работы алгоритма, о работе алгоритма с частью входных данных, о слишком длинных сертификатах в проверках принадлежности слов языкам класса NP и т.д. Был и вопрос, например, «почему вы не используете Гёделевы номера?». 

Стала понятна первоочередная необходимость глубокой подготовки фундамента для теории алгоритмов, а не попытка построение доказательства для NP ≠ P без теоретического фундамента.  Последней каплей стали слова оппонента, называвшего себя «профессиональным математиком», что я «толку воду в ступе» и что я «лгу или ошибаюсь» именно о том, чем я его убеждал, и с чем он вынужден был соглашаться, когда я преодолевал его возражения в ходе моего построения доказательства для NP ≠ P.

Поэтому я отложил вопрос о доказательстве NP ≠ P как менее приоритетный с точки зрения математики (он приоритетен только если смотреть с чуждой для математики коммерческой стороны – объявленной премии института Клейна) и занялся один построением теории строк (слов) - когда у меня выпадала такая возможность. А это такая теории первого порядка, которая необходима для решения вопросов теории алгоритмов. 

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

После 15 июля 2018 г. (когда я прекратил дискуссию из-за очередного грубого нарушения этики оппонентом https://dxdy.ru/post1326877.html#p1326877 ) удалось сформулировать основы теории строк, в достаточной степени, чтобы можно было «представлять» алгоритмы без потери в «представлении» важных для теории алгоритмов свойств алгоритмов. А сейчас, в период карантинных мероприятий – подготовил теорию для публикации и предлагаю её к рассмотрению.  

Доказательство недостаточной выразительности арифметики для решения вопросов теории алгоритмов дано в данной статье в разделе 2. «Теория строк», подразделе VI. «Алгоритмы, не сводимые к (частично) рекурсивным функциям и арифметике». Там нет ничего особенно сложного. Хотя, «нет ничего сложного» – это только после того, как изложенное там было найдено, конечно. 

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

А помимо этого, для решения задач уровня NP ≠ P необходимо формализовать, что такое «сложность вычислений». Для кого/чего имеет место быть эта сложность. И, почему этому кому-то/чему-то «сложно» решать некоторые задачи. По сути – это тоже вопрос об алгоритмах, решающих вопросы теории алгоритмов. Но этот вопрос будет отложен до статьи 5 или дальше – если считать эту статью первой.

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

Данная статья является самой объёмной и принципиальной среди всех статей (остальные в черновиках пока) цикла. Остальные статьи (кроме второй) в основном получают свои результаты как логические выводы на базе данной статьи и их размер значительно меньше размера данной статьи. Впрочем, в процессе их подготовки к публикации что-то, может быть, и изменится.

Предисловие к версии 2.

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

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

Поэтому 2-я версия первой статьи получилась значительно больше 1-й версии, вопреки первоначальному желанию сократить и упростить изложение. Но увеличение объема произошло за счёт добавления принципиальных для теории алгоритмов сведений и доказательств. Аксиоматизация по сравнению с первой версией стала более понятной и удобной для применения, на мой взгляд.

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

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.