Вопрос в упражнении 1.9 из книги Арора-Барака « Вычислительная сложность - современный подход» : Определите машину Тьюринга в ОЗУ как машину Тьюринга с оперативной памятью. Мы формализуем это следующим образом: У машины есть бесконечный массив A, который инициализируется для всех пробелов. Он...
Я получил доказательство перехода от перечислителя к машине Тьюринга (продолжайте запускать перечислитель и посмотрите, соответствует ли он вводу), но я не вижу, как работает другой способ. Согласно моим заметкам и книге (Введение в теорию вычислений - Sipser), чтобы получить перечислитель Тьюринга...
Означает ли принятие, что ТМ будет читать и распознавать символ из ячейки, с которой он в данный момент читает? И это тот случай, когда ТМ останавливается, если вход...
У меня есть следующая алгоритмическая проблема: Определить сложность пространства Тьюринга распознавания цепочек ДНК, которые являются палиндромами Уотсона-Крика. Палиндромы Уотсона-Крика - это строки, обратным дополнением которых является исходная строка. Дополнением определяется буква-накрест,...
Итак, вот вопрос из прошлого теста в моем классе теории вычислений: Бесполезное состояние в ТМ - это состояние, которое никогда не вводится ни в какую строку ввода. Пусть Докажите, что неразрешима.USELESSTM={⟨M,q⟩∣q is a useless state in M}.USЕLЕSSTMзнак равно{⟨M,Q⟩|Q бесполезное состояние...
Машины Тьюринга и неограниченные грамматики - это два разных формализма, которые определяют языки RE. Некоторые языки RE разрешимы, но не все. Мы можем определить разрешимые языки с помощью машин Тьюринга, сказав, что язык разрешимый, если есть язык для языка, который останавливает и принимает все...
Я видел веб-сайты, которые якобы «доказывают», что HTML5 + CSS является Turing Complete. Я видел сайты, которые якобы «доказывают», что SQL завершен по Тьюрингу. Я видел множество веб-сайтов, которые якобы «объясняют», что значит быть завершенным по Тьюрингу. Достаточно! Где я могу найти книгу...
Я пытаюсь найти ответы на два вопроса об универсальной машине Тьюринга. Как универсальная машина Тьюринга может моделировать машину Тьюринга, если моделируемая машина имеет большее число состояний? Как универсальная машина Тьюринга может имитировать машину Тьюринга, если на моделируемой машине...
Доказано, что проблема определения, является ли вход палиндромом или нет, требует пространства на машине Тьюринга. Однако даже для сохранения входных данных требуется пространство n , не значит ли это, что всем машинам Тьюринга требуется пространство Ω ( n ) ?Ω ( журналн )Ω(журналN)\Omega(\log...
На этом сайте есть много вариантов вопроса о том, могут ли ТМ решить проблему остановки, будь то для всех других ТМ или определенных подмножеств. Этот вопрос несколько другой. Он спрашивает, может ли тот факт, что проблема остановки относится ко всем ТМ, может быть решен ТМ. Я верю, что ответ...
Почему вычислимые числа (в смысле Тьюринга) перечислимы? Это должно быть очень очевидно, но я сейчас просто не вижу
Читая этот вопрос « Естественные неразрешимые проблемы RE, но не полные по Тьюрингу », мне пришло в голову следующее: Если - это функция занятого бобра (максимально достижимая оценка среди всех останавливающих 2-символьных машин Тьюринга с n-состояниями описанного выше типа при запуске на чистой...
В предыдущем вопросе Что такое алгоритм? Я спросил, является ли алгоритм алгоритмом, который возвращает значение функции, основанной на массиве предварительно вычисленных значений. Один из ответов, который привлек мое внимание, был таким: Факторный пример попадает в другую модель вычисления,...
Чтобы доказать, что 3-раскраска разрешима, достаточно сказать: Каждый узел на графике имеет 3 возможных цвета Поэтому мы можем перечислить все возможностей и затем проверить, что никакие два ребра не соединяют узлы одного цвета3N3N3^n Означает ли это, что 3-раскраска разрешима? Или мне нужно...
Одно из утверждений о теореме Райса приведено на странице 35 «Вычислительная сложность: современный подход» (Арора-Барак): Частичная функция от до - это функция, которая не обязательно определяется на всех ее входах. Мы говорим, что TM вычисляет частичную функцию если для каждого для которого...
В колледже мы изучали теорию вычислений в целом и машины Тьюринга более конкретно. Одним из замечательных теоретических результатов является то, что за счет потенциально большого алфавита (символов) вы можете уменьшить количество состояний до 2. Я искал примеры различных машин Тьюринга, и...
Является ли машина Тьюринга, которому разрешено чтение и запись символов из бесконечного алфавита, более мощной, чем обычная ТМ (единственное отличие, у машины все еще есть конечное число состояний)? Интуиция говорит мне, что нет, так как вам нужно бесконечное количество состояний, чтобы...
Пусть входная строка будет задана как . Затем, если NFA в настоящее время находится в состоянии (и прочитал входной алфавит ), то перед чтением следующего входного символа NFA разделяется на два NFA, один из которых находится в состоянии а другой - в , если происходит переход тип . Если существует...
Булева функция - это функция .е: { 0 , 1 }N→ { 0 , 1 }е:{0,1}N→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} Известно, что логический базис является полным по Тьюрингу, поскольку он позволяет переворачивать любую последовательность или оставлять ее без изменений. То же самое можно сказать о воротах .( ∨ , ∧...
Кажется, я вспоминаю из студенческого класса, что для машины Тьюринга с конечной лентой всегда будут существовать соответствующие конечные автоматы, но я не смог найти это подтверждение где-либо в Интернете. Это на самом деле так, или я неправильно...