03.08.2022
№222.018.40c4
Результат интеллектуальной деятельности: Вычислимость по Тьюрингу превосходит в принципиальном отношении вычислимость рекурсивных функций
Вид РИД
Произведениe науки
Описание произведения:
В данной работе продемонстрировано, что вычислимость по Тьюрингу превосходит вычислимость рекурсивных функций, вопреки принятому сейчас и «доказанному» мнению об их одинаковой вычислимости. Так же, намечен путь построения теории строк.
Ключевые слова:
Вычислительные системы, Вычислимость, Машина Тьюринга
Основные результаты научного произведения:
На примере вычисления размера записи числа на ленте Машины Тьюринга доказано, что рекурсивные функции не имеют аналогичных возможностей для вычисления, хотя одинаковая вычислимость по Тьюрингу и рекурсивных функций (натуральных чисел) «доказана» и является одной из принципиальных теорем теории вычислимости. Таким образом, в теории вычислимости была допущена грубая принципиальная ошибка и она нуждается в пересмотре. Намечен путь построения соответствующей теории – с использованием типов строк и соответствующих им чисел-строк.
Перспективные направления применения для дальнейших исследований и разработок:
Важная для теоретических и практических вопросов тема о зависимости эффективности вычислений от алгоритмов и размеров данных могут быть исследованы теперь при помощи найденных теоретических методов, без тех принципиальных ошибок, которые имелись в прежних подходах, которые не позволяли даже отличить натуральное число от его компьютерного представления.
Приоритетные направления развития науки, технологий и техники в РФ:
Информационно-телекоммуникационные системы
В данной работе продемонстрировано, что вычислимость по Тьюрингу превосходит вычислимость рекурсивных функций, вопреки принятому сейчас и «доказанному» мнению об их одинаковой вычислимости. Так же, намечен путь построения теории строк..
Важная для теоретических и практических вопросов тема о зависимости эффективности вычислений от алгоритмов и размеров данных могут быть исследованы теперь при помощи найденных теоретических методов, без тех принципиальных ошибок, которые имелись в прежних подходах, которые не позволяли даже отличить натуральное число от его компьютерного представления.
Хеш-код депонирования:
94fd2cca6a266b1d20b0f03a7157f7ce657e60661c781c8adf069d7842c6c965
Источник поступления информации:
Портал edrid.ru
Showing 1-5 of 5 items.
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 науки
25.04.2020
№220.018.19db
Теория строк (слов). недостаточная выразительность рекурсивных функций и арифметики для теории алгоритмов
Построение теории первого порядка - теории строк (слов) Доказательство недостаточной выразительности рекурсивных функций и арифметики для теории алгоритмов.
Тип: Произведениe науки
16.03.2021
№221.018.3f2d
Машина исполнения компьютерных алгоритмов - архитектура математической модели с центральным процессором и неограниченными лучами данных
Построена математическая модель вычислительной системы вместо машины Тьюринга. Архитектура построенной модели аналогична архитектуре современных компьютеров с центральным процессором и оперативной памятью. Удалось преодолеть ограничение на размер доступной оперативной памяти из-за разрядности...
Тип: Произведениe науки
30.01.2023
№223.018.4167
Числа арифметики пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики пеано не создаёт им эти свойства
Числа арифметики Пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики Пеано не создаёт им эти свойства. То есть, с точки зрения возможности применять числа арифметики Пеано в качестве вычислимых объектов внутри какой-либо теории они не были...
Тип: Произведениe науки
Showing 1-5 of 5 items.
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 науки
25.04.2020
№220.018.19db
Теория строк (слов). недостаточная выразительность рекурсивных функций и арифметики для теории алгоритмов
Построение теории первого порядка - теории строк (слов) Доказательство недостаточной выразительности рекурсивных функций и арифметики для теории алгоритмов.
Тип: Произведениe науки
16.03.2021
№221.018.3f2d
Машина исполнения компьютерных алгоритмов - архитектура математической модели с центральным процессором и неограниченными лучами данных
Построена математическая модель вычислительной системы вместо машины Тьюринга. Архитектура построенной модели аналогична архитектуре современных компьютеров с центральным процессором и оперативной памятью. Удалось преодолеть ограничение на размер доступной оперативной памяти из-за разрядности...
Тип: Произведениe науки
30.01.2023
№223.018.4167
Числа арифметики пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики пеано не создаёт им эти свойства
Числа арифметики Пеано не обладают необходимыми для вычислимости свойствами и никакое логическое расширение арифметики Пеано не создаёт им эти свойства. То есть, с точки зрения возможности применять числа арифметики Пеано в качестве вычислимых объектов внутри какой-либо теории они не были...
Тип: Произведениe науки
