Проблема почтовой корреспонденции (PCP) неразрешима. Ограниченная версия PCP является -полной и отмеченная версией PCP (слова одного из двух списков, должны отличаться по первой букве) в P S P A C E [1].Н ПNп\mathrm{NP}P S P A C EпSпAСЕ\mathrm{PSPACE} Используются ли эти ограниченные версии, чтобы...
Я читал о числах занятых бобров и о том, как они асимптотически растут больше, чем любая вычислимая функция. Почему это так? Это из-за невычислимости функции занятого бобра? Если так, то все ли невычислимые функции растут асимптотически больше, чем вычислимые? Редактировать: Хорошие ответы ниже, но...
Я в некотором роде новичок, но очень интересуюсь областью вычислений и теории сложности, и я хочу разъяснить свое понимание того, как классифицировать проблемы и насколько сильно проблемы связаны с машиной, используемой для их решения. Мое понимание Стандартная машина Тьюринга - машина Тьюринга,...
Функция максимального сдвига занятого бобра имеет известные значения для n ≤ 4 . Есть ли какая-то основная, структурная причина, по которой немыслимо, что мы когда-нибудь найдем S ( n ) для n > 4 ? Что такого отличного в n = 4 от n = 5 ? Или n = 6 ? Где-то на этом пути должна быть какая-то...
По поводу предложения Рафаэля о пересечении двух NPDA : Пусть и A 2 NPDA для контекстно-свободных языков L 1 и L 2 соответственно. Предполагая, что мы знаем, что L = L 1 ∩ L 2 не зависит от контекста, можем ли мы (эффективно) построить NPDA A для L ?A1A1A_1A2A2A_2L1L1L_1L2L2L_2L = L1∩ L2Lзнак...
Мне интересно, если решение разрешимости проблемы является разрешимой проблемой. Я не думаю, но после начальных поисков я не могу найти литературу по этой...
Тем не менее, многие «знаменитые» неразрешимые проблемы, по крайней мере, полуразрешимы, а их дополнение неразрешимо. Одним из примеров, прежде всего, может быть проблема остановки и ее дополнение. Тем не менее, кто-нибудь может привести пример, в котором проблема и ее дополнение неразрешимы и не...
Если у нас есть какая-либо произвольная компьютерная программа, которая может изменить ее инструкции, возможно ли смоделировать эту программу с помощью программы, которая не может изменить ее инструкции? Редактировать: Я новичок в stackexchange, поэтому не уверен, что мне разрешено задавать НОВЫЙ...
Я изучаю теорему SMN, и концепция напомнила мне о карри. Из википедии статьи о теореме SMN : теорема утверждает, что для данного языка программирования и целые положительные числа т и п, существует определенный алгоритм, который принимает в качестве входных данных исходный код программы с т + п...
Говорят, что теория вычислимости также называется теорией рекурсии. Почему это так называется? Почему рекурсия имеет такое большое
Комментарий к tex.SE заставил меня задуматься. Утверждение по существу: Если я могу написать компилятор для языка X на языке X, то X полон по Тьюрингу. В терминах вычислимости и формальных языков это: Если решает , L ⊆ L T M и ⟨ M ⟩ ∈ L , то F L = R E .MMML ⊆ LТ МL⊆LTML \subseteq L_{\mathrm{TM}}⟨...
Вот проблема: Докажите, что одноленточные машины Тьюринга, которые не могут писать на той части ленты, которая содержит входную строку, распознают только обычные языки. Моя идея состоит в том, чтобы доказать, что этот конкретный TM эквивалентен DFA. Использовать эту ТМ для симуляции DFA очень...
У меня проблемы с пониманием проблемы остановки Тьюринга. Его доказательство предполагает, что существует магическая машина которая может определить, будет ли компьютер останавливаться или зацикливаться навсегда для данного ввода. Затем мы подключаем другую машину, которая обращает вывод, и у нас...
Как можно решить, имеет ли некоторую последовательность цифр? ππ\piвдохновил меня на вопрос, можно ли вычислить следующую невинную версию: е( n ) = { 10если н¯ происходит в десятичном представлении πв противном случаеf(n)={1if n¯ occurs in the decimal representation of π0otherwisef(n) =...
Переписывание системы представляет собой набор правил в виде . Если мы применим это правило к строке мы заменим любую подстроку в подстрокой и наоборот.A ↔ BA↔ВA \leftrightarrow BвесвесwAAAвесвесwВВB Учитывая начальную строку мы можем получить в системе по следующим правилам:A A A B BAAAВВAAABBB A...
Одним из определений вычислимо перечислимого (ce, эквивалентного рекурсивно перечислимому, эквивалентного полуразрешимому) множества является следующее: A⊆Σ∗A⊆Σ∗A \subseteq \Sigma^* означает, что существует разрешимый язык (называемый верификатором) st для всех ,V⊆Σ∗V⊆Σ∗V\subseteq...
Недавний экзаменационный вопрос звучал так: AAA - бесконечное рекурсивно перечислимое множество. Докажите, что имеет бесконечное рекурсивное подмножество.AAA Пусть бесконечное рекурсивное подмножество . Должен ли иметь подмножество, которое не является рекурсивно перечислимым?CCCAAACCC Я ответил 1....
Возможно ли теоретически указать язык программирования, для которого не может быть никакой реализации? Язык программирования - это способ определения функций. Реализация означает метод для выполнения данной программы на этом языке на заданном входе для вывода функции, соответствующей программе на...
Я столкнулся со следующей интересной проблемой: пусть - многочлены над полем действительных чисел, и предположим, что все их коэффициенты целочисленные (то есть существует конечное точное представление этих многочленов). При необходимости можно предположить, что степень обоих полиномов равна....
Есть ли алгоритм для решения следующей задачи: При заданной машине Тьюринга которая определяет язык L , существует ли машина Тьюринга M 2, решающая L так , что t 2 ( n ) = o ( t 1 ( n ) ) ?M1M1M_1LLLM2M2M_2LLLt2(n)=o(t1(n))t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Функции и t 2 являются наихудшим временем...