Является ли машина Тьюринга без возможности записи на пустые ячейки менее мощной, чем стандартная Тьюринг?

Является ли машина Тьюринга без возможности записи на пустые ячейки менее мощной, чем стандартная Тьюринг?

Я думаю, что ответ - да, но я не могу найти вычисление, которое может сделать стандартная машина Тьюринга, но эта машина не может.

Есть идеи?

Другими словами, «будет ли компьютер с ограниченной памятью менее мощным, чем компьютер с неограниченной памятью »?

Nat

Ответы:

Тип машины Тьюринга, который вы описываете, является линейным ограниченным автоматом (он может писать только на части ленты, содержащие входные данные). LBA являются акцепторами для контекстно-зависимых языков, поэтому, чтобы найти конкретный пример проблемы, которая не может быть решена с помощью этого ограничения, но может быть решена в целом на машине Тьюринга, вам просто нужен язык, который разрешим, но не зависит от контекста. чувствительны.

Пример, приведенный в Википедии:

Примером рекурсивного языка, который не является контекстно-зависимым, является любой рекурсивный язык, решение которого - сложная задача EXPSPACE, скажем, набор пар эквивалентных регулярных выражений с возведением в степень.

Дополнительные примеры см. В разделе « Есть ли пример рекурсивного языка, не зависящего от контекста»?

roctothorpe
источник

$\textsf{DSPACE}(O(n))$

быстрая сортировка
источник

Разве вы не можете просто предоставить достаточно длинный суффикс для любой конкретной проблемы специальных символов в конце ленты, которые можно использовать в качестве пробелов?

Gen

@gen Не в общем. В самом общем случае просто отметьте, что знание такого длинного суффикса сделает проблему остановки разрешимой. Следовательно, вычисление достаточно длинного префикса, вообще говоря, может быть неразрешимым, поэтому не стоит полагать, что такой суффикс задан.

Чи

Было бы правильнее интерпретировать этот ответ как « машины Тьюринга с ограниченной памятью не будет иметь достаточно памяти для запуска любой произвольной программы , так как некоторые программы могут требовать больше памяти , чем то , что они случаются иметь. »?

Nat

@Nat: Я бы сказал, что «объем памяти, который может потребоваться программе, в общем случае неизвестен до ее запуска». Что любопытно (большой математический парадокс), это то, что для любого целочисленного триплета X, Y, Z существует верхний предел числа ячеек ленты, необходимых для программ, которые завершаются и содержат не более X состояний, на лентах, которые могут содержать не более Y типов символов и инициализируются с помощью символов Z на ленте, но такая верхняя граница не доказуема, за исключением тривиальных значений X, Y и Z.

суперкат