Почему мы используем одиночные ленточные машины Тьюринга для сложности времени?

Как вы знаете, существует много аномалий для одиночных ленточных машин Тьюринга, когда время : симуляция ТМ с несколькими лентами, симуляция большого алфавита ленты с просто , возможность построения времени, неплотность теоремы иерархии времени, ... $o(n^2)$ $\{0,1,b\}$

Также результаты, такие как , и очень специфичные для модели временные нижние границы для простых задач (которые не переводятся даже в суперлинейные нижние границы на двух ленточных TM). $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$ $O(n^2)$

Для сложности пространства мы используем модель, в которой у нас есть отдельная лента ввода только для чтения, которая является более естественной и надежной.

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

Если мы изменим стандартную модель сложности времени на две ленты ТМ, разумные результаты в теории сложности не изменятся, и мы избежим этих аномалий, вызванных конкретной моделью. Итак, мой вопрос:

Есть ли какая-то причина, почему временная сложность все еще определяется в терминах одиночных ТМ? (кроме исторических причин)

cc.complexity-theory turing-machines Кава
источник

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

$\:$ Я видел только надежные классы сложности времени, определенные одиночными ТМ.

$\;\;$

@ Рики, я имел в виду временную сложность проблемы, которая определяется с точки зрения временной сложности отдельных ленточных ТМ, которые могут ее решить.

Каве

и я имею в виду, что я никогда не видел, чтобы это было сделано.

$\:$ Я всегда видел, как минимум, произвольный доступ.

$\;\;$

но действительно ли это обычное определение? то, что я видел в учебниках: 1) определить одну машину ленты Тьюринга (потому что это проще); 2) показать, как распространиться на другие варианты, в частности на мульти-ленту и произвольный доступ; 3) показать, что все они могут симулировать друг друга с максимально полиномиальным замедлением; 4) быстро забыть о модели по большей части, по крайней мере, до тех пор, пока нам не понадобятся более тонкие вещи, такие как машины оракула и сокращение пространства журналов; поэтому, как и @RickyDemer, я бы оспорил утверждение, что это действительно обычное определение.

Сашо Николов

У меня нет ответа на этот вопрос, но я просто хочу показать вам эту работу Ямаками ( springerlink.com/content/u844854721p83870 ). В этой статье обсуждается, что происходит, когда вы добавляете рекомендации на небольшую машину (т. Е. Линейно-временная однотонная ТМ). Он доказывает несколько разделений классов, но делает это, используя эти одноленточные ТМ. Эти разделения не сработали бы, если бы у вас был другой вид ТМ. Я думаю, что это хороший пример, где вы можете доказать классные вещи с помощью одной ленты и, вероятно, не можете с другой моделью. Мораль заключается в том, что «когда речь идет о тонких вещах», это важно.

Маркос Вильягра

Ответы:

Другие ответы выглядят очень хорошо. Я хотел бы поделиться комментарием, который Рассел Импальяццо сделал несколько лет назад на лекции, которая с тех пор застряла у меня.

Я думаю, что Тьюринг, возможно, предпочел одну ленту ТМ из-за физической правдоподобности.

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

Для одиночной ленты TM, если предположить, что лента бесконечной длины (пожалуйста, придерживайтесь меня), вы можете создать TM, которой просто нужно ограниченное количество энергии на одну итерацию. Представьте ленту как длинный стержень, а головка, которая содержит всю логику ТМ, просто движется вдоль этого стержня. (Я думаю о нем как о милом маленьком приспособленном приспособлении, использующем очень примитивную технологию. У стержня могут быть выемки, чтобы помочь ему в этом, и содержимое ячейки ленты может быть просто блоком, смещенным ортогонально к оси стержня.)

С другой стороны, как вы делаете это для ленты TM? Если у вас есть $k$ $k$ Из вышеперечисленных хитростей они должны сообщить свое состояние чтения потенциально чрезвычайно удаленным другим головкам, которые потребляют неограниченное количество энергии (скажем, вы используете провода, которые обязательно пропускают тепло), и, кроме того, не являются мгновенными, что усложняет механизм. Если бы вместо этого вы держали головы вместе и перемещали ленты под ними, вы бы использовали достаточно энергии для перемещения лент бесконечной длины ... Я не вижу, как получить ограниченную энергию в любом случае. Трюки, такие как сжимание ленты (для получения конечной длины), предполагают бесконечно делимую вселенную и нарушают такие вещи, как постоянная Планка и голографический принцип. Даже игнорируя их, механизмы в голове должны быть сколь угодно точными, что опять-таки вызывает энергетические проблемы и невероятно сложно.

