Дмитрий Леонидович Гуринович
Научный руководитель Института фундаментальной математики
5 Вычислимость по Тьюрингу превосходит в принципиальном отношении вычислимость рекурсивных функций
В данной работе продемонстрировано, что вычислимость по Тьюрингу превосходит вычислимость рекурсивных функций, вопреки принятому сейчас и «доказанному» мнению об их одинаковой вычислимости. Так же, намечен путь построения теории строк.
Основные результаты научного произведения:
На примере вычисления размера записи числа на ленте Машины Тьюринга доказано, что рекурсивные функции не имеют аналогичных возможностей для вычисления, хотя одинаковая вычислимость по Тьюрингу и рекурсивных функций (натуральных чисел) «доказана» и является одной из принципиальных теорем теории вычислимости. Таким образом, в теории вычислимости была допущена грубая принципиальная ошибка и она нуждается в пересмотре. Намечен путь построения соответствующей теории – с использованием типов строк и соответствующих им чисел-строк.
Перспективные направления применения для дальнейших исследований и разработок: Важная для теоретических и практических вопросов тема о зависимости эффективности вычислений от алгоритмов и размеров данных могут быть исследованы теперь при помощи найденных теоретических методов, без тех принципиальных ошибок, которые имелись в прежних подходах, которые не позволяли даже отличить натуральное число от его компьютерного представления.
Приоритетные направления развития науки, технологий и техники в РФ: Информационно-телекоммуникационные системы.
В данной работе продемонстрировано, что вычислимость по Тьюрингу превосходит вычислимость рекурсивных функций, вопреки принятому сейчас и «доказанному» мнению об их одинаковой вычислимости. Так же, намечен путь построения теории строк.. Важная для теоретических и практических вопросов тема о зависимости эффективности вычислений от алгоритмов и размеров данных могут быть исследованы теперь при помощи найденных теоретических методов, без тех принципиальных ошибок, которые имелись в прежних подходах, которые не позволяли даже отличить натуральное число от его компьютерного представления.
Впервые опубликовано 03.08.2022.