Может ли каждая функция , вычисляемая за время на одноленточной машине Тьюринга с использованием алфавита размера вычисляться за время на машина одной ленты Тьюринга с использованием алфавита размером (скажем, и пробел)?
(Из комментариев ниже от OP) Обратите внимание, что ввод записывается с использованием , но машина Тьюринга, использующая алфавит размера k, может перезаписывать входные символы символами из большего алфавита. Я не вижу, как кодировать символы в большем алфавите в меньшем алфавите без необходимости сдвигать ввод, что будет стоить времени n 2 .
Ответы:
Частичный ответ, если TM работает вo(|x|log|x|)
Если 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))
Таким образом, регулярна и, очевидно, все еще регулярна по алфавиту Σ 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)
источник
Для всех размеров алфавита больше выполнения изменяется только на постоянный коэффициент, так как log k1 для всех K , л > 1 .logk(x)∈Θ(logl(x)) k,l>1 Разработка:В временных шагов предполагаемая машина Тьюринга может обрабатывать не более t позиций / битов. Биты взяты из k -нарного алфавита, wlog { 0 , 1 , … , k - 1 } . Создайте новую машину Тьюринга, заменив каждый переход на ⌈Очевидно, что в результате машина исполняет тьюринговы самое большее шаги.⌈log2(k)⌉⋅t∈O(t)
Дополнение: Вышеупомянутые разрывы аргументации, потому что операции, которые перезаписывают входной символ с битом не в не могут быть переведены непосредственно; вход должен быть сдвинут. Это может быть исправлено путем перевода исходного ввода перед началом вычисления (по существу, дополнением); это можно сделать за время O ( n 2{0,1} ,результатев общее время выполнения O ( п 2 ) + ⌈ вход 2 ( K ) ⌉ ⋅ т .O(n2) O(n2)+⌈log2(k)⌉⋅t
Следовательно, использование только двух символов для кодирования промежуточных результатов не оказывает асимптотического влияния, если , но предварительная обработка преобладает в более быстрых алгоритмах. Поскольку наиболее интересные функции находятся в Ω ( n 2 ) (например, добавление двух чисел), можно считать, что проблема пренебрежимо мала.t(n)∈Ω(n2) Ω(n2)
источник