Pourquoi utilisons-nous des machines de Turing à bande unique pour la complexité du temps?

Comme vous le savez, il existe de nombreuses anomalies pour les machines de Turing à bande unique lorsque le temps est : simulation multi-bande TM, simulation d'un alphabet de bande plus grand avec seulement , constructibilité temporelle, non-étanchéité du théorème de la hiérarchie temporelle, ... $o(n^2)$ $\{0,1,b\}$

Également des résultats comme , et des limites inférieures de temps très spécifiques au modèle pour des problèmes simples (qui ne se traduisent pas par des limites inférieures même super-linéaires sur deux bande TM). $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$ $O(n^2)$

Pour la complexité de l'espace, nous utilisons un modèle où nous avons une bande d'entrée en lecture seule séparée, qui est plus naturelle et plus robuste.

Un modèle de MT avec plusieurs bandes (ou au moins 2 bandes de travail) serait beaucoup plus robuste et ne conduirait pas à des anomalies comme celles que j'ai énumérées ci-dessus. J'ai demandé une fois à un éminent théoricien de la complexité qui a prouvé des résultats de simulation dans les premières années de la théorie de la complexité s'il connaissait des améliorations sur l'un de ces anciens résultats et la réponse a été qu'il ne pense pas que "les questions sur le modèle à une bande sont que important".

Si nous modifions le modèle standard de complexité temporelle en deux MT de bande, les résultats raisonnables de la théorie de la complexité ne changeront pas et nous éviterons ces anomalies causées par un modèle particulier. Ma question est donc:

y a-t-il une raison pour laquelle la complexité temporelle est toujours définie en termes de MT à bande unique? (autres que des raisons historiques)

cc.complexity-theory turing-machines Kaveh
la source

Je n'ai jamais vu de complexité temporelle définie par des MT à bande unique. Je n'ai vu que les classes de complexité temporelle robustes définies par les MT à bande unique.

$\:$

$\;\;$

@ Ricky, je voulais dire que la complexité temporelle d'un problème est définie en termes de complexité temporelle des MT à bande unique qui peuvent le résoudre.

Kaveh

et je veux dire que je n'ai jamais vu ça faire. J'ai toujours vu, au minimum, un accès aléatoire.

$\:$

$\;\;$

mais est-ce vraiment la définition habituelle? ce que j'ai vu dans les manuels est: 1) définir une machine de Turing à bande unique (car c'est plus simple); 2) montrer comment s'étendre à d'autres variantes, en particulier multi-bandes et accès aléatoire; 3) montrent que tous ces éléments peuvent se simuler avec au plus un ralentissement polynomial; 4) oubliez rapidement le modèle pour la plupart, au moins jusqu'à ce que nous ayons besoin de choses plus subtiles comme des machines Oracle et des réductions d'espace de journalisation; donc, comme @RickyDemer, je contesterais l'affirmation selon laquelle c'est vraiment la définition habituelle.

Sasho Nikolov

Je n'ai pas de réponse à cela, mais je veux juste vous montrer ce travail de Yamakami ( springerlink.com/content/u844854721p83870 ). Cet article explique ce qui se passe lorsque vous ajoutez des conseils à une petite machine (c.-à-d. Une bande unique à temps linéaire TM). Il prouve plusieurs séparations de classes, mais il le fait en utilisant ces MT à une bande. Ces séparations ne fonctionneraient pas si vous aviez un autre type de MT. Je pense que c'est un bel exemple où vous pouvez prouver des choses sympas avec une seule bande et probablement pas avec un modèle différent. La morale est "les questions d'une seule bande lorsque vous traitez des choses subtiles".

Marcos Villagra

Réponses:

Les autres réponses sont très belles. Je voudrais partager un commentaire que Russell Impagliazzo a fait il y a des années dans une conférence, qui est restée avec moi depuis.

Je pense que Turing a peut-être préféré une seule bande TM en raison de la plausibilité physique.

J'ai pointé Russell sur ce fil il y a quelques jours mais, vu qu'il n'est pas ici, j'aimerais que son commentaire soit connu, et je ferai de mon mieux pour l'interpréter.

