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