Сегодня за ланчем я поднял эту проблему со своими коллегами, и, к моему удивлению, аргумент Джеффа Э., что проблема разрешима, не убедил их ( вот тесно связанный пост о mathoverflow). Постановка проблемы, которую легче объяснить («это P = NP?»), Также разрешима: да или нет, и поэтому один из двух...
Мне пришло в голову этот вопрос о проблеме остановки, и я не смог найти хорошего ответа в Интернете, задаваясь вопросом, может ли кто-нибудь помочь. Возможно ли, что проблема остановки разрешима для любого ТМ на любом входе, если он не сам ТМ? В принципе: Halts(TM, I) IF TM == I: Undecidable,...
На этом сайте есть много вариантов вопроса о том, могут ли ТМ решить проблему остановки, будь то для всех других ТМ или определенных подмножеств. Этот вопрос несколько другой. Он спрашивает, может ли тот факт, что проблема остановки относится ко всем ТМ, может быть решен ТМ. Я верю, что ответ...
В середине срока был вариант следующего вопроса: Для разрешимого определить Показать, что не обязательно разрешимый.прив ( 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...
Я пытаюсь придумать доказательство для следующего: Для любого языка AAA , существует язык BBB такие , что A≤TBA≤TBA \le_{\mathrm{T}} B , но B ≰TA≰TA\nleq_{\mathrm{T}} A . Я думал о том, чтобы позволить BBB быть ATMATMA_{\mathrm{TM}} , но я понимаю, что не все языки Тьюринга сводимы к...
Одно из утверждений о теореме Райса приведено на странице 35 «Вычислительная сложность: современный подход» (Арора-Барак): Частичная функция от до - это функция, которая не обязательно определяется на всех ее входах. Мы говорим, что TM вычисляет частичную функцию если для каждого для которого...