Pour une seule bande TM, en supposant une bande de longueur infinie (veuillez rester avec moi), vous pouvez construire une TM qui a juste besoin d'une quantité limitée d'énergie par itération. Imaginez la bande comme une longue tige, et la tête, qui contient toute la logique TM, se déplace simplement le long de cette tige. (Je pense que c'est un joli petit engin à engrenages, utilisant une technologie très primitive. La tige peut avoir des encoches pour l'aider, et le contenu des cellules de bande peut simplement être un bloc glissé orthogonalement à l'axe de la tige.)

D'un autre côté, comment procédez-vous pour une -tape TM? Si vous avez $k$ $k$ des engins ci-dessus, ils doivent communiquer leur état de lecture aux autres têtes potentiellement extrêmement éloignées, ce qui prend des quantités d'énergie illimitées (disons que vous utilisez des fils, qui fuient nécessairement de la chaleur), et en plus n'est pas instantané, compliquant ainsi le mécanisme. Si au lieu de cela vous gardiez les têtes ensemble et déplaçiez les bandes en dessous, vous utiliseriez suffisamment d'énergie pour déplacer des bandes de longueur infinie. Je ne vois pas comment obtenir une énergie limitée dans les deux cas. Des astuces comme la réduction des incréments de bande (pour obtenir une longueur finie) supposent un univers infiniment divisible et violent des choses comme la constante de Planck et le principe holographique. Même en les ignorant, les mécanismes de la tête doivent être arbitrairement précis, ce qui provoque à nouveau des problèmes énergétiques et est prodigieusement compliqué.

Bien sûr, le premier schéma a des problèmes: la construction de la bande infinie avec une infinité d'encoches, une infinité de soleils pour alimenter les capteurs solaires sur la tête mobile, une offre infinie de fournitures de nettoyage et d'entretien, etc. Peut-être une percée majeure en mécanique quantique peut laisser les têtes tape bien communiquer, mais regardez maintenant à quel point notre engin est compliqué. En tout cas, je pense que le commentaire de Russell est très, très intéressant. $k$

matus
la source

je pensais que Turing essayait d'abstraire le concept d '"informatique" et non d'abstraire un modèle pour un appareil physique. dans ce cas, une machine de Turing à bande unique capture clairement l'intuition philosophique selon laquelle le calcul implique un accès local à une grande mémoire (infinie)

Sasho Nikolov

Je m'attendais à des raisons théoriques (non réalisabilité des modèles) mais je trouve cette réponse très intéressante, donc je l'accepte. Merci encore.

Kaveh

En gardant les têtes de bande en place, il semble que nous puissions rendre l'énergie logarithmique totale ou, espérons-le, pas pire que quasilinéaire dans le temps en concevant une forme de la construction de Hennie-Stearns. J'imagine les bandes enroulées en boucles de plus en plus grandes au fur et à mesure qu'elles s'étendent dans les deux sens ... Ou plus imaginativement, sur des bobines de bandes, 100 bandes sur une bobine, 100 bobines sur un rack, 100 racks sur un entrepôt, et sur et sur. Bien sûr, pour une énergie limitée par itération, nous aurions besoin d'une énergie totale linéaire dans le temps. Mais le quasi-linéaire est meilleur que le quadratique naïf, j'ai donc pensé le mentionner.

Dan Brumleve

$f(n)$

Il y a une raison pédagogique claire pour Sipser, à savoir que le cours se déroule naturellement de cette façon parce que:

Vous devez introduire la machine à bande unique avant la machine à bandes multiples, sinon la courbe d'apprentissage s'accentue.
$\cdot$ $\cdot$
Vous devriez idéalement comparer la machine à bandes multiples avec la machine à bande unique au moment où vous introduisez la machine à bandes multiples, sinon l'ignorance prolongée entraînera une confusion supplémentaire.
Vous pouvez omettre d'introduire les classes TIME analogues pour les machines multi-bandes, simplifiant ainsi la notation globale.

Il n'y a aucune raison de chicaner sur la propreté conceptuelle lorsque la pédagogie dicte si clairement le chemin le plus facile, et chaque étudiant en informatique doit suivre ce cours élémentaire, y compris tous ceux qui ne comprennent toujours pas les preuves.

Jeff Burdges
la source

Non, IIRC, ma première rencontre avec les MT a été la première édition de Hopcroft et Ullman. Mais la raison pour laquelle je pose cette question est en fait liée au joli manuel de Sipser, j'ai enseigné la théorie de la complexité basée sur Sipser et j'ai senti qu'elle serait plus simple et plus propre (sans perte de matériel essentiel) pour moi et les étudiants si elle était basée sur un multi -tape TMs. Tous ces petits détails techniques sur l'accès restreint des MT à bande unique seraient évités et je pourrais couvrir des sujets plus intéressants dans le temps limité dont je disposais. Sipser est détendu quant à l'utilisation de la thèse de Church-Turing,

Kaveh

donc je pensais qu'être détendu à propos de cette partie pourrait aussi être bien. Dans la partie théorème de la hiérarchie temporelle, il mentionne que le facteur de log supplémentaire n'est pas requis si nous avions plusieurs bandes et qu'il serait assez serré. Cela m'a amené à demander s'il y a une raison non historique d'utiliser des MT à bande unique pour la complexité temporelle. Ce n'est pas pire que d'utiliser une bande distincte en lecture seule pour la complexité de l'espace (et encore une fois, c'est principalement parce qu'une seule bande TM ne capture pas bien l'intuition des classes de complexité de petit espace).

Kaveh

Je ne vois pas comment on pourrait même donner un sens aux limites d'espace sub-linéaires sans une bande d'entrée séparée.

$\;$

Oui, je suppose que SPACE se fait différemment, en partie parce que vous ferez des limites sublinéaires, ce que vous ne ferez probablement pas pour TIME. Je plaiderais pour l'indexation de TIME ou pour faire tout ce que Sipser fait pour SPACE si vous souhaitez le faire de cette façon, je voudrais certainement parler de TIME ou TIME_1 ou autre avant les machines multi-bandes.

Jeff Burdges

Fait intéressant, Sipser dit simplement "machine de Turing" lors de la définition de l'espace (f (n)), mais modifie plus tard la définition lors de la discussion des fonctions sublinéaires f, en attribuant un exercice sur l'équivalence du superliner f. J'ai déjà enseigné ce matériel à Sipser. Je n'y avais pas trop réfléchi à l'époque, mais j'en suis heureux maintenant.

Jeff Burdges

La machine Turing d'origine a été décrite à l'aide d'une seule bande:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

Donc, comme vous le dites dans votre question, c'est principalement pour des raisons historiques. De plus, on a toujours tendance à se demander quel est le modèle le plus simple qui peut faire quelque chose ...

De plus, étant donné que ce sujet est généralement enseigné de manière très formelle, il est techniquement plus facile de décrire une machine à bande unique qu'un usinage à deux bandes.

Voir également:

http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html

Sariel Har-Peled
la source