Я пытался выяснить, разрешима ли проблема остановки для трехмерных одномерных клеточных автоматов. Определение Пусть обозначает конфигурацию системы на временном шаге i . Более формально f : A ∗ × N → A ∗ , где A - алфавит.е( ш , я )f(w,i)f(w,i)яiif:A∗×N→A∗f:A∗×N→A∗f:A^*\times \mathbb{N} \to A^*AAA...
Сегодня я узнал, что алгоритм анализа отличается в зависимости от вычислительной модели. Это то, о чем я никогда не думал и не слышал. Пример, данный мне, который проиллюстрировал это далее, пользователем @chi был: Например, рассмотрим задачу: дано вернуть . В оперативной памяти это может быть...
Является ли «теорема Райса для вычислимых вещественных чисел», то есть нет нетривиального нетривиального свойства числа, представленного данным вычислимым вещественным веществом, истинной? Соответствует ли это каким-то прямым образом связности...
Можно показать, что две вычислительные модели являются полными, если каждая из них может кодировать универсальный симулятор для другой. Можно показать, что две логики будут полными, если будет показано, что кодирование правил логических выводов (и, возможно, аксиом, если они присутствуют) каждого...
В середине срока был вариант следующего вопроса: Для разрешимого определить Показать, что не обязательно разрешимый.прив ( L ) = { х | ∃ у й рентгеновские у ∈ LLLLPref ( L )Pref ( L ) = { x ∣ ∃ y St X Y∈ L }Pref(L)={x∣∃y s.t. xy∈L}\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}Pref...
Является ли машина Тьюринга, которому разрешено чтение и запись символов из бесконечного алфавита, более мощной, чем обычная ТМ (единственное отличие, у машины все еще есть конечное число состояний)? Интуиция говорит мне, что нет, так как вам нужно бесконечное количество состояний, чтобы...
Почему вычислимые числа (в смысле Тьюринга) перечислимы? Это должно быть очень очевидно, но я сейчас просто не вижу
Мы хотим выложить квадрат m×mm×mm\times m используя два типа плиток: квадрат 1×11×11 \times 1 квадрат 2×22×22 \times 2 , чтобы каждый нижележащий квадрат был покрыт без перекрытия. Определим функцию f(n)f(n)f(n) которая задает размер наибольшего однозначно обрабатываемого квадрата, используя nnn...
Читая этот вопрос « Естественные неразрешимые проблемы RE, но не полные по Тьюрингу », мне пришло в голову следующее: Если - это функция занятого бобра (максимально достижимая оценка среди всех останавливающих 2-символьных машин Тьюринга с n-состояниями описанного выше типа при запуске на чистой...
Я студент, только начинающий читать о обратимых вычислениях. Я знаю, что по принципу Ландауэра необратимые вычисления рассеивают тепло (а обратимые - нет). Я рассказал об этом своему профессору, который никогда раньше не слышал об обратимых вычислениях, и ему было трудно понять, почему теория...
Это продолжение другого вопроса здесь , и я надеюсь, что он не слишком философский. Как отметил Рафаэль в комментарии к моему предыдущему вопросу, на самом деле я не получил определения «вычислимый», но согласно некоторым прочитанным мною работам определение также не совсем понятно, когда речь идет...
Предположим, у меня есть две функции FFF и GGG и я заинтересован в определении F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Предположим, что мои функции состоят из элементарных функций (полиномов, экспонент, логарифмов и тригонометрических функций), но не, скажем, из ряда Тейлора. Эта проблема...
Чтобы доказать, что 3-раскраска разрешима, достаточно сказать: Каждый узел на графике имеет 3 возможных цвета Поэтому мы можем перечислить все возможностей и затем проверить, что никакие два ребра не соединяют узлы одного цвета3N3N3^n Означает ли это, что 3-раскраска разрешима? Или мне нужно...
Сегодня за ланчем я поднял эту проблему со своими коллегами, и, к моему удивлению, аргумент Джеффа Э., что проблема разрешима, не убедил их ( вот тесно связанный пост о mathoverflow). Постановка проблемы, которую легче объяснить («это P = NP?»), Также разрешима: да или нет, и поэтому один из двух...
Мне пришло в голову этот вопрос о проблеме остановки, и я не смог найти хорошего ответа в Интернете, задаваясь вопросом, может ли кто-нибудь помочь. Возможно ли, что проблема остановки разрешима для любого ТМ на любом входе, если он не сам ТМ? В принципе: Halts(TM, I) IF TM == I: Undecidable,...
На этом сайте есть много вариантов вопроса о том, могут ли ТМ решить проблему остановки, будь то для всех других ТМ или определенных подмножеств. Этот вопрос несколько другой. Он спрашивает, может ли тот факт, что проблема остановки относится ко всем ТМ, может быть решен ТМ. Я верю, что ответ...
Я пытаюсь придумать доказательство для следующего: Для любого языка AAA , существует язык BBB такие , что A≤TBA≤TBA \le_{\mathrm{T}} B , но B ≰TA≰TA\nleq_{\mathrm{T}} A . Я думал о том, чтобы позволить BBB быть ATMATMA_{\mathrm{TM}} , но я понимаю, что не все языки Тьюринга сводимы к...
Одно из утверждений о теореме Райса приведено на странице 35 «Вычислительная сложность: современный подход» (Арора-Барак): Частичная функция от до - это функция, которая не обязательно определяется на всех ее входах. Мы говорим, что TM вычисляет частичную функцию если для каждого для которого...