Азбука одноленточной машины Тьюринга

40

Может ли каждая функция f:{0,1}{0,1} , вычисляемая за время t на одноленточной машине Тьюринга с использованием алфавита размера k=O(1) вычисляться за время O(t) на машина одной ленты Тьюринга с использованием алфавита размером 3 (скажем, 0,1, и пробел)?

(Из комментариев ниже от OP) Обратите внимание, что ввод записывается с использованием , но машина Тьюринга, использующая алфавит размера k, может перезаписывать входные символы символами из большего алфавита. Я не вижу, как кодировать символы в большем алфавите в меньшем алфавите без необходимости сдвигать ввод, что будет стоить времени n 2 .0,1kn2

Manu
источник
8
Обратите внимание, что ввод записывается с использованием , но машина Тьюринга, использующая алфавит размера k, может перезаписывать входные символы символами из большего алфавита. Я не вижу, как кодировать символы в большем алфавите в меньшем алфавите без необходимости сдвигать ввод, что будет стоить времени n 2 . 0,1kn2
Ману,
4
@Emanuele: Вы должны отредактировать вопрос и подчеркнуть этот аспект; в противном случае это звучит так же, как стандартное учебное упражнение ...
Юкка Суомела
3
@ Tsuyoshi, я думаю, ты неправильно понял вопрос.
Суреш Венкат
4
@Jukka: На одноленточной машине Тьюринга все, что можно вычислить за время , фактически является обычными языками. о(NжурналN)
Кристоффер Арнсфельт Хансен
6
@Abel: Результат, который вы цитируете от Arora и Barak, обходит основную проблему здесь, потому что в их модели (которая является довольно стандартной для многоленточных TM), у них есть отдельная входная лента только для чтения.
Джошуа Грохов

Ответы:

5

Частичный ответ, если TM работает в о(|Икс|журнал|Икс|)

Если TM4 является 4-символьным TM (с алфавитом Σ4={ϵ,0,1,2} ), который вычисляет , то есть решает язык L = { x | f ( x ) = 1 } в ( o ( | x | log | x | ) )f:{0,1}{0,1}L={x|f(x)=1}(o(|x|log|x|))

Одна ленточная детерминированная линейно-временная сложность равна 1DLIN=1DTime(O(n))

  • Хенни доказал (1), что REG=1DLIN
  • Кобаяши доказал (2), что REG=1DTime(o(nlogn))

Таким образом, регулярна и, очевидно, все еще регулярна по алфавиту Σ 3 = { ϵ , 0 , 1 }LΣ3={ϵ,0,1}

Таким образом, существует DFA, который определяет L и использует только символы в . 3-символьный TM3 с одной лентой может быть построен непосредственно из DFA, и он выбирает L, используя тот же незаполненный вход исходного TM4 .Σ3

... вы не можете собрать его напрямую из TM4, но TM3 существует.

Если TM4 работает в вы можете сместить вход и выполнить прямое преобразование из TM4 в TM3.Ω(n2)

Как отмечено в комментариях, сложный случай - когда TM4 работает в .Ω(nlogn)o(n2)


(1) Хенни, расчеты машины Тьюринга в автономном режиме с одной лентой (1965)

(2) Кобаяши, О структуре недетерминированной одноленточной иерархии времени машины Тьюринга (1985)

