Существуют релятивистские пространства-времени (например, пространства-времени МГ; см. Хогарт, 1994), где мировая линия бесконечной длительности может содержаться в прошлом конечного наблюдателя. Это означает, что обычный наблюдатель может иметь доступ к бесконечному количеству вычислительных...
Я знаю, что шлюзы NAND можно использовать для создания схем, реализующих каждую таблицу истинности, а современные компьютеры состоят из вентилей NAND. Какова теоретическая связь между воротами NAND и полнотой Тьюринга? Мне кажется, что схемы затворов NAND ближе к конечным автоматам, чем машины...
У меня есть эти вопросы из старого экзамена, который я пытаюсь решить. Для каждой задачи, вход является кодирование некоторой машины Тьюринга MMM . Для целого числа c>1c>1c>1 и следующих трех задач: Правда ли, что для каждого входа xxx M не передает |x|+c|x|+c|x|+c позиции при работе на xxx ?...
Я в некотором роде новичок, но очень интересуюсь областью вычислений и теории сложности, и я хочу разъяснить свое понимание того, как классифицировать проблемы и насколько сильно проблемы связаны с машиной, используемой для их решения. Мое понимание Стандартная машина Тьюринга - машина Тьюринга,...
Я читал в Википедии и некоторых других текстах, которые Проблема остановки [...] разрешима для линейных ограниченных автоматов (LBA) [и] детерминированных машин с конечной памятью. Но ранее было написано, что проблема остановки - неразрешимая проблема, и поэтому TM не может ее решить! Так как LBA...
Тем не менее, многие «знаменитые» неразрешимые проблемы, по крайней мере, полуразрешимы, а их дополнение неразрешимо. Одним из примеров, прежде всего, может быть проблема остановки и ее дополнение. Тем не менее, кто-нибудь может привести пример, в котором проблема и ее дополнение неразрешимы и не...
Я пытаюсь понять существование неузнаваемых языков. Чтобы понять это, мне нужно знать, почему машина Тьюринга распознает только один язык, а не несколько. Почему...
Я просматривал определение контекстно-зависимого языка в Википедии и обнаружил следующее: Каждая категория языков является надлежащим подмножеством категории прямо над ней. Любой автомат и любая грамматика в каждой категории имеют эквивалентный автомат или грамматику в категории непосредственно над...
Определения машин Тьюринга всегда явно указывают на то, что пустой символ не является частью входного алфавита. Интересно , что идет не так , когда вы бы сделать его частью входного алфавита, потому что фактически пустой символ , уже , кажется, часть входных данных. Чтобы объяснить, что «кажется» в...
Справочная информация: я полный дилетант в области компьютерных наук. Я читал о занятых номерах Бивер здесь , и я нашел следующий отрывок: Человечество может никогда не узнать значение BB (6) наверняка, не говоря уже о значении BB (7) или любом более высоком числе в последовательности. На самом...
Я читал ответ на недавний вопрос, и мне в голову пришла странная эфемерная мысль. Мои просьбы об этом могут предать либо то, что мои теоретические отбросы серьезно отсутствуют (в основном это правда), либо что мне еще слишком рано читать этот сайт. Теперь с отказом от ответственности ... Это хорошо...
Вот проблема: Докажите, что одноленточные машины Тьюринга, которые не могут писать на той части ленты, которая содержит входную строку, распознают только обычные языки. Моя идея состоит в том, чтобы доказать, что этот конкретный TM эквивалентен DFA. Использовать эту ТМ для симуляции DFA очень...
Я задавался вопросом, почему ленты / ленты не являются частью формального определения машины Тьюринга. Рассмотрим, например, формальное определение машины Тьюринга на странице Википедии . Определение, следующее за Хопкрофтом и Уллманом, включает в себя: конечный набор состояний , ленточный алфавит...
Мне сказали, что квантовые компьютеры не являются вычислительно более мощными, чем машины Тьюринга. Может ли кто-нибудь любезно помочь дать некоторые литературные ссылки, объясняющие этот...
Я прочитал несколько раз, что невозможно эффективно перевернуть ответ NDTM. Однако я не понимаю, почему. Например, учитывая NDTM который выполняется в , этот текст (раздел 3.3) утверждает, что неясно, как другой NDTM может определить за время, как перевернуть...
Означает ли существование неразрешимых проблем непосредственную непредсказуемость физических систем? Давайте рассмотрим проблему остановки, сначала мы построим физический UTM, скажем, используя обычную конструкцию на основе схем. Тогда не может быть никакой разрешимой физической теории, которая...
Пусть Есть ли машина Тьюринга R, которая решает (я не имею в виду, распознает) язык ?L ∅L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.L∅L∅L_\emptyset Похоже, тот же метод,...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Я читаю Sipser , и я нахожу , что это трудно понять , что этот процесс таким образом, что , если вы дадите мне K машины Тьюринга с к лентам, я могу выплюнуть эквивалентную машину Тьюринга только с одной лентой. Пример был бы хорош. На самом деле, отработанный пример , который показывает , как...
Я видел машины Тьюринга, изображенные бесконечными лентами в одном и двух направлениях. Есть ли разница в мощности таких машин Тьюринга или они в основном эквивалентны? В своей голове я думаю, что они эквивалентны, так как я предполагаю, что должен быть какой-то способ представить двустороннюю...