Программа Гильберта-1 для теории алгоритмов: теория слов (строк)
. К оглавлению . Показать весь текст .
Оглавление
0. Введение
1. Недостаточность арифметики для целей теории алгоритмов
2. Теория строк
Текущая версия – 1.0
Следующая версия 2.0 — Теория строк (слов). Недостаточная выразительность арифметики для теории алгоритмов.
Следующая статья:
Программа Гильберта-2 для теории алгоритмов: модель работы алгоритмов
0. Введение
С момента формулировки гипотезы NP ≠ P (1971 г.) прошло без малого полвека, со времени создания первой ЭВМ (1941 г) – почти 80 лет. Но математической теории (первого порядка) в том смысле, как понимал это Гильберт и другие логики первой половины 20 века – такой теории для изучения алгоритмов не создано до сих пор. Это странное, на первый взгляд, заявление будет обосновано далее.
В частности, арифметика недостаточно выразительно для формализации понятия слова – так как числа могут пониматься в «стандартной интерпретации» (не в «позиционной записи», а как «счётные палочки»). Поэтому «Гёделевы номера», «алгоритмы» в арифметике и т.п. аппарат оказывается непригодными для изучения вопросов теории алгоритмов.
А помимо этого, для решения задач уровня NP ≠ P необходимо формализовать, что такое «сложность вычислений». Для кого/чего имеет место быть эта сложность. И, почему этому кому-то/чему-то «сложно» решать некоторые задачи. По сути – это тоже вопрос об алгоритмах, решающих вопросы теории алгоритмов. Это характерный пример изучения теории средствами самой теории – именно то, что было сделано в первой половине 20 века логиками при реализации программы Гильберта. А программа Гильберта требовала тщательной формализации теории для того, чтобы применить методы теории (арифметики и логики в том случае) к ней самой.
По изложенным причинам реализация программы Гильберта тем более необходима в отношении теории алгоритмов.
Попытка наметить, и отчасти реализовать программу Гильберта (в том числе в части формализации) в отношении теории алгоритмов и предпринята в данной статье. Конкретно в данной статье будет построена на уровне аксиом теория первого порядка для слов (строк) и разобраны некоторые сопутствующие вопросы.
