Une machine de Turing sans capacité d'écriture sur des cellules vierges est-elle moins puissante que la Turing standard?

Une machine de Turing sans capacité d'écriture sur des cellules vierges est-elle moins puissante que la Turing standard?

Je pense que la réponse est oui mais je ne suis pas en mesure de trouver un calcul qu'une machine standard de Turing peut faire mais cette machine ne le peut pas.

Des idées?

En d'autres termes, " Un ordinateur avec une mémoire limitée serait-il moins puissant qu'un ordinateur avec une mémoire illimitée. "?

Nat

Réponses:

Le type de machine de Turing que vous décrivez est un automate borné linéaire (il ne peut écrire que sur les parties de la bande contenant l'entrée). Les LBA sont les accepteurs des langages contextuels, donc pour trouver un exemple spécifique d'un problème qui ne peut pas être résolu avec cette restriction mais qui peut être résolu en général par une machine Turing, vous avez juste besoin d'un langage décidable mais pas contextuel. sensible.

L'exemple donné sur Wikipedia est:

Un exemple de langage récursif qui n'est pas sensible au contexte est tout langage récursif dont la décision est un problème difficile à EXPSPACE, disons l'ensemble de paires d'expressions régulières équivalentes avec exponentiation.

Pour plus d'exemples, voir Existe - t-il un exemple de langage récursif qui n'est pas sensible au contexte?

roctothorpe
la source

Une machine de Turing qui ne peut pas écrire sur des blancs est par la version spatiale du théorème d'accélération linéaire un automate borné linéaire. Par conséquent, aucun problème de décision en dehors de ne peut être résolu par celui-ci. De tels problèmes existent par le théorème de la hiérarchie spatiale. $\textsf{DSPACE}(O(n))$

tri rapide
la source

Ne pouvez-vous pas simplement fournir un suffixe suffisamment long, pour un problème donné, de symboles spéciaux à la fin de la bande pouvant être utilisés comme blancs?

gen

@gen Pas en général. Dans le cas le plus général, notez simplement que la connaissance d'un suffixe aussi long rendrait le problème d'arrêt décidable. Par conséquent, le calcul d'un préfixe suffisamment long peut être indécidable, en général - il est donc déraisonnable de supposer qu'un tel suffixe est donné.

chi

Serait-il exact d'interpréter cette réponse comme: "Les machines Turing avec une mémoire limitée n'auront pas assez de mémoire pour exécuter un programme arbitraire, car certains programmes peuvent nécessiter plus de mémoire que ce qu'ils se trouvent. "?

Nat

@Nat: Je dirais que "la quantité de mémoire dont un programme peut avoir besoin est généralement inconnue jusqu'à ce que le programme soit exécuté". Ce qui est curieux (un grand paradoxe mathématique), c'est que pour tout triplet entier X, Y, Z, il existe une limite supérieure au nombre de cellules de bande requises pour les programmes qui se termineront et qui contiennent au plus X états, sur des bandes qui peuvent contenir au plus Y types de symboles, et sont initialisés avec des symboles Z sur la bande, mais aucune limite supérieure n'est prouvable, sauf pour les valeurs triviales de X, Y et Z.

supercat