Забытая нижняя граница эмуляции машины Тьюринга

Есть ли доказательство того, что эмуляция машины Тьюринга на забывающей машине Тьюринга не может быть выполнена менее чем за $\mathcal{O}\left(m\log m\right)$ где $m$ - это число шагов, которые машина Тьюринга использует? Или это только верхняя граница?

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

«Они [ Pippenger и Фишер, 1979 ] показал , что этот результат не может быть улучшена в целом, так как существует язык L которым распознается 1-ленты в реальном времени машина Тьюринга $M$ , и любая забывающий машина Тьюринга $M'$ признание $L$ сусло используйте хотя бы порядок $O(n \log n)$ шагов ".

Это должно заявить $O(m \log m)$ как абсолютную границу. Однако я не нахожу никаких доказательств этого в

Пиппенгер, Николас; Фишер, Майкл Дж. , Соотношения между мерами сложности , J. Assoc. Вычи. Мах. 26, 361-381 (1979). ZBL0405.68041 .

Есть идеи? Кроме того, какова пространственная сложность этой эмуляции? Насколько я знаю, переход на универсальную машину Тьюринга только удваивает длину ленты. Могу ли я предположить, что сложность пространства равна $\mathcal{O}\left(l\right)$ при $l$ сложности пространства оригинальной машины Тьюринга?

Как упомянуто выше, в общем случае неизвестно, существует ли более быстрое забытое моделирование.

Но интересные нижние оценки для этой проблемы известны в более ограниченных условиях. Например, что если вы хотите забыть о симуляции, которая сохраняет не только время но и использование пространства s ? Beame и Machmouchi недавно доказали интересное пространство-время компромиссом нижняя граница для этой проблемы: либо пространство должно увеличиваться на коэффициент п 1 - O ( 1 ) , или время должно увеличиваться на коэффициент Q , ( журнал N ⋅ журнал войти n ) .$t$$s$$n^{1-o(1)}$$\Omega(\log n \cdot \log \log n)$

Документ находится здесь: http://eccc.hpi-web.de/report/2010/104/

Просто расширенный комментарий: я думаю, что это все еще открытая проблема; см. блог Липтона и Риган, где можно обсудить некоторые вопросы, касающиеся улучшения результата теоремы Фишера-Пиппенгера .

Например, см. Сообщения: « Забывчивые машины Тьюринга» и « Границы » или «Пределы цепей» для вычислений машины Тьюринга (обе датированы 2009 г.).

Во втором посте они показывают, что лучшая оценка цепи ( ) возможна с использованием частично булевой функции g : 2 n → { 0 , 1 , ∗ }, которая аппроксимирует исходную функцию f на 2 n - o ( n ) входов.$O(n \log {\log n})$$g:2^n \to \{0,1,*\}$$f$$2^{n-o(n)}$