Alphabet de Turing à une seule bande

Toute fonction calculable en temps sur une machine de Turing à bande unique utilisant un alphabet de taille peut-elle être calculée en temps sur une seule bande machine de Turing en utilisant un alphabet de taille ( par exemple, et en blanc)? $f : \{0,1\}^* \to \{0,1\}$ $t$ $k = O(1)$ $O(t)$ $3$ $0,1,$

(D'après les commentaires ci-dessous de l'OP) Remarquez que l'entrée est écrite en utilisant , mais la machine de Turing en utilisant un alphabet de taille peut écraser les symboles en entrée avec des symboles du plus grand alphabet. Je ne vois pas comment encoder des symboles dans un alphabet plus grand dans un alphabet plus petit sans avoir à décaler l'entrée, ce qui coûterait le temps . $0,1$ $k$ $n^2$

computability turing-machines Manu
la source

Notez que l'entrée est écrite en utilisant

, mais la machine de Turing en utilisant un alphabet de taille

peut remplacer les symboles en entrée par des symboles du plus grand alphabet. Je ne vois pas comment encoder des symboles dans un alphabet plus grand dans un alphabet plus petit sans avoir à décaler l'entrée, ce qui coûterait le temps

0, 1

$0,1$

k

$k$

n^{2}

$n^2$

Manu

@ Emmanuel: Vous devriez éditer la question et mettre l'accent sur cet aspect; Sinon, cela ressemble exactement à un exercice classique ...

Jukka Suomela

@Tsuyoshi, je pense que vous avez mal compris la question.

Suresh Venkat

@Jukka: Sur une machine de Turing à bande unique, tout ce qui peut être calculé en temps

est en fait un langage courant .

o (n \log n)

$o(n \log n)$

Kristoffer Arnsfelt Hansen

@Abel: Le résultat que vous citez d'Arora et Barak résout le problème principal car, dans leur modèle (qui est assez standard pour les MT multi-bandes), ils ont une bande d'entrée distincte en lecture seule.

Joshua Grochow

Réponses:

Une réponse partielle si TM s'exécute en $o( |x| \log |x|)$