Конечно, у первой схемы есть проблемы: создание бесконечной ленты с бесконечным количеством выемок, бесконечного множества солнц для питания солнечных коллекторов на движущейся головке, бесконечного запаса чистящих и вспомогательных материалов и т. Д. Возможно, какой-то крупный прорыв в квантовой механике может позволить головкам ленты хорошо общаться, но теперь посмотрим, насколько сложна наша штуковина. В любом случае, я думаю, что комментарий Рассела очень, очень интересный. $k$

Матус
источник

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

Сашо Николов,

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

Каве

Удерживая ленточные головки на месте, кажется, что мы можем сделать полную энергию логлинеарной или, надеюсь, не хуже квазилинейной во времени, разработав форму конструкции Хенни-Стернса. Я представляю, как ленты скручиваются во все более крупные петли, когда они растягиваются в любом направлении ... Или, если быть более выразительным, на катушках с лентами, 100 лент на катушку, 100 катушек на стойку, 100 стоек на склад и т. Д. на. Конечно, для ограниченной энергии на итерацию нам понадобится полная энергия, линейная по времени. Но квазилинейный лучше, чем наивный квадратичный, поэтому я подумал, что упомяну это.

Дан Брумлев

$f(n)$

Есть кристально чистая педагогическая причина, почему Sipser делает это, а именно, курс естественным образом течет именно так, потому что:

Вы должны представить одну ленточную машину перед многоканальной машиной, в противном случае вы улучшите кривую обучения.
$\cdot$ $\cdot$
В идеале вам следует сравнивать многоленточный аппарат с одиночным ленточным автоматом в тот момент, когда вы вводите многоленточный аппарат, в противном случае длительное невежество приведет к дополнительной путанице.
Вы можете не вводить аналогичные классы TIME для многоленточных машин, что упрощает общее обозначение.

Нет смысла спорить о концептуальной чистоте, когда педагогика так четко определяет самый простой путь, и каждый студент, изучающий информатику, должен пройти этот элементарный курс, включая всех тех, кто до сих пор не понимает доказательств.

Джефф Берджес
источник

Нет, IIRC, мое первое знакомство с ТМ было первым изданием Хопкрофта и Уллмана. Но причина, по которой я задаю этот вопрос, на самом деле связана с хорошим учебником Сипсера, я преподавал теорию сложности на основе Сипсера и чувствовал, что она будет проще и чище (без потери существенного материала) для меня и студентов, если она будет основана на ТМ. Все эти мелкие технические подробности об ограниченном доступе одиночных ленточных ТМ можно было бы избежать, и я мог бы рассказать о более интересных материалах за то ограниченное время, которое у меня было. Sipser расслаблен в использовании тезиса Черча-Тьюринга,

Kaveh

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

Каве

Я не понимаю, как можно было бы понять смысл сублинейных пространственных границ без отдельной входной ленты.

$\;$

Да, я бы предположил, что SPACE выполняется по-другому, частично потому, что вы будете делать сублинейные границы, чего, скорее всего, не будет для TIME. Я бы поспорил за то, чтобы подписаться на TIME или делать то, что Sipser делает для SPACE, если вы хотите сделать это таким образом, конечно, я бы хотел поговорить о TIME или TIME_1 или о чем-либо еще до многоленточных машин.

Джефф Берджес

Интересно, что Sipser говорит просто «машина Тьюринга» при определении SPACE (f (n)), но позже меняет определение при обсуждении сублинейных функций f, назначая упражнение на эквивалентность для суперлайнера f. Я преподавал этот материал из Sipser раньше. В то время я не слишком много думал об этом, но сейчас мне это приятно.

Джефф Берджес

Оригинальная машина Тьюринга была описана с использованием одной ленты:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

Итак, как вы заявляете в своем вопросе, это в основном по историческим причинам. Кроме того, всегда есть тенденция спрашивать, какая простейшая модель может что-то сделать ...

Кроме того, поскольку эту тему обычно преподают очень формально, технически проще описать одну ленточную машину, чем две ленточные.

Сариэль Хар-Пелед
источник