Pourquoi le symbole vide n'est-il pas considéré comme faisant partie de l'alphabet d'entrée d'une machine de Turing?

Les définitions des machines de Turing indiquent toujours explicitement que le symbole vide ne fait pas partie de l'alphabet saisi.

Je me demande ce qui ne va pas quand vous le ferez partie de l'alphabet d'entrée, car effectivement le symbole vide semble déjà faire partie de l'entrée.

Pour expliquer que «semble» dans la dernière phrase, considérez ce qui suit.

Dans la configuration par défaut, un nombre infini de symboles vierges apparaissent à droite de l'entrée. Lorsque la tête de bande se déplace sur le premier symbole vierge, le calcul peut simplement continuer, car il n'a pas besoin d'être un état d'acceptation ou de rejet.

Supposons maintenant que le calcul écrive ensuite les symboles de l'alphabet d'entrée à droite de ce premier symbole vierge, puis revient à la position la plus à gauche tout en revenant à l'état de départ. Il recommencerait alors avec une bande différente. Effectivement, cela commence maintenant par une entrée différente, où il y a des symboles d'entrée à droite du blanc qui n'étaient pas là auparavant. L'entrée semble inclure efficacement le symbole vierge. Le comportement ultérieur de la machine pourrait également être différent: après avoir rencontré à nouveau le flan, il rencontrera maintenant différents symboles à droite.

En supposant que ce scénario soit en effet possible, pourquoi ne considéreriez-vous pas la partie symbole vierge de l'alphabet d'entrée et pourquoi ne permettriez-vous pas de l'inclure comme partie de l'entrée «initiale»?

C'est peut-être juste un moyen de définir l'entrée de telle sorte qu'elle ne soit pas toujours infinie?

turing-machines Confusion
la source

Quand j'étais en classe, j'ai conçu des machines de Turing qui utilisaient la possibilité d'utiliser β (le symbole vierge local) dans leur entrée comme séparateurs de champ.

Joshua

Réponses:

La raison principale est qu'il permet à la machine de détecter la fin de son entrée: c'est (le caractère avant) le premier blanc. Si vous avez autorisé des blancs dans l'entrée, la machine ne pourrait jamais savoir si elle pourrait trouver plus d'entrée en balayant plus à droite. Bien sûr, vous pouvez résoudre ce problème en ayant un caractère spécial "fin d'entrée", mais vous devez alors insister sur le fait que cela ne peut pas apparaître dans l'entrée, de sorte que vous venez de déplacer le problème d'un niveau plus profond.

Cela rend également les conditions initiales beaucoup plus faciles à spécifier: l'entrée est la section non vierge de la bande initiale, qui doit être finie et contiguë. Et si vous voulez qu'un caractère vide fasse partie de l'alphabet saisi, vous pouvez toujours ajouter un caractère supplémentaire (appelez-le "espace" ou quelque chose) et faire en sorte que la machine se comporte comme vous le souhaitez lorsqu'elle le voit.

David Richerby
la source

Ah, bien sûr, sans pouvoir déterminer la fin de l'entrée initiale, certains calculs seraient impossibles. Mais sinon, le symbole n'a rien de spécial. Et je suppose que c'est une question d'économie terminologique d'utiliser le symbole vide, car vous en avez besoin de toute façon dans votre alphabet. Je pense que cela aurait été plus évident pour moi lors de la définition initiale avec un symbole de fin d'entrée explicite et une remarque qu'il n'était pas strictement nécessaire et souvent omis.

Confusion

Il existe des encodages d'entrée simples qui ne nécessitent pas de symbole supplémentaire. Par exemple, on peut simuler un alphabet à quatre caractères en considérant des paires de caractères 00, 01, 10 et 11, puis (par exemple) désigner un décodage . Mais cela simplifie considérablement les choses pour permettre à un troisième personnage, et cela ne produit aucun réel inconvénient.

{00} \to 0, {11} \to 1, {10, 01} \to b

$\{00\} \rightarrow 0, \{11\} \rightarrow 1, \{10, 01\} \rightarrow b$

Yonatan N

Étant donné que la machine Turing a besoin de règles qui régissent ce qu'elle fait si elle lit un blanc, et qu'elle peut avoir une règle qui lui dit d'écrire un blanc, cela ne signifie-t-il pas que le blanc fait effectivement partie de son alphabet? Je ne vois pas pourquoi l'entrée peut ne pas contenir de blancs. Que diriez-vous d'encoder des éléments d'entrée en utilisant les caractères non vides et un seul blanc comme séparateur? Ensuite, plusieurs blancs consécutifs indiquent la fin de l'entrée.

Rosie F

@YonatanN Bien sûr. C'est "simple" mais avoir un symbole vide est plus simple.

David Richerby

@RosieF Le blanc fait partie de l'alphabet de la bande; l'alphabet d'entrée est un sous-ensemble de cela. Et, bien sûr, vous pouvez définir des conventions sur la façon dont l'entrée peut contenir des blancs dans certaines circonstances (comme vous l'avez fait), mais cela rend les définitions plus complexes. Des définitions plus complexes signifient qu'il est plus difficile de prouver des choses sur les machines Turing. Et, puisque les machines Turing ne sont vraiment utilisées que pour prouver des choses (si vous voulez concevoir un ordinateur réel, ce ne sera pas une MT), ce n'est pas un bon compromis.

David Richerby

Vous pouvez définir le symbole vierge pour faire partie de l'alphabet. Le problème est que si une machine de Turing avec l'entrée b010010b (où b signifie blanc ) ne lit jamais au-delà du deuxième b, alors la machine se comportera exactement de la même manière sur toutes les entrées commençant par b010010b.

Ces machines de Turing sont appelées machines de Turing de préfixe , et elles sont très utiles pour prouver certains théorèmes sur la complexité de Kolmogorov.

Peter Shor
la source

Réponse très courte: l' alphabet de la bande est l'ensemble des symboles qui peuvent apparaître sur la bande, et il comprend le symbole vierge. L' alphabet d'entrée est l'ensemble des symboles qui peuvent apparaître dans l'entrée initiale , et il n'inclut pas le symbole vide. L'alphabet principal auquel la machine tient est l'alphabet sur bande: elle a encore besoin de règles pour savoir quoi faire lorsqu'elle voit un blanc, par exemple.

Cette distinction est importante, comme d'autres l'ont dit, pour que la machine puisse dire où se termine son entrée. C'est la même raison pour laquelle vous ne pouvez pas (utilement) mettre un caractère zéro au milieu d'une chaîne en C: le caractère zéro est réservé pour signifier "le dernier caractère non nul avant que ce ne soit la fin des données, donc quand vous voyez cela, vous avez terminé ". Si vous devez vous attendre à zéro caractère au milieu de la chaîne, l'écriture strlendevient beaucoup plus difficile.

Draconis
la source