Автор РИД: Гуринович Дмитрий Леонидович

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

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

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

Построение теории первого порядка - теории строк (слов) Доказательство недостаточной выразительности рекурсивных функций и арифметики для теории алгоритмов.

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

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