×
25.04.2020
220.018.19db

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

Вид РИД

Произведениe науки

Код транзакции депонирования в блокчейн Ethereum: 0xcf34f2dfb263ca7e180031dcd2e602f6c8636fa638e0851892254ddcf2c12157
Наименование РИД на английском: Theory of strings (words). The lack of expressiveness of recursive functions and arithmetic to the theory of algorithms
Описание произведения: Построение теории первого порядка - теории строк (слов) Доказательство недостаточной выразительности рекурсивных функций и арифметики для теории алгоритмов.
Ключевые слова: Метаматематика для теории алгоритмов, скорость вычислений, вычислимость, неполнота
Основные результаты научного произведения:
С момента формулировки гипотезы NP ≠ P (1971 г.) прошло без малого полвека, со времени создания первой ЭВМ (1941 г) – почти 80 лет. Но математической теории (первого порядка) в том смысле, как понимал это Гильберт и другие логики первой половины 20 века – такой теории для изучения алгоритмов не было создано до сих пор. Понять, что нужной теории нет – было очень неожиданным открытием для меня. 
В частности, (частично) рекурсивные функции, на которых строится представимость алгоритмов в арифметике, не могут работать с входными данными частично – а легко построить алгоритм, который завершает свою работу, прочитав первый символ во входных данных, переданных ему для работы. А частично рекурсивная функция читает входные данные до конца. С арифметикой та же проблема. 
Поэтому я отложил вопрос о доказательстве NP ≠ P как менее приоритетный с точки зрения математики и занялся построением теории строк (слов). А это такая теории первого порядка, которая необходима для решения вопросов теории алгоритмов. 
В процессе построения теории строк выяснились некоторые интересные парадоксы и появилась возможность доказать, в частности, недостаточную выразительность арифметики для решения вопросов теории алгоритмов. И удалось это сделать как раз на базе построенной теории строк.
Перспективные направления применения для дальнейших исследований и разработок: Для решения задач уровня NP ≠ P необходимо формализовать, что такое «сложность вычислений». Для кого/чего имеет место быть эта сложность. И, почему этому кому-то/чему-то «сложно» решать некоторые задачи. По сути – это тоже вопрос об алгоритмах, решающих вопросы теории алгоритмов. Но этот вопрос будет отложен до статьи 5 или дальше – если считать эту статью первой. Вопрос изучения теории средствами самой теории – именно то, что было сделано в первой половине 20 века логиками при реализации программы Гильберта. А программа Гильберта требовала тщательной формализации теории для того, чтобы применить методы теории (арифметики и логики в том случае) к ней самой. Вот для логической формализации теории алгоритмов и написана эта статья. Данная статья является самой объёмной и содержательной в теоретическом отношении среди всех статей (остальные в черновиках пока) цикла. Остальные статьи (кроме второй) в основном получают свои результаты как логические выводы на базе данной статьи и их размер значительно меньше размера данной статьи. Впрочем, в процессе их подготовки к публикации что-то, может быть, и изменится.
Приоритетные направления развития науки, технологий и техники в РФ: Информационно-телекоммуникационные системы
Содержательная часть РИД:
Хеш-код депонирования: 20ba2b335387bd72122b8563616706436a2da291b92c94d22f64b3dfff8aecf0
Источник поступления информации: Портал edrid.ru

Показаны записи 1-6 из 6.
12.03.2017
№217.015.93d1

Программа гильберта, np ≠ p, рефлексия

Была использована методика Гёделя по построению такого рода тестовой задачи из класса NP, которая оказывается заведомо неразрешимой для заданного (произвольного) алгоритма-решения. При этом данная тестовая задача принадлежит классу NP, а искомый алгоритм-решение представляет из себя метод свести...
Тип: Произведениe науки
28.09.2017
№217.015.eeea

Языки логики и классы сложности. рефлексия. np ≠ p

