Il a été prouvé que le problème de décider si une entrée est un palindrome ou non nécessite un espace sur une machine de Turing. Cependant, même le stockage de l'entrée prend de l'espace cela ne signifie-t-il pas que toutes les machines Turing nécessitent de l'espace ?
Bien sûr, il n'y a pas de contradiction ici, car toute fonction qui utilise au moins l'espace linéaire utilise également au moins l'espace logarithmique. Mais écrire suggère qu'il est possible pour une machine Turing d'utiliser moins d'espace linéaire - après tout, pourquoi les gens passeraient-ils tout ce temps à prouver si c'était exactement la même chose ce qui semble être un trivial lié? Alors, qu'est-ce que cela signifie pour une machine Turing d'utiliser moins d'espace linéaire?
Réponses:
Pour les espaces restreints, nous utilisons le modèle suivant. La machine Turing a trois bandes: une bande d'entrée en lecture seule, une bande de travail en lecture-écriture et une bande de sortie en écriture seule. Nous mesurons uniquement la consommation d'espace sur la bande de travail. Pour les palindromes, avec l'espace sur la bande de travail, nous pouvons implémenter des boucles FOR qui vont sur l'entrée, en comparant les caractères correspondants aux deux extrémités. Chaque index prend de l' espace pour être stocké.O ( logn ) O ( logn )
la source