Simulation universelle des machines de Turing

Soit une fonction fixe constructible dans le temps.$f$

Le résultat de simulation universelle classique pour les MT (Hennie et Stearns, 1966) indique qu'il existe un TM deux bandes tel que, étant donné$U$

• la description d'un TM , et$\langle M \rangle$
• une chaîne d'entrée ,$x$

s'exécute pour les étapes et renvoie la réponse de M sur x . Et g peut être considéré comme n'importe quelle fonction dans ω ( f ( n ) lg f ( n ) ) .$g(|x|)$$M$$x$$g$$\omega(f(n)\lg f(n))$

Mes questions sont:

1. Quel est le résultat de simulation le plus connu sur une seule bande TM? Le résultat ci-dessus est-il également valable?

2. Y a-t-il une amélioration par rapport à [HS66]? Peut-on simuler des MT sur une MT à deux bandes pour les étapes de manière plus rapide? Peut-on prendre g ( n ) pour être dans ω ( f ( n ) ) à la place de ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Quel est le résultat de simulation le plus connu sur une seule bande TM? Le résultat ci-dessus est-il également valable?

Nous pouvons simuler une MT à bandes multiples sur une TM à bande unique avec une augmentation quadratique du temps. Le temps de simulation est . L'augmentation quadratique est nécessaire car il existe des langages (par exemple les palindromes) qui nécessitent le temps Ω ( n 2 ) sur un DTM à bande unique mais peuvent être résolus dans le temps O ( n ) sur un DTM à deux bandes.$O(n^2)$$\Omega(n^2)$$O(n)$

En bref, le résultat ci-dessus ne fonctionne pas lorsque le simulateur est un TM à bande unique.

Pour la simulation de MT à bande unique sur une MT à bande unique (avec alphabet fini arbitraire), le résultat est valable, c'est-à-dire que la simulation peut être effectuée avec une augmentation du facteur dans le temps. Voir (2) et (3). La référence semble être (6).$\lg$

Y a-t-il une amélioration par rapport à [HS66]? Peut-on simuler des MT sur une MT à deux bandes pour les étapes de manière plus rapide? Peut-on prendre g ( n ) pour être dans ω ( f ( n ) ) à la place de ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Il semble qu'il n'y ait eu aucune amélioration car cela impliquerait un meilleur théorème de hiérarchie temporelle que celui actuellement connu.

Correction: Les théorèmes de hiérarchie habituels sont basés sur des classes de complexité temporelle définies à l'aide de MT à bande unique. Pour les TM à bande un résultat serré similaire au théorème de la hiérarchie spatiale est démontré par Furer en 1982 (5). Le facteur lg n'est pas nécessaire. Voir également (4).$n$$\lg$

Les références:

1. Peter van Emde Boas, "Machine Models and Simulation", dans Handbook of Theoretical Computer Science, 1990
   (en particulier, pp. 18-21)

2. Michael Sipser, "Introduction to the Theory of Computation", 2006
   (les classes de complexité temporelle sont définies à l'aide de MT avec bande unique infinie dans les deux directions et alphabet fini arbitraire, voir pages 140 et 341)

3. Odifreddi, "Théorie classique de la récursivité", vol. I & II, 1989 & 1999
   (les définitions sont similaires à Sipser, voir Def. I.4.1 in vol. I page 48, Def. VII.4.1 in vol. II page 67, and Thm. VII.4.15 in vol. II page 83)

4. Piergiorgio Odifreddi, "Théorie classique de la récursivité", vol. II, 1999
   (page 84)

5. Martin Fürer, " La hiérarchie temporelle déterministe serrée ", 1982

6. Juris Hartmanis, " Complexité computationnelle des calculs de machine de Turing à une bande ", 1968

7. FC Hennie et RE Stearns, " Simulation à deux bandes de machines de Turing à bandes multiples ", 1966

8. Autres questions connexes:

   1. Limites inférieures et séparation des classes ,
   2. $\lg f$
   3. Alphabet de machine de Turing à bande unique ,
   4. Pour le théorème de la hiérarchie temporelle, comment l'entrée est-elle traduite efficacement? ,
   5. un commentaire de Luca Trevisan.