Si TM4 est un TM 4-symboles (avec l' alphabet ) qui calcule , ie décide langue dans $\Sigma_4 = \{\epsilon,0,1,2 \}$ $f:\{0,1\}^* \to \{0,1\}$ $L = \{ x | f(x) = 1 \}$ $(o( |x| \log |x|))$

Une complexité déterministe dans le temps linéaire est $1DLIN = 1DTime(O(n))$

Hennie a prouvé (1) que $REG = 1DLIN$
Kobayashi a prouvé (2) que $REG = 1DTime(o(n \log n))$

Alors est régulière, et est évidemment encore alphabet régulier sur $L$ $\Sigma_3 = \{\epsilon,0,1\}$

Donc , il y a un DFA qui décident L et utilise uniquement des symboles dans . Un TM3 à une seule bande et à trois symboles peut être construit directement à partir du DFA et il décide L en utilisant la même entrée non rembourrée du TM4 d'origine . $\Sigma_3$

... vous ne pouvez pas le construire directement à partir de TM4, mais TM3 existe.

Si TM4 s'exécute en vous pouvez alors décaler l'entrée et effectuer une conversion directe de TM4 en TM3. $\Omega(n^2)$

Comme noté dans les commentaires le cas difficile est quand TM4 fonctionne dans . $\Omega(n\log n) \cap o(n^2)$

(1) Hennie, Calculs sur une machine de Turing hors ligne (1965).

(2) Kobayashi, Sur la structure de la hiérarchie temporelle de la machine de Turing non déterministe (1985).

Marzio De Biasi
la source

Le point à propos de

est déjà mentionné par Kristoffer Arnsfelt Hansen dans les commentaires sous la question. Le cas est vraiment intéressant

o (n \log n)

$o(n\log n)$

Ω (n \log n) \cap o (n^{2})

$\Omega(n\log n) \cap o(n^2)$

Kaveh

Vous avez raison, je n'ai pas remarqué le commentaire de Kristoffer. J'ai mal exprimé le cas intéressant (je ne sais pas comment le prouver), alors j'ai mis à jour la réponse.

Marzio De Biasi

@Kaveh: Qu'en est-il des machines

heure des problèmes de promesse? Est - ce que nous savons déjà comment convertir, par exemple, une machine qui permet de résoudre un problème de promesse en

temps? Je ne vois pas comment faire, et la connexion aux langages normaux ne tient plus (à moins que je me trompe gravement).

o (n \log n)

$o(n \log n)$

O (n)

$O(n)$

Jukka Suomela

@Kaveh: Ne pouvez-vous pas simplement prendre un problème

qui n'est pas un langage courant mais qui peut être résolu avec une machine de Turing dans, par exemple,

tours, et définir un problème de promesse comme suit: yes-instances consistent en une chaîne

suivie de

bits de rembourrage; aucune instance n'est constituée d'une chaîne

suivie de

bits de rembourrage. Le problème de la promesse est résoluble dans

L

$L$

O (n^{2})

$O(n^2)$

x \in L

$x \in L$

| x |^{2}

$|x|^2$

x \notin L

$x \notin L$

| x |^{2}

$|x|^2$

O (n)

$O(n)$ temps, et il est impossible de résoudre en utilisant une machine à états finis.

Jukka Suomela

@Kaveh: Je suppose que l'argument intuitif échoue pour la raison suivante: Oui, il existe un problème non prometteur résolu par la même machine. Cependant, le temps de fonctionnement de la machine peut atteindre

pour certaines entrées. (Intuitivement, la machine ne peut pas vérifier qu'il ya suffisamment de rembourrage, et donc « jouer en toute sécurité » , il faut supposer qu'il y ait suffisamment de rembourrage après le préfixe

Ensuite , il gaspille.

le temps de déterminer si

, ce qui est trop si, par exemple, nous avions seulement

Θ (n^{2})

$\Theta(n^2)$

x

$x$

Θ (| x |^{2})

$\Theta(|x|^2)$

x \in L

$x \in L$

Θ (| x |)

$\Theta(|x|)$ des morceaux de rembourrage.)

Jukka Suomela

-4

~~Pour tout alphabet tailles supérieures à , runtimes seul changement par un facteur constant depuis pour tout . $1$ $\log_k(x) \in \Theta(\log_l(x))$ $k, l > 1$~~

~~Elaboration:~~ En pas de temps, la machine de Turing supposé peut traiter à la plupart des positions / bits. Les bits proviennent d'un alphabet nary, wlog . Créer une nouvelle machine de Turing en remplaçant chaque transition par transitions; chaque ancien bit est codé par bits dans $t$ $t$ $k$ $\{0,1,\dots,k-1\}$ $\lceil \log_2(k) \rceil$ $\lceil \log_2(k) \rceil$ $\{0,1\}$ (des blancs sont réservés pour marquer les cellules inutilisées). Notez qu'il s'agit essentiellement de chiffres codés binaires.

De toute évidence, la machine de Turing résultant exécute au plus étapes. $\lceil \log_2(k) \rceil \cdot t \in \mathcal{O}(t)$

Addition: les arguments d'argumentation ci-dessus sont interrompus, car les opérations qui écrasent un symbole d'entrée avec un bit ne figurant pas dans ne peuvent pas être traduites directement; l'entrée doit être décalée. Cela peut être modifié en traduisant l'entrée d'origine avant de commencer le calcul (essentiellement du remplissage); cela peut être fait en temps , ce qui entraîne un temps d' exécution total de . $\{0,1\}$ $\mathcal{O}(n^2)$ $\mathcal{O}(n^2) + \lceil \log_2(k) \rceil \cdot t$

Par conséquent, en utilisant seulement deux symboles pour l' encodage des résultats intermédiaires est sans impact asymptotique si , mais plus rapide des algorithmes de pré - traitement domine. Comme les fonctions les plus intéressantes sont en (par exemple, en ajoutant deux nombres), on peut considérer le problème négligeable. $t(n) \in \Omega(n^2)$ $\Omega(n^2)$

Raphaël
la source

Tant que vous ne me convaincrez pas que cela est censé être le cas, je garderai cette voix.

Andrej Bauer

J'aimerais entendre des preuves de votre demande. Tout cela, ce n’est qu’une revendication.

Andrej Bauer

Oh, je vois de quoi tu parles. D'accord désolé. Cependant, la question n'est pas à ce sujet . C'est une légère variation.

Andrej Bauer

Je pense que le cas avec t = Ω (n ^ 2) est le cas facile car vous pouvez vous permettre le temps nécessaire pour décaler la chaîne d'entrée. Le cas essentiel est lorsque t = o (n ^ 2). Je ne sais pas à quel point il est important d’envisager une MT sur une seule bande avec un temps de jeu (n ^ 2), mais la question est de savoir à quoi.

Tsuyoshi Ito

La question initiale implique déjà que le cas

est facile; par conséquent, je ne vois pas vraiment en quoi cette réponse ajoute quelque chose de nouveau ...

Ω (n^{2})

$\Omega(n^2)$

Jukka Suomela