Марцио де Биаси
источник
1
Дело уже отмечен Кристоффером Арнсфельтом Хансеном в комментариях под вопросом. Действительно интересный случай - это Ω ( n log n ) o ( n 2 ) . o(nlogn)Ω(nlogn)o(n2)
Каве
Вы правы, я не заметил комментарий Кристоффера. Я плохо выразил интересный случай (я не знаю, как это доказать), поэтому я обновил ответ.
Марцио Де Биаси
1
@Kaveh: А как насчет -временных машин для проблем с обещаниями? Мы уже знаем, как преобразовать, например, любую машину, которая решает проблему обещания за O ( n ) времени? Я не вижу, как это сделать, и связь с обычными языками больше не работает (если я не ошибаюсь). o(nlogn)O(n)
Юкка Суомела
1
@Kaveh: Разве вы не можете просто взять задачу которая не является обычным языком, но может быть решена с помощью машины Тьюринга в, например, O ( n 2 ) раундах, и определить задачу обещания следующим образом: yes-экземпляры состоят из строкаLO(n2) за которой следует | х | 2 бита заполнения; без экземпляров состоит из строки x L, за которой следует | х | 2 бита заполнения. Задача обещания разрешима в O ( n )xL|x|2xL|x|2O(n)время, и это не разрешимо, используя конечный автомат.
Юкка Суомела
1
@Kaveh: Я полагаю, что интуитивный аргумент не работает по следующей причине: Да, существует проблема, не связанная с обещаниями, которая решается на той же машине. Тем не менее, время работы машины может достигать Θ(n2) для некоторых входов. (Интуитивно понятно, что машина не может проверить, достаточно ли заполнения, и, следовательно, «для безопасной игры», она должна предполагать, что после префикса имеется достаточно заполнения . Тогда она тратит время Θ ( | x | 2 ), чтобы определить, является ли x L и это слишком много, если, например, у нас было только Θ ( | x | )xΘ(|x|2)xLΘ(|x|)немного отступов.)
Юкка Суомела
-4

Для всех размеров алфавита больше выполнения изменяется только на постоянный коэффициент, так как log k1 для всех K , л > 1 .logk(x)Θ(logl(x))k,l>1

Разработка: В временных шагов предполагаемая машина Тьюринга может обрабатывать не более t позиций / битов. Биты взяты из k -нарного алфавита, wlog { 0 , 1 , , k - 1 } . Создайте новую машину Тьюринга, заменив каждый переход на ttk{0,1,,k1} переходов; каждый старый бит кодируется с помощьюlog 2 ( k ) битов в { 0 , 1 }log2(k)log2(k){0,1}(пробелы зарезервированы для пометки неиспользуемых ячеек). Обратите внимание, что это по существу двоичные цифры.

Очевидно, что в результате машина исполняет тьюринговы самое большее шаги.log2(k)tO(t)

Дополнение: Вышеупомянутые разрывы аргументации, потому что операции, которые перезаписывают входной символ с битом не в не могут быть переведены непосредственно; вход должен быть сдвинут. Это может быть исправлено путем перевода исходного ввода перед началом вычисления (по существу, дополнением); это можно сделать за время O ( n 2{0,1} ,результатев общее время выполнения O ( п 2 ) + вход 2 ( K ) т .O(n2)O(n2)+log2(k)t

Следовательно, использование только двух символов для кодирования промежуточных результатов не оказывает асимптотического влияния, если , но предварительная обработка преобладает в более быстрых алгоритмах. Поскольку наиболее интересные функции находятся в Ω ( n 2 ) (например, добавление двух чисел), можно считать, что проблема пренебрежимо мала.t(n)Ω(n2)Ω(n2)

Рафаэль
источник
3
Пока вы не убедите меня, почему это так, я буду сдерживать это.
Андрей Бауэр
1
Я хотел бы услышать некоторые доказательства вашего заявления. Все это только одна претензия.
Андрей Бауэр
2
О, я понимаю, что вы имеете в виду. Хорошо извини Однако вопрос не об этом . Это небольшое изменение.
Андрей Бауэр
6
Я думаю, что случай с t = Ω (n ^ 2) является простым случаем, потому что вы можете позволить себе сместить входную строку. Существенным является случай, когда t = o (n ^ 2). Я не знаю, насколько важно рассматривать одноленточную ТМ с o (n ^ 2) временем, но вопрос об этом.
Цуёси Ито
3
Исходный вопрос уже подразумевает, что случай Ω(n2) прост; следовательно, я действительно не вижу, как этот ответ добавляет что-то новое ...
Юкка Суомела