Émulation Oblivious Turing Machine borne inférieure

Existe-t-il une preuve que l'émulation d'une machine de Turing sur une machine de Turing inconsciente ne peut pas être effectuée en moins de$\mathcal{O}\left(m\log m\right)$ where $m$ is the number of steps the Turing machine uses? Or is this just an upper bound?

In the paper of Paul Vitányi about relativized oblivious Turing machines, Vitányi claims

"They [Pippenger and Fischer, 1979] showed that this result cannot be improved in general, since there is a language L wich is recognized by a 1-tape real-time Turing machine $M$, and any oblivious Turing machine $M'$ recognizing $L$ must use at least an order $O(n \log n)$ steps".

This should state $O(m \log m)$ as an absolute bound. However I don't find any proof of this in

Pippenger, Nicholas; Fischer, Michael J., Relations among complexity measures, J. Assoc. Comput. Mach. 26, 361-381 (1979). ZBL0405.68041.

Any ideas? Furthermore, what is the space complexity of this emulation? As far as I know the conversion to a universal Turing machine only doubles the tape length. Can I assume that the space complexity is $\mathcal{O}\left(l\right)$ with $l$ the space complexity of the original Turing machine?

Comme mentionné ci-dessus, on ne sait pas en général s'il existe une simulation inconsciente plus rapide.

Mais des limites inférieures intéressantes pour ce problème sont connues, dans des conditions plus contraintes. Par exemple, si vous voulez une simulation inconsciente qui préserve non seulement le temps$t$ mais aussi l'utilisation de l'espace $s$? Beame et Machmouchi ont récemment prouvé un compromis intéressant espace-temps limite inférieure pour ce problème: soit l'espace doit augmenter d'un facteur de$n^{1-o(1)}$ou le temps doit être multiplié par $\Omega(\log n \cdot \log \log n)$.

Le document est ici: http://eccc.hpi-web.de/report/2010/104/

Juste un commentaire étendu: je pense que c'est toujours un problème ouvert; voir le blog de Lipton et Regan pour de belles discussions sur l'amélioration du résultat du théorème de Fischer-Pippenger .

Par exemple, voir les articles: Oblivious Turing Machines et a "Crock" or Circuits Bounds for Turing Machine Computations (tous deux datés de 2009).

Dans le deuxième post, ils montrent qu'un meilleur circuit lié ( $O(n \log {\log n})$) est possible en utilisant une fonction booléenne partielle $g:2^n \to \{0,1,*\}$qui se rapproche de la fonction d'origine$f$ sur $2^{n-o(n)}$ inputs.