После прочтения соответствующего вопроса о неконструктивных доказательствах существования алгоритмов мне стало интересно, есть ли способы показать существование «маленьких» (скажем, состояний) вычислительных машин без фактического их построения. Формально: предположим, нам дан некоторый язык и...
Я ищу небольшой язык, который поможет «убедить» студентов, что машины Тьюринга являются достаточно общей вычислительной моделью. Это язык, который похож на языки, к которым они привыкли, но также легко моделируется на машине Тьюринга. Пападимитриу использует машины ОЗУ для этой работы, но я боюсь,...
Ответ: неизвестно Большое спасибо всем, кто помог уточнить этот вопрос и определения, связанные с ним. Определения этой вики послужили отправной точкой для более новой вики TCS: « Содержит ли P языки, существование которых не зависит от PA или ZFC? (Вики сообщества TCS) ». Более поздняя вики...
Робин Ганди был учеником Алана Тьюринга . Ганди сделал анализ Аналитического двигателя Бэббиджа (см. «Ганди - Слияние идей в 1936 году», цитируемый в «Херкен, Рольф - Универсальная машина Тьюринга - Обследование за полвека . Springer Verlag») - и сказал, что это сделал (ср. стр. 52–53):...
В честь дня рождения Алана Тьюринга Google опубликовал рисунок, показывающий машину. Что за машина это каракули? Может ли он выражать язык Тьюринга? Существуют очевидные отличия от классической машины Тьюринга: конечная лента, ограничения на то, как можно связать состояние, ... Каракули еще можно...
Я магистр, специализирующийся на распределенных системах, но также интересующийся теоретической информатикой. Мне было интересно, есть ли формальное представление распределенной системы поверх машины Тьюринга? То есть возможно ли расширить (сделать вариант) концепцию машины Тьюринга, чтобы...
Я играл с очень интересным и все еще открытым вопросом « Азбука одноленточной машины Тьюринга » (Эмануэле Виола) и придумал следующий язык: L = { x ∈ { 0 , 1 }N ул | х | = n = 2м и c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1 }L={x∈{0,1}n s.t. |x|=n=2m and count1(x)=k∗m;n,m,k≥1}L = \{ x \in \{0,1\}^n...
Кажется, большая часть литературы посвящена машинам с одним оракулом для конкретных задач, однако, как представляется, есть несколько статей, в которых рассматриваются машины с несколькими оракулами. Есть хорошая статья или тезис, который дает обзор того, что известно о таких машинах? В частности...
Недетерминированные линейные ограниченные автоматы ограниченного посещения распознают только регулярные языки? Под недетерминированным линейным ограниченным автоматом (nLBA) я подразумеваю недетерминированную машину Тьюринга с одной лентой, где вход «дополняется» конечными маркерами на обоих...
Давайте исправим кодировку машин Тьюринга и универсальной машины Тьюринга U, которая на входе (T, x) выводит все выходные данные T на входе x (возможно, оба работают вечно). Определим колмогоровскую сложность x, K (x) как длину самой короткой программы p, такой, что U (p) = x. Существует ли N...
Какое-то время мне было любопытно, что машины Тьюринга имеют ровно одну ленту и ровно 3 состояния (а именно, начальное состояние , состояние принятия и состояние отказа ). Обратите внимание, что я допускаю произвольные (конечные) алфавиты ленты (т. Е. Алфавит ленты не ограничен равным входному...
У меня наивный вопрос: существует ли машина Тьюринга, завершение которой истинно, но недоказуемо какой-либо естественной, последовательной и конечно аксиоматизируемой теорией? Я прошу простое доказательство существования, а не конкретный пример. Это может быть связано с порядковым анализом ....