Espace limité Machine de Turing - la clarification de la complexité informatique (livre: Arora-Barak) question 4.1

Question

J'ai la question suivante à partir Complexité - Une approche moderne par Sanjeev Arora et Boaz Barak:

  

[Q 4.1]   Prouver l'existence d'un espace TM universel pour le calcul borné (analogue à la TM universelle déterministe du théorème 1.9).

C'est, prouve qu'il existe une machine de Turing $ SU $ tel que pour chaque chaîne $ \ alpha $ et entrée $ x $, si le TM $ M_ \ alpha $ - le TM représenté par $ \ alpha $ - - arrêts sur $ x $ avant d'utiliser $ t des cellules de dollars de sa bande de travail, puis $ SU (\ alpha, t, x) = M_ \ alpha (x) $ et de plus, les utilisations $ SU $ au plus $ C \ cdot t $ cellules de la bande de travail, où $ $ C est une constante ne dépendant que de $ M_ \ alpha $.

Après avoir vérifié le théorème 1.9 et la TM avec le temps universel lié, je vois que la construction $ SU (\ alpha, t, x) $ signifie que la machine de Turing SU arrête après $ t $ étapes. Toutefois, si tel est le cas, cela signifie que nous pouvons créer une machine de Turing équivalent à $ M_ \ alpha $ de telle sorte que la nouvelle Turing arrête la machine à $ t pas de $ où $ t $ est l ' « espace » utilisé dans l'original.

Cependant, cela semble un échange douteux d'espace et le temps. Si d'autre part, $ t $ signifie en réalité que la deuxième machine arrête à $ t espace $ aussi, la deuxième partie n'a pas de sens plus car il dit utilise $ SU $ cellules $ Ct $, ce qui est $ t $.

Alors, ma question est de savoir comment puis-je interpréter cela? La première interprétation vraiment possible?

Answer 1

Je ne comprends pas ce que vous essayez de dire après « - », mais voici ce que vous devez faire:

Si tout va bien vous comprenez l'idée de turing le codage de la machine: à savoir que vous pouvez attribuer un identifiant unique (à savoir "label") $ \ alpha $ à chaque machine de Turing. Donc, par M_ $ \ alpha $, on entend la machine de Turing marquée par $ \ alpha $. Vous avez donc besoin de concevoir un à machine de Turing $ SU $ qui prend trois entrées $ \ alpha $, $ t $ et $ x $ ($ \ alpha $ est une étiquette de la machine turation, $ t $ est un espace lié, et $ x $ est une chaîne d'entrée) et:

• si $ M_ \ alpha utilisations $ plus de $ t bits $ de l'espace de travail sur $ d'entrée x $ avant qu'il arrête, alors nous avons pas besoin de $ SU $

• si $ M_ \ alpha Utilisations de $ au plus $ t $ bits d'espace de travail sur $ d'entrée x $, nous avons deux exigences pour $ SU $:

  • SU utilisations $ $ chez la plupart des unités Ct $ $ de l'espace de travail où $ C $ est une fonction de $ \ alpha $, mais pas $ t $ ou $ x $
  • M_ de $ SU $ $ \ alpha (x) $

L'idée est que pour toute machine et toute entrée, $ SU $ peut simuler cette machine tout en utilisant seulement un peu plus d'espace que la machine d'origine. Notez que $ t $ est une limite sur l'espace que $ M_ \ alpha Utilisations de $, pas l'espace que les utilisations $ SU $. $ SU $ ne peut pas être exactement comme espace efficace que la machine d'origine, car la simulation nécessite certains frais généraux, mais le point est que les frais généraux est faible en $ C $ est fixé pour chaque $ \ alpha $, peu importe la taille $ x $ est en la taille.

Le théorème 1.9. a aussi une surcharge: une machine qui arrête pas de temps $ T $ est simulé en $ CT \ Log pas de temps T où $ $ $ C est encore un peu indépendant de constante de $ T $ ou de la chaîne d'entrée.