Например, в языках программирования обычно пишут компилятор / интерпретатор X-in-X, но на более общем уровне многие известные системы с полным набором Тьюринга могут имитировать себя впечатляющими способами (например, симуляция игры жизни Конвея в игре жизни Конвея). ). Итак, мой вопрос: способна...
Решение проблемы CNF-SAT можно описать следующим образом: Вход: булева формула в конъюнктивной нормальной форме.ϕφ\phi Вопрос: существует ли присвоение переменной, которая удовлетворяет ?ϕφ\phi Я рассматриваю несколько различных подходов к решению проблемы CNF-SAT с помощью недетерминированной...
Я где-то читал, что машина Тьюринга не может вычислить это, и поэтому она неразрешима, но почему? Почему для компьютера невозможно вычислить дерево разбора и принять решение? Возможно я ошибаюсь и это можно...
У меня совсем недавно была дискуссия о машинах Тьюринга, когда меня спросили: «Машина Тьюринга получена из автоматов или наоборот»? Конечно, я не знал ответа, но мне любопытно узнать. Машина Тьюринга - это немного более сложная версия автоматов Push-Down. Исходя из этого, я предполагаю, что машина...
Как вы знаете, существует много аномалий для одиночных ленточных машин Тьюринга, когда время : симуляция ТМ с несколькими лентами, симуляция большого алфавита ленты с просто { 0 , 1 , b } , возможность построения времени, неплотность теоремы иерархии времени,...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Отказ от ответственности: я очень мало знаю о теории сложности. Извините, но на самом деле нет способа задать этот вопрос, не будучи (ужасно) лаконичным: Какими должны быть морфизмы в «категории» машин Тьюринга? Это, очевидно, субъективно и зависит от толкования теории, поэтому в идеале ответ на...
Я жду определенного ответа на заглавный вопрос. Существует ли набор правил, который переводит любую программу в конфигурацию конечных фигур на бесконечной доске, например, если черно-белые играют только легальные ходы, игра заканчивается за конечное время, если программа останавливается? Правила те...
Любой язык, не являющийся полным по Тьюрингу, не может написать для себя интерпретатор. Я понятия не имею, где я это прочитал, но я видел, что это использовалось несколько раз. Кажется, что это порождает своего рода «окончательный» нетуринговский законченный язык; те, которые могут...
Одна из удивительных вещей в компьютерной науке заключается в том, что физическая реализация в некотором смысле «неактуальна». Люди успешно создали компьютеры из нескольких различных подложек - реле, вакуумных трубок, дискретных транзисторов и т. Д. Вскоре люди могут преуспеть в создании...
Учитывая язык L, определенный машиной Тьюринга, который его решает, возможно ли алгоритмически определить, лежит ли L в
С чисто абстрактной математической / вычислительной точки зрения (как) можно даже узнать или рассуждать о таких проблемах, как 3-SAT, сумма подмножества, коммивояжер и т. Д.,? Сможем ли мы хоть как-то осмыслить их с функциональной точки зрения? Будет ли это вообще возможно? Я размышлял над этим...
В связи с этим вопросом мне пришло в голову задаться вопросом: какова временная сложность одноленточной машины Тьюринга с одной головкой для вычисления длины ее входных данных? Чтобы быть точным, скажем, что алфавит ленты равен , входные данные представляют собой строку в ( 0 + 1 ) ∗, окруженную...
Проще говоря: как соотносятся машины Тьюринга с оракулами и семействами однородных цепей с оракулами? Как последние определяются для получения той же вычислительной модели для данной машины оракула Тьюринга? Это может быть элементарный вопрос, но не очевидно, где искать, и я из тех людей, которым...
Есть ли доказательство того, что эмуляция машины Тьюринга на забывающей машине Тьюринга не может быть выполнена менее чем за O(mlogm)O(mlogm)\mathcal{O}\left(m\log m\right) где mmm - это число шагов, которые машина Тьюринга использует? Или это только верхняя граница? Витани утверждает, что в...
Теорема иерархии времени утверждает, что машины Тьюринга могут решить больше проблем, если у них есть (достаточно) больше времени. Имеет ли это какое-то значение, если пространство ограничено асимптотически? Как DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) относится к...
Хорошо известно, что проблема остановки является неисчислимой. Тем не менее, можно экспоненциально «сжать» информацию о проблеме остановки, так что ее распаковка является вычислимой. Точнее, можно вычислить из описания машин Тьюринга и n- битного состояния рекомендации ответ на проблему остановки...
Я совершенно уверен, что я не первый, кто принимает идею, которую я собираюсь представить. Однако было бы полезно, если бы я мог найти какую-либо литературу, связанную с этой идеей. Идея состоит в том, чтобы построить машину Тьюринга M со свойством, что если P = NP, то M будет решать 3-SAT за...
Определите как класс языков, которые могут быть приняты машиной (множественной) Тьюринга за время f ( n ) + 1 . (« + 1 » просто для упрощения обозначений и предотвращения путаницы.) Обратите внимание, что вокруг f ( n ) + 1 нет O ( ⋅ ) .D T I M E (f( н ) )DTяMЕ(е(N))\mathsf{DTIME}(f(n))е( n ) +...
Есть ли машина Тьюринга, которая может решить, остановятся ли почти все другие машины Тьюринга? Предположим, у нас есть некоторое перечисление машин Тьюринга и некоторое представление о «размере» набора натуральных чисел ‖ ⋅ ‖ , и мы определяем:N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\|...