Machine à ruban semi-infinie

Une machine de Turing avec une bande semi-infinie a une extrémité gauche mais pas d'extrémité droite. L'extrémité gauche est limitée par un marqueur de fin.

C'est une cassette à deux pistes -

  • Upper track - Il représente les cellules à droite de la position initiale de la tête.

  • Lower track - Il représente les cellules à gauche de la position initiale de la tête dans l'ordre inverse.

La chaîne d'entrée de longueur infinie est initialement écrite sur la bande dans des cellules de bande contiguës.

La machine démarre à partir de l'état initial q0et la tête scanne à partir du marqueur d'extrémité gauche «Fin». À chaque étape, il lit le symbole sur la bande sous sa tête. Il écrit un nouveau symbole sur cette cellule de bande, puis déplace la tête dans une cellule de bande gauche ou droite. Une fonction de transition détermine les actions à entreprendre.

Il a deux états spéciaux appelés accept state et reject state. Si à tout moment il entre dans l'état accepté, l'entrée est acceptée et si elle entre dans l'état de rejet, l'entrée est rejetée par le TM. Dans certains cas, il continue de fonctionner indéfiniment sans être accepté ou rejeté pour certains symboles d'entrée.

Note - Les machines de Turing avec bande semi-infinie sont équivalentes aux machines de Turing standard.