Я понимаю, что полнота Тьюринга требует неограниченной памяти и неограниченного времени. Однако в этом сервисе существует ограниченное количество атомов, что ограничивает память. Например, даже если иррационально, нет способа сохранить более определенного числа цифр, даже если все атомы во...
Гиперкомпьютер относится к моделям вычислений, которые невозможно моделировать с использованием машин Тьюринга. (Гиперкомпьютеры не обязательно физически реализуемы!) Некоторые гиперкомпьютеры имеют доступ к ресурсу, который позволяет решить проблему остановки для стандартных машин Тьюринга....
Многие теоремы и «парадоксы» - диагонализация Кантора, неразрешимость хетлинга, неразрешимость колмогоровской сложности, неполнота Гёделя, неполнота Хаитина, парадокс Рассела и т. Д. - все имеют по существу одно и то же доказательство диагонализацией (обратите внимание, что это более конкретно, чем...
Фрактальный лабиринт - это лабиринт, который содержит копии самого себя. Например, следующий от Mark JP Wolf из этой статьи : Начните с МИНУС и пройдите в ПЛЮС. Когда вы вводите уменьшенную копию лабиринта, обязательно запишите название буквы этой копии, так как вам придется оставить эту копию на...
Я ищу наименьший возможный универсальный комбинатор , измеряемый количеством абстракций и приложений, необходимых для указания такого комбинатора в лямбда-исчислении . Примеры универсальных комбинаторов включают в себя: размер 23: λf.f (fS (KKKI)) K размер 18: λf.f (fS (KK)) K размер 14: λf.fKSK...
Допустим, вы создаете компьютер, который будет вычислять состояние всех атомов во Вселенной в определенный момент времени в будущем. Поскольку Вселенная по определению является всем, что существует (и всем, что взаимодействует с остальными), она также включает в себя компьютер, который вы создаете....
( UPDATE : лучше формируются вопрос ставятся здесь в качестве комментариев к общепринятом ответу ниже , показывает , что этот вопрос не является четко определенным) Классическое доказательство невозможности проблемы остановки зависит от демонстрации противоречия при попытке применить алгоритм...
Существует ли общая теорема, которая при надлежащей дезинфекции утверждает, что наиболее известные результаты, касающиеся использования действительных чисел, могут фактически использоваться при рассмотрении только вычислимых вещественных чисел? Или существует правильная характеристика результатов,...
Я жду определенного ответа на заглавный вопрос. Существует ли набор правил, который переводит любую программу в конфигурацию конечных фигур на бесконечной доске, например, если черно-белые играют только легальные ходы, игра заканчивается за конечное время, если программа останавливается? Правила те...
Любой язык, не являющийся полным по Тьюрингу, не может написать для себя интерпретатор. Я понятия не имею, где я это прочитал, но я видел, что это использовалось несколько раз. Кажется, что это порождает своего рода «окончательный» нетуринговский законченный язык; те, которые могут...
Одна из удивительных вещей в компьютерной науке заключается в том, что физическая реализация в некотором смысле «неактуальна». Люди успешно создали компьютеры из нескольких различных подложек - реле, вакуумных трубок, дискретных транзисторов и т. Д. Вскоре люди могут преуспеть в создании...
Учитывая язык L, определенный машиной Тьюринга, который его решает, возможно ли алгоритмически определить, лежит ли L в
Этот вопрос также был размещен на Math.SE, /math/1002540/fixed-points-in-computability-nd-logic Я надеюсь, что это также хорошо, чтобы опубликовать это здесь. Если нет, или если это слишком просто для CS.SE, пожалуйста, сообщите мне, и я удалю его. Я хотел бы лучше понять связь между теоремами о...
Не могли бы вы указать, как построить функцию Аккермана (на самом деле меня интересует версия, предложенная Роузой Петером и Рафаэлем Робинсоном) с помощью стандартных мюрекурсивных операторов? Я пробовал оригинальные статьи Петера и Робинсона, но в работе Петера используется язык, отличный от...
Мы говорим, что машина Тьюринга смертна, если M останавливается для каждой начальной конфигурации (в частности, содержимое ленты и начальное состояние могут быть произвольными). Каждый рекурсивный язык распознается смертной машиной Тьюринга? (т. е. если есть ТМ, принимающий L , существует также...
Давно известно, что при любой степени восстановления существует конечно представленная группа, проблема слова в которой есть в этой степени. У меня вопрос: верно ли то же самое для произвольных полиномиальных степеней Тьюринга? В частности, существует ли разрешимое множество , существует ли конечно...
Грег Иган в своей художественной литературе «Темные целые» (рассказ о двух вселенных, в которых две разные математики общаются посредством доказательства теорем о непоследовательности в арифметике) утверждает, что можно построить компьютер общего назначения исключительно на существующих...
Две статьи, которые я бы включил: Д. Козен, "Индексация субрекурсивных классов" , STOC, 1978. Р. Лэднер, "О структуре полиномиальной временной сводимости" , JACM, 1975....
Меня интересует «ближайшая» (и «самая сложная») проблема к гипотезе Коллатца , которая была успешно решена (на что Эрдос сказал, что «математика еще не созрела для таких задач»). Было доказано, что класс "коллатцовых" проблем неразрешим. Тем не менее, проблемы, которые в некоторой степени похожи,...
Теорема Райса утверждает, что каждое нетривиальное свойство множества, распознаваемое некоторой машиной Тьюринга, неразрешимо. Я ищу теорему о сложности теории Райса, которая говорит нам, какие нетривиальные свойства NP-множеств...