Calcul de la longueur d'entrée sur une machine de Turing à une bande

À propos de cette question, je me suis demandé: quelle est la complexité temporelle pour une machine de Turing à une seule bande et à une seule tête pour calculer la longueur de son entrée? Pour être précis, disons que l'alphabet de la bande est $\{0,1,b\}$ , l'entrée est une chaîne en $(0+1)^*$ entourée de blancs, la machine démarre au symbole d'entrée le plus à gauche et doit se terminer à la symbole le plus à gauche d'une chaîne en (à nouveau entouré de blancs) qui donne la représentation binaire de la longueur d'entrée. Cela peut également être considéré comme le problème de la conversion d'un nombre d'unaire en binaire. $(0+1)^*$

Il est facile de résoudre ce problème sur une machine à deux bandes ou à deux têtes en temps linéaire (il suffit de numériser l'entrée avec une tête tout en utilisant l'autre tête pour incrémenter plusieurs fois un compteur; l'incrémentation est une opération à temps amorti constant). Mais les solutions à tête unique que je peux proposer ne sont que (par exemple, incrémenter plusieurs fois un compteur et le déplacer d'une position le long de la bande). Y a-t-il une borne inférieure correspondante? $O(n\log n)$

J'ai essayé quelques recherches, mais des expressions comme «une tête» et «longueur d'entrée» sont si courantes qu'il est difficile de rechercher dans la littérature des résultats connus sur ce problème.

turing-machines David Eppstein
la source

Intéressant .. C'est moins évident qu'il n'y paraît. Je suis curieux de savoir s'il existe une relation entre une borne inférieure pour cela et une borne inférieure pour la simulation de MT inconsciente. (Toute MT résolvant ce problème serait, par définition, inconsciente (ou aurait un code inutile).)

Daniel Apon

Réponses:

Il ne peut pas être calculé au temps . $o(n\lg n)$

Soit une machine ayant donné une chaîne d'entrée s'arrête avec la taille de écrite en binaire sur la bande. $M$ $x$ $x$

Nous pouvons ajouter un DFA simple (temps linéaire à espace nul) à pour vérifier si la taille de l'entrée est une puissance de deux: vérifiez simplement que le premier bit est 1 et le reste est zéro. $M$

Supposons que exécute le temps . On peut alors décider dans le temps que la taille de l'entrée est une puissance de deux. En d'autres termes, le langage suivant est décidable en . Il résulte de $M$ $o(n \lg n)$ $o(n \lg n)$ $\mathsf{DTime}(n \lg n)$

L = {0^{i} ∣ \exists k i = 2^{k}}

$L = \{ 0^i \mid \exists k \ i = 2^k\}$

que

doit être régulier. Mais il est facile de vérifier que la langue n'est pas régulière. Donc

ne peut pas fonctionner au temps

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$

L

$L$

M

$M$

o (n \lg n)

$o(n \lg n)$

Kaveh
la source

Je manque quelque chose: Quand vous dites que

, envisagez - vous des calculs sur une machine mono-bande? Habituellement, je pense que les machines à deux bandes sont utilisées pour définir les classes de complexité. Une question très connexe est de savoir d'où vient le résultat ci-dessus?

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n\lg n))=\mathsf{Reg}$

Bruno

@Bruno, oui, je parle de machines de Turing à bande unique. Je ne sais pas quelle est la norme pour définir les classes de complexité, divers livres utilisent différents modèles. Les articles originaux de la théorie de la complexité utilisaient des bandes multiples, je pense, mais il semble que cela ait changé, voyez ceci . Pour

vous pouvez le trouver dans "The Classical Recursion Theory" vol. II et "Manuel de l'informatique théorique".

D T i m e (n \lg n) = R e g

$\mathsf{DTime}(n \lg n) = \mathsf{Reg}$

Kaveh

Merci pour les pointeurs, j'ai jeté un coup d'œil dans "The Classical Recursion Theory" vol. II. Pour le fait qu'il a changé, ce n'est pas si clair pour moi. Par exemple, le livre de Sipser utilise des MT à bande unique pour définir les classes de complexité temporelle, mais le livre de Hopcroft-Ullman et les plus récents d'Arora-Barak et Goldreich utilisent des TM à bandes multiples.

Bruno

@Bruno, je pense que la définition la plus courante de DTime est plus compliquée. Par exemple, l'affirmation communément affirmée que "le théorème de la hiérarchie temporelle n'est pas connu pour être serré" n'est vraie que pour les machines à bande unique, pour les machines à deux bandes, il est connu pour être serré depuis 1982.

Kaveh

D T i m e

$\mathsf{DTime}$