dmitgu

Category:

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

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

Оглавление 

0. Введение

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

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

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

Текущая версия – 1.0

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

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

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

0. Введение 

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

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

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

По изложенным причинам реализация программы Гильберта тем более необходима в отношении теории алгоритмов.

Попытка наметить, и отчасти реализовать программу Гильберта (в том числе в части формализации) в отношении теории алгоритмов и предпринята в данной статье. Конкретно в данной статье будет построена на уровне аксиом теория первого порядка для слов (строк) и разобраны некоторые сопутствующие вопросы.

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.