Les tuiles Wang (dominos) ont été inventées par Hao Wang en 1961 pour des problèmes mathématiques, mais ont été largement utilisées dans les jeux pour créer des graphiques de tuiles. Grâce à eux, les résultats ne semblent pas répétitifs, tant dans les textures 2D que dans les modèles 3D avec carrelage.
Il semble que les tuiles de Van soient également capables d'exécuter des machines Turing, et donc, elles sont complètes de Turing, ce qui signifie qu'elles peuvent exécuter n'importe quel programme.
C'est une déclaration incroyable et incompréhensible, donc dans ce post, j'examinerai un peu ce problème.
En bref sur Van Tiles
Les tuiles Van sont des tuiles rectangulaires dans lesquelles chacune des faces ne peut correspondre qu'à d'autres faces spécifiques, mais pour toute face particulière, il existe plusieurs tuiles possibles qui peuvent correspondre à cette face. En faisant correspondre les visages, je veux dire qu'ils se connectent de manière transparente sans créer d'artefacts visuels ou de signes d'une couture entre les carreaux.
Cette propriété est utile pour les graphiques, car elle vous permet de créer des graphiques de tuiles sans couture, mais la configuration de l'emplacement des tuiles peut être complètement aléatoire, à condition que toutes les faces soient compatibles les unes avec les autres. Le résultat est des graphiques en mosaïque, qui ne ressemblent pas du tout à ceux qui se répètent, car les motifs visuels deviennent beaucoup moins visibles que les graphiques en mosaïque traditionnels.
Des exemples graphiques, des informations plus détaillées et des liens vers Shadertoy peuvent être trouvés ici:
Wang Tiling .
Voici un exemple que j'ai créé. Mes graphismes sont des «programmeurs artistiques», mais j'espère que l'idée est claire. Le dessin est composé de 16 tuiles, et pour chaque face, il existe deux types de faces différents.
En bref sur les machines de Turing
Les machines de Turing ont été inventées en 1936 par Alan Turing comme un ordinateur généralisé, pour lequel il a été prouvé qu'il peut exécuter n'importe quel algorithme.
La machine de Turing est composée de plusieurs composants principaux: bandes de mémoire, têtes de lecture / écriture et machines d'état.
La bande mémoire a une longueur infinie, c'est-à-dire qu'elle a une capacité de stockage infinie et, au début, elle est initialisée avec des zéros uniquement.
La tête de lecture / écriture commence à partir d'une certaine position de la bande et peut lire / écrire des valeurs, et également se déplacer à gauche et à droite le long de la bande.
La machine d'état contrôle la tête de lecture / écriture.
La machine d'état sait dans quel état elle se trouve et a des règles sur ce qu'il faut faire dans chaque état lorsqu'elle lit une valeur sur la bande.
Par exemple, dans l'état A, si 0 est lu sur la bande, la règle peut être d'écrire 1 à la position actuelle de la bande, de déplacer la tête de lecture / écriture vers la droite ou de passer à l'état B.L'État B peut avoir une logique complètement différente et peut soit effectuer la transition revenir à l'état A, ou rester dans l'état B, ou passer à un état complètement différent.
En utilisant une logique de transition entre les états aussi simple, tout algorithme informatique peut être exécuté.
La machine de Turing peut également avoir un «état d'arrêt», ce qui signifie que le programme a terminé son exécution et que la réponse a été calculée.
Vous cherchez des programmes. peut être facilement vu. qu'au fil du temps, ils finiront ou seront dans une boucle infinie et ne s'arrêteront jamais. Certains programmes sont situés entre eux, ils sont complexes et il n'est pas si facile de déterminer s'ils s'arrêteront jamais. Turing a prouvé qu'il n'y a pas de solution générale pour déterminer si la machine Turing s'arrêtera (c'est un programme informatique), et c'est ce qu'on appelle
le problème d'arrêt . En général, la seule façon de savoir si un programme s'arrête est d'attendre. En fait, dans le cas général, les réponses à cette question sont «oui» ou «pas encore», cependant, dans le cas de nombreux programmes spécifiques, vous pouvez voir qu’après leur lancement, ils prendront fin avec le temps.
Calculs de tuiles Wang
Il s'avère que les tuiles Wang peuvent simuler une machine de Turing, c'est-à-dire qu'elles sont complètes de Turing, ce qui signifie qu'elles peuvent exécuter n'importe quel algorithme informatique.
Pour réaliser cela, nous avons besoin d'une colonne de tuiles Van qui indique l'état de la machine de Turing à un moment donné, en commençant au temps 0 dans la colonne la plus à gauche. Nous allons mettre des tuiles dans la colonne de droite avec toutes les règles des visages, puis créer une colonne à droite de celle-ci, et ainsi de suite, jusqu'à ce que le programme se termine (ou nous le ferons pour toujours s'il ne se termine pas). Si vous sélectionnez le bon jeu de tuiles, il vous suffira de vérifier la conformité aux règles des faces dans le processus de disposition des tuiles pour terminer la machine de Turing.
Regardons un exemple simple qui a les règles de logique de la machine à états suivantes:
- Lorsque la machine est dans l'état A, alors dans le cas de la lecture de 0, nous écrivons 1, déplaçons la tête de lecture / écriture vers le bas et passons à l'état B.
- Lorsque la machine est dans l'état A, dans le cas de la lecture 1, le programme s'arrête (passe à l'état final).
- Lorsque la machine est dans l'état B, dans le cas de la lecture de 0, nous écrivons 1, déplaçons la tête de lecture-écriture et passons à l'état A.
- Lorsque la machine est à l'état B, dans le cas de la lecture 1, le programme s'arrête (passe à l'état final)
Lecteur de bande
Tout d'abord, nous avons besoin d'un stockage permanent pour la bande. Pour ce faire, nous avons besoin des deux tuiles suivantes:
Pour tester leur travail, nous pouvons préparer un segment de la bande avec quelques valeurs (créer une colonne de tuiles Van) et nous assurer que les seules tuiles Van appropriées situées à côté de la colonne initiale sont des tuiles qui transfèrent les valeurs 0 et 1 dans le temps sans changer eux.
Dans le diagramme ci-dessous, nous initialisons la bande avec la valeur 0101 dans la colonne la plus à gauche (temps 0). N'ayant que des tuiles avec des faces compatibles, nous voyons que les valeurs en mémoire sont stockées pour toujours. Nous avons implémenté un lecteur de mémoire!
Nous allons commencer à montrer notre exemple avec une mémoire initialisée à 0, et la figure ci-dessus montre simplement la persistance de la mémoire.
Machine d'état de tête de lecture-écriture
La tête de lecture / écriture d'une machine de Turing est présentée comme faisant partie des informations sur le visage. Ainsi, en plus du visage stockant 0 ou 1, si la tête de lecture / écriture s'y trouve, elle stocke également l'état de la machine d'état.
Dans notre exemple, deux états sont utilisés (sans inclure l'état final): A et B. Si 1 est lu, alors dans l'un des états (A ou B) le programme se termine.
Pour gérer cela, nous avons besoin des tuiles suivantes:
Maintenant que nous avons les règles de transition vers l'état final (règles 2 et 4), nous devons comprendre comment mettre en œuvre les règles qui contrôlent le passage d'un état à un autre (règles 1 et 3).
Déplacement de la tête de lecture / écriture
La règle 1 stipule que si nous sommes dans l'état A et lisons 0, nous devons écrire 1, déplacer la tête de lecture / écriture vers le bas et passer à l'état B.
Nous avons besoin de cette tuile pour lire 0 dans l'état A, pour écrire 1 comme sortie, et commander la tuile ci-dessous pour entrer dans l'état B.
La tuile en dessous de la tuile actuelle peut avoir une valeur de 0 ou 1; sans connaître une valeur spécifique, nous devons la sauvegarder, mais accepter la tête de lecture / écriture et être dans l'état B. Pour cela, nous avons besoin de deux tuiles - une pour 0 sur la bande dans cette position, l'autre pour 1 sur la bande.
La règle 3 stipule que si nous sommes dans l'état B et lisons 0, nous devons écrire 1, déplacer la tête de lecture-écriture vers le haut et passer à l'état A.
Pour ce faire, nous avons besoin d'une construction similaire à la construction de la règle 1, mais nous ne descendons pas, mais vers le haut. Les trois tuiles suivantes donneront le résultat souhaité:
Carreaux de colonne initiale
Nous percevrons les limites de la zone de simulation comme si elles avaient une face «x».
Cela signifie que pour créer la colonne initiale (machine de Turing au temps 0), nous avons besoin de deux tuiles spéciales. Une tuile est nécessaire pour stocker la valeur 0 sur la bande, qui initialise la bande, et une autre tuile - pour stocker la position de la tête de lecture / écriture dans l'état A, qui est notre état initial.
Ces deux tuiles sont:
Ensemble de tuiles prêt
Voici l'ensemble complet de 12 tuiles que nous utiliserons:
Simulation complète
Voici la conception originale de notre machine Turing au temps 0. Notez que c'est l'un des états initiaux possibles, mais c'est l'état que nous avons choisi. Nous ne laissons pas la possibilité de choisir où commence la tête de lecture / écriture et sa présence également. Si nous ne suivons que les règles des faces, nous pouvons obtenir 4 ou 0 têtes de lecture-écriture, ou n'importe quel nombre entre elles.
De là, pour créer la deuxième colonne, nous partons du haut et descendons, en choisissant une tuile qui correspond aux restrictions de la face qu'elle touche. Dans cette première étape, la tête lit 0, écrit 1, descend et passe à l'état B.
Voici la deuxième étape, où la tête lit 0, écrit 1, monte et passe à l'état A.
Voici la dernière étape dans laquelle la tête lit 1 et entre dans l'état final, indiquant que le programme est terminé.
Le programme s'est terminé et nous a donné une valeur de sortie de 0110, ou 6. Ces valeurs de sortie ne sont pas particulièrement importantes, mais d'autres programmes peuvent produire une sortie significative. Par exemple, nous pouvons forcer une machine de Turing à ajouter deux nombres, et la sortie sera la somme de ces deux nombres.
Détail important
Ici, nous devons mentionner un détail important que nous n'avons pas considéré ci-dessus, et qui n'est pas mentionné dans la plupart des explications des machines de Turing sur les carreaux Van.
Lorsque vous placez la deuxième tuile pour le temps 2, la seule restriction sur les faces est que la tuile doit avoir x en haut et 1 à gauche. En fait, à cause de cela, la situation devient ambiguë, car il n'est pas clair laquelle des deux tuiles illustrées ci-dessous doit être sélectionnée.
Alors, comment choisissons-nous la bonne?
La réponse est que nous faisons simplement une hypothèse et choisissons l'une d'entre elles. Si dans ce cas la mauvaise tuile est sélectionnée, alors quand nous passerons à la tuile suivante, nous chercherons une tuile avec x en haut et B0 à gauche. Une telle tuile n'existe pas, nous ne pouvons donc pas mettre la tuile. Lorsque cela se produit, nous devons revenir à la dernière vignette et essayer l'une des autres options.
C'est, malheureusement, lors de la simulation de machines Turing à l'aide de carreaux Wang, il y a littéralement un processus d'essai et d'erreur, mais au moins, il est tout à fait gérable. Cela complique vraiment un peu les calculs dans le pixel shader (ou dans d'autres appareils à parallélisme élevé), mais les coûts ne sont pas beaucoup plus élevés.
Conclusion et liens
Certains des liens ci-dessous traitent des carreaux Wang et des machines Turing, mais les discussions ne semblent pas adhérer strictement aux machines Turing. Par exemple, vous remarquerez peut-être que dans certains exemples, les données sont autorisées à revenir dans le temps - lorsque le programme se termine, la réponse est sur bande au moment 0 de la machine de Turing, malgré le fait que ces données n'étaient pas là au moment 0. Cela montre que les tuiles Wang peuvent faire les calculs par elles-mêmes, pas seulement simuler des machines de Turing, mais je ne sais pas exactement comment cette technique sera appelée.
De plus, si vous êtes intéressé à savoir ce qui est utile dans le calcul à l'aide de carreaux Wang, alors personnellement, je ne peux pas imaginer des cas d'application pratique. Cependant, les scientifiques semblent avoir découvert que l'ADN peut agir de la même manière que les carreaux de Van dans le sens où les connexions ne sont établies qu'entre des faces compatibles. Grâce à cela, des calculs basés sur l'ADN sont désormais recherchés sur la base du processus de calcul à l'aide de carreaux Wang. Sujet assez intéressant!
Voici l'implémentation du calcul des nombres premiers à l'aide des tuiles Wang dans Shadertoy dans le pixel shader WebGL:
Shadertoy: WangTiles: PrimeGeneratorVoici d'autres vidéos intéressantes sur les voitures Turing et le problème de l'arrêt:
Turing Machines Explained - ComputerphileTuring et le problème de l'arrêt - ComputerphileEt voici quelques liens supplémentaires:
Calculer avec des tuilesWikipédia: tuiles VanTuiles Wang et machines de TuringTuiles Wang - 1Voici quelques articles scientifiques:
Calculer avec des tuilesCalculabilité des pavages