Переработка предыдущей заметки на эту тему – «Программа Гильберта, NP ≠ P, Рефлексия» ( https://edrid.ru/rid/217.015.93d1.html ) на базе формализма языков и классов их сложности из теории алгоритмов. В том числе были «переведены» кое-какие сведения из формальной логики в термины «языков» и...
Тип: Произведениe науки
16.03.2021
№221.018.3f2d

Машина исполнения компьютерных алгоритмов - архитектура математической модели с центральным процессором и неограниченными лучами данных

Построена математическая модель вычислительной системы вместо машины Тьюринга. Архитектура построенной модели аналогична архитектуре современных компьютеров с центральным процессором и оперативной памятью. Удалось преодолеть ограничение на размер доступной оперативной памяти из-за разрядности...
Тип: Произведениe науки
03.08.2022
№222.018.40c4

Вычислимость по тьюрингу превосходит в принципиальном отношении вычислимость рекурсивных функций

В данной работе продемонстрировано, что вычислимость по Тьюрингу превосходит вычислимость рекурсивных функций, вопреки принятому сейчас и «доказанному» мнению об их одинаковой вычислимости. Так же, намечен путь построения теории строк.
Тип: Произведениe науки
30.01.2023
№223.018.4167

Числа арифметики пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики пеано не создаёт им эти свойства

Числа арифметики Пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики Пеано не создаёт им эти свойства. То есть, с точки зрения возможности применять числа арифметики Пеано в качестве вычислимых объектов внутри какой-либо теории они не были...
Тип: Произведениe науки
22.06.2025
№225.018.873b

Расширение математической логики средствами ооп для достижения необходимой выразительности при разборе вопросов вычислений и вычислимости

Обнаружен неизвестный ранее в математике этап применения математических теорий и методов, без которого невозможно проводить вычисления и в значительной степени невозможно пользоваться математическими теориями на практике. Этот этап применения математических теорий оставался в ведении практиков...
Тип: Произведениe науки
Показаны записи 1-6 из 6.
12.03.2017
№217.015.93d1

Программа гильберта, np ≠ p, рефлексия

Была использована методика Гёделя по построению такого рода тестовой задачи из класса NP, которая оказывается заведомо неразрешимой для заданного (произвольного) алгоритма-решения. При этом данная тестовая задача принадлежит классу NP, а искомый алгоритм-решение представляет из себя метод свести...
Тип: Произведениe науки
28.09.2017
№217.015.eeea

Языки логики и классы сложности. рефлексия. np ≠ p

Переработка предыдущей заметки на эту тему – «Программа Гильберта, NP ≠ P, Рефлексия» ( https://edrid.ru/rid/217.015.93d1.html ) на базе формализма языков и классов их сложности из теории алгоритмов. В том числе были «переведены» кое-какие сведения из формальной логики в термины «языков» и...
Тип: Произведениe науки
16.03.2021
№221.018.3f2d

Машина исполнения компьютерных алгоритмов - архитектура математической модели с центральным процессором и неограниченными лучами данных

Построена математическая модель вычислительной системы вместо машины Тьюринга. Архитектура построенной модели аналогична архитектуре современных компьютеров с центральным процессором и оперативной памятью. Удалось преодолеть ограничение на размер доступной оперативной памяти из-за разрядности...
Тип: Произведениe науки
03.08.2022
№222.018.40c4

Вычислимость по тьюрингу превосходит в принципиальном отношении вычислимость рекурсивных функций

В данной работе продемонстрировано, что вычислимость по Тьюрингу превосходит вычислимость рекурсивных функций, вопреки принятому сейчас и «доказанному» мнению об их одинаковой вычислимости. Так же, намечен путь построения теории строк.
Тип: Произведениe науки
30.01.2023
№223.018.4167

Числа арифметики пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики пеано не создаёт им эти свойства

Числа арифметики Пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики Пеано не создаёт им эти свойства. То есть, с точки зрения возможности применять числа арифметики Пеано в качестве вычислимых объектов внутри какой-либо теории они не были...
Тип: Произведениe науки
22.06.2025
№225.018.873b

Расширение математической логики средствами ооп для достижения необходимой выразительности при разборе вопросов вычислений и вычислимости

Обнаружен неизвестный ранее в математике этап применения математических теорий и методов, без которого невозможно проводить вычисления и в значительной степени невозможно пользоваться математическими теориями на практике. Этот этап применения математических теорий оставался в ведении практиков...
Тип: Произведениe науки
+ добавить свой РИД