Quel type d'automate est le Turing Doodle de Google?

Pour célébrer l'anniversaire d'Alan Turing, Google a publié un doodle montrant une machine. Quel type de machine est le doodle? Peut-il exprimer une langue Turing Complete?

Il existe des différences évidentes avec la machine de turing classique: une bande finie, des contraintes dans la façon dont l'état peut être connecté, ...

Le doodle est toujours disponible ici

(L'affichage en haut à droite montre la sortie attendue.)

La bande au milieu est divisée en carrés pouvant contenir un blanc, un zéro ou un. La tête est positionnée au-dessus de l'un des carrés et est utilisée pour la lecture et l'écriture.

Sous la bande, vous pouvez voir une flèche verte sur laquelle vous pouvez cliquer pour démarrer la machine. Il y a deux lignes de cercles à côté, dont certaines sont connectées. Je les appellerai "états".

Après le démarrage de la machine, le premier état à droite du bouton vert s'allume, puis le suivant à droite, et ainsi de suite ... Chaque état contient l'une des commandes suivantes:

• vide = ne rien faire (passer simplement à l'état suivant)
• 1 = écrire un sur la bande à la position actuelle de la tête
• 0 = écrire un zéro sur la bande à la position actuelle de la tête
• flèche vers la gauche = déplacer la tête d'un pas vers la gauche
• flèche vers la droite = déplacer la tête d'un pas vers la droite
• condition: si la valeur sous la tête est égale à la valeur indiquée dans le carré, descendez à la deuxième ligne d'états. sinon, passez à l'état suivant vers la droite
• saut à gauche: revenir à un état précédent (fixe) mais uniquement sur la ligne supérieure [J'avais initialement oublié celui-là, merci @Marzio!]

Il n'y a aucun moyen de "superposer" deux sauts (l'un sur l'autre). La machine s'arrête lorsqu'elle quitte un état et il n'y a pas d'état suivant à sa droite.

(Après l'arrêt de la machine, le contenu de la bande est comparé au contenu de l'écran, mais je ne considère pas que cela fait partie des fonctionnalités prévues de la machine.)

En admettant que:

• nous pouvons ajouter un nombre arbitrairement élevé de lignes ("lignes d'état")
• les rangées peuvent être arbitrairement longues
• la bande est infinie

$M_4$

... donc même si le Doodle de l'AT n'est peut - être pas Turing complet (en raison de l'opérateur de saut gauche qui ne se chevauche pas uniquement disponible dans la première rangée), il est assez puissant pour parcourir la fine ligne de (non) décidabilité: - ré

EDIT: TURING DOODLE EST TURING COMPLET

(Je laisse la réponse précédente ci-dessus, car je ne suis pas sûr que cette partie soit correcte :-)

Je pense que même avec un seul saut gauche sans chevauchement, le Turing Doodle est Turing complet! . L'idée (simple) est d'utiliser la bande elle-même pour stocker l'état actuel et d'utiliser plusieurs cellules pour représenter un alphabet plus grand.

Par exemple, une MT à 2 états et 8 symboles peut être simulée en utilisant la représentation de bande suivante:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

Le doodle Turing peut:

1. $s$
2. $b2, b1, b0$
3. écrivez le symbole suivant, déplacez la tête vers la "macro-cellule" à gauche ou à droite et enregistrez-y l'état suivant; dans la figure ci-dessous, ces opérations (qui peuvent être effectuées sur une séquence de cellules en utilisant les actions se déplacer vers la gauche / droite et écrire) sont appelées "MW";
4. enfin, transférez le contrôle à la rangée supérieure qui, avec un seul saut à gauche, ramènera le contrôle à l'étape 1.

L'image complète est disponible ici .

$TM$$DM$

La machine est fournie avec une «bande» (l'analogue du papier) qui la traverse et divisée en sections (appelées «carrés») pouvant chacune porter un «symbole». À tout moment, il n'y a qu'un seul carré, disons le r-ème, portant le symbole S (r) qui est «dans la machine». Nous pouvons appeler ce carré le «carré scanné». Le symbole sur le carré scanné peut être appelé le «symbole scanné». Le «symbole scanné» est le seul dont la machine est, pour ainsi dire, «directement consciente». Cependant, en modifiant sa configuration m, la machine peut effectivement se souvenir de certains des symboles qu'elle a «vus» (scannés) précédemment. Le comportement possible de la machine à tout moment est déterminé par la configuration m qn et le symbole numérisé S (r). Cette paire qn, S (r) sera appelée la «configuration»: ainsi la configuration détermine le comportement possible de la machine. Dans certaines configurations dans lesquelles le carré numérisé est vierge (c'est-à-dire sans symbole), la machine écrit un nouveau symbole sur le carré numérisé: dans d'autres configurations, elle efface le symbole numérisé. La machine peut également modifier le carré en cours de numérisation, mais uniquement en le déplaçant d'un endroit vers la droite ou la gauche. En plus de n'importe laquelle de ces opérations, la configuration m peut être modifiée. Certains des symboles écrits {232} formeront la séquence de chiffres qui est la décimale du nombre réel qui est calculé. Les autres ne sont que des notes brutes pour «aider la mémoire». Ce ne seront que ces notes brutes qui seront susceptibles de s'effacer. ne porte aucun symbole), la machine écrit un nouveau symbole sur le carré numérisé: dans d'autres configurations, elle efface le symbole numérisé. La machine peut également modifier le carré en cours de numérisation, mais uniquement en le déplaçant d'un endroit vers la droite ou la gauche. En plus de n'importe laquelle de ces opérations, la configuration m peut être modifiée. Certains des symboles écrits {232} formeront la séquence de chiffres qui est la décimale du nombre réel qui est calculé. Les autres ne sont que des notes brutes pour «aider la mémoire». Ce ne seront que ces notes brutes qui seront susceptibles de s'effacer. ne porte aucun symbole), la machine écrit un nouveau symbole sur le carré numérisé: dans d'autres configurations, elle efface le symbole numérisé. La machine peut également modifier le carré en cours de numérisation, mais uniquement en le déplaçant d'un endroit vers la droite ou la gauche. En plus de n'importe laquelle de ces opérations, la configuration m peut être modifiée. Certains des symboles écrits {232} formeront la séquence de chiffres qui est la décimale du nombre réel qui est calculé. Les autres ne sont que des notes brutes pour «aider la mémoire». Ce ne seront que ces notes brutes qui seront susceptibles de s'effacer. Certains des symboles écrits {232} formeront la séquence de chiffres qui est la décimale du nombre réel qui est calculé. Les autres ne sont que des notes brutes pour «aider la mémoire». Ce ne seront que ces notes brutes qui seront susceptibles de s'effacer. Certains des symboles écrits {232} formeront la séquence de chiffres qui est la décimale du nombre réel qui est calculé. Les autres ne sont que des notes brutes pour «aider la mémoire». Ce ne seront que ces notes brutes qui seront susceptibles de s'effacer.

Je pense que ces opérations incluent toutes celles qui sont utilisées dans le calcul d'un nombre. La défense de cette affirmation sera plus facile lorsque la théorie des machines sera familière au lecteur. Dans la section suivante, je procède donc au développement de la théorie et suppose que l'on comprend ce que l'on entend par «machine», «bande», «numérisé», etc.

Ceci est un extrait de l'article original de Turing "Sur les nombres calculables, avec une application au problème Entscheidungs".

Un bon compagnon moderne pour le papier que je recommande est The Annotated Turing de Charles Petzold.

Comme vous pouvez le voir, Google a juste essayé de ressembler à une machine qui est très similaire à la description de Turing.

EDIT: en supposant que l'alphabet complet de Google TM est celui affiché à la fin du jeu après avoir cliqué sur l' icône du lapin , et en tenant compte du fait qu'il produit une séquence infinie , a obtenu plus de lignes et de colonnes (nous pouvons donc supposer que nous pouvons ajouter n'importe quel ), a des sauts à gauche (et aussi des sauts à gauche qui se chevauchent ) à n'importe quelle ligne , a un saut conditionnel et inconditionnel entre les rangées adjacentes, je pense que c'est Turing complet .

Dans les puzzles, les sauts sont autorisés sur les deux lignes, mais ils ne peuvent pas se chevaucher. Au dernier doodle de séquence de lapin à la fin du jeu, ils autorisent les sauts sur chaque ligne et ils peuvent être imbriqués entre parenthèses et [()] est autorisé, mais ([)] ne semble pas être autorisé.

J'utiliserai les hypothèses suivantes:

1. $0$$1$$\epsilon$
2. La machine peut utiliser n'importe quel nombre fixe de lignes
3. Les sauts à gauche sont autorisés sur n'importe quelle ligne (j'utiliserai un saut à gauche par ligne)
4. $\epsilon$$0$$1$

Avec ces hypothèses, la machine Google Doodle est terminée .

$0$$1$$\epsilon$$0$$1$$n$

$3(n - 1) + 1$$5n + 1$

$\epsilon$$0$$1$$\epsilon$$0$$1$$0$$1$

Le GDM simule le TM comme suit:

1. $1$
2. $j$
3. $\epsilon$$0$$1$
4. $\epsilon$
5. $0$$1$
6. $0$$1$

Choisissez votre TM universel préféré et implémentez-le dans la procédure ci-dessus pour obtenir un GDM universel.