L'entrée dans une machine de Turing peut-elle être de longueur infinie?

En considérant uniquement l'alphabet , les chaînes qui peuvent être données en entrée aux machines de Turing proviennent de l'ensemble . Mais est-il logique que l'entrée soit une chaîne binaire infinie? Par exemple, si une machine Turing accepte toutes les chaînes commençant par un 0, une chaîne binaire de zéros infinis appartient-elle également au langage accepté par la machine Turing?$\Sigma = \{0,1\}$$\Sigma^{*}$

L'exécution d'une machine Turing sur une bande initialisée avec une chaîne infinie ne pose aucun problème, bien que cela ne soit généralement pas pris en compte. Cependant, nous avons toujours besoin que la machine se termine en temps fini. Il existe également des notions de calcul en temps infini, qui peuvent être appropriées ici.

C'est l'une des caractéristiques des machines de Turing de type 2 . Ils sont utilisés, entre autres, pour analyser la calculabilité des fonctions entre des nombres réels. Encore plus intéressant, ils sont utilisés pour analyser la calculabilité des opérateurs comme l'intégration.

Fait intéressant: l'intégration numérique exacte est calculable.

Pour répondre à la question "est-ce que cela a du sens", cela peut même être utile si vous envisagez des machines Turing qui fonctionnent en temps limité.

Plus précisément, c'est une façon très utile de penser aux machines de Turing sans préfixe . Ce sont des machines dont le jeu d'entrées d'arrêt est sans préfixe; c'est-à-dire qu'aucune entrée qui provoque l'arrêt de la machine n'est le préfixe d'une autre. Celles-ci sont équivalentes en puissance aux machines Turing ordinaires, mais seulement si nous permettons à la machine Turing de décider de ses propres entrées d'arrêt: ie. l'utilisateur n'a aucune idée sur quelles entrées la machine va s'arrêter (et c'est une propriété indécidable).

Une façon de voir cela est comme une machine de Turing ordinaire avec une bande d'entrée infinie unidirectionnelle avec une tête de bande qui ne peut pas reculer. L'utilisateur remplit la bande de bits et exécute la machine. Il s'agit par définition d'une machine de Turing sans préfixe. Si la machine s'arrête, elle n'a dû lire qu'un nombre fini de bits, et aucun préfixe de cette partie de la bande ne peut être un programme, sinon la machine s'y serait arrêtée.

C'est un bon moyen de parler des distributions de probabilité calculables: l'utilisateur remplit la bande de bits aléatoires (la source de hasard de la machine) et la machine crache une chaîne de bits aléatoire. L'ensemble de toutes ces machines de Turing correspond à l'ensemble des distributions calculables (en particulier les semi-mesures semi-calculables inférieures).

L'avantage de l'entrée infinie est que nous n'avons pas à spécifier ce que fait la machine si nous lui donnons le préfixe d'un programme d'arrêt, c'est-à-dire. la machine essaie de lire au-delà de la fin de l'entrée que nous lui avons donnée.

Même si vous ne disposez pas d'une telle bande, vous pouvez utiliser une autre machine Turing pour la produire.

Une machine Turing a accès à la bande de données vide mais infinie (ou certaines sources disent que "la machine a juste une petite fabrique de bandes intégrée"). Il peut donc l'initialiser avec un modèle de données programmable, puis la bande peut être consommée comme entrée d'une autre machine Turing.

Bien sûr, si votre contenu est tel qu'aucun algorithme n'a pu être défini pour le produire, ce contenu ne peut pas être créé par la machine Turing.

Dans certains cas, une entrée infinie peut être envisagée et réduite à l'action d'une machine de Turing "standard". Par exemple, considérons un motif fini à répétition infinie spécifié sur l'entrée. Une machine de Turing peut être créée pour garder une trace de la quantité de ce motif infini qui a été modifiée par les actions actuelles de la tête de bande en utilisant une quantité limitée de mémoire / stockage de bande. En d'autres termes, il "simule de manière équivalente" un motif de taille infinie sur la bande.

Un autre cas où une «entrée infinie» a été envisagée est l'analyse de l' équivalence / exhaustivité de Turing des automates cellulaires. dans une preuve complexe, Cook a introduit un concept désormais appelé par certains «équivalence de Turing faible» dans la conversion des opérations de règles CA 110 en opérations de machine de Turing qui démarrent sur une bande initiale spécifiée à l'infini mais avec des motifs de taille finie (répétitifs).

Dans les langages formels, une chaîne est, par définition, une séquence finie de symboles. Une machine de Turing classique a une bande infinie avec une chaîne d'entrée finie. En tant que tel, bien qu'il n'y ait pas de limite à la durée de l'entrée, elle ne peut pas être infinie.

Cela dit, il existe de nombreuses machines alternatives qui fonctionnent de manière similaire à une MT mais avec des séquences d'entrée infinies.

La pertinence d'une entrée de longueur infinie dépend de l'objectif. Strictement dans le contexte des machines de Turing, cela n'a aucun sens (car ce n'est pas possible), mais dans le contexte des machines de type Turing, cela a du sens et il a de nombreuses applications.