?

Log in

No account? Create an account

October 13th, 2019

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

Оглавление 

0. Введение

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

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

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

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

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

0. Введение 

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

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

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

Read more...Collapse )

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

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

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

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

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

1111111111

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

10

Read more...Collapse )

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

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

Математики называют объекты теории алгоритмов термином «слово», программисты используют для того же термин «строка». Далее буду использовать термин программистов, потому что аксиомы построены именно в соответствии с общеизвестной практикой программирования.

Для предметных переменных типа строка буду использовать все переменные, кроме i, j, k, l, m, n – которые оставлю для натуральных чисел. Увеличение числа i на 1 буду обозначать так:

i’ – такое обозначение увеличения числа на 1 является аксиоматизируемой операцией в арифметике (и её кратким вариантов в виде теории Пеано), поэтому сохраним тут это стандартное обозначение.

Теперь запишем аксиомы теории строк.

Аксиома о равенстве строк:

a = b ⇔ ∀ i str(a, i, 1) = str(b, i, 1) 

Пояснение: строки одинаковы, если на всех одинаковых местах в строках стоят одинаковые символы.

Аксиома о границе слова, если она есть:

str(a, i, 1) = ⊖ ⇒ str(a, i + 1, 1) = ⊖ 

Пояснение: попытка извлечь из строки очередной символ после того, как не удалось извлечь символ с предыдущего места – тоже ничего не даёт. Точнее – даёт пустую строку ⊖.

Аксиома об отсутствии символов нулевой длины:

str(a, i, 0) = ⊖ 

Пояснение: попытка извлечь из строки с произвольного её места подстроку нулевой длины даёт только пустую строку ⊖.

Read more...Collapse )

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

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

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

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

Вот нужные для «превращения» некоторых строк ещё и в числа аксиомы:

∃ l_NumBeg ∃ l_NumLim: 

( 0 ≤ l_NumBeg < l_NumLim ≤ I_ChrLim )

∧  0 = Chr(l_NumBeg) 

∧ ( l_NumBeg ≤ j < l_NumLim ⇒ (Chr(j)) ’ = Chr(j ’ ) )

∧ Chr(l_NumLim) ’ = (Chr(l_NumBeg) ’ ) ⋅ Chr(l_NumBeg)

∧ ( (k ≠ 0 ∧ l_NumBeg ≤ j < l_NumLim) ⇒ (k ⋅ Chr(j)) ’ = k ⋅ Chr(j ’ ) )

∧ ( k ≠ 0 ⇒ (k ⋅ Chr(l_NumLim)) ’ = (k ' ) ⋅ Chr(l_NumBeg) ) 

Пояснения: 

1. Мы задаём «алфавит в алфавите» - для цифр. 

Read more...Collapse )

Latest Month

November 2019
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Tags

Powered by LiveJournal.com
Designed by yoksel