Description

Ce premier challenge (description longue mais challenge facile) a pour but de découvrir les bases des Machines de Turing.
Pour citer Wikipedia :

Une machine de Turing est un appareil théorique qui manipule des symboles sur un ruban en fonction d'une table de règles. En dépit de sa simplicité, une machine de Turing peut être adaptée pour simuler la logique de n'importe quel algorithme, et est particulièrement utile pour comprendre le fonctionnement des ordinateurs.

Je vous laisse faire quelques recherches à leur propos.
Le but ici est simplement d'implémenter une Machine de Turing, et de l'exécuter sur un ruban qu'on vous envoie, dans le but de comprendre comment ça marche avant le prochain challenge.

En résumé (Wikipedia l'explique très bien), une Machine de Turing est une machine à états améliorée, avec un ruban sur lequel elle peut lire et écrire des symboles.
Elle est composée de :

• Un ensemble fini d'états. Parmi eux, il y a un état initial, et un ou plusieurs états finaux.
• Une table de transitions, qui va indiquer, en fonction de l'état courant et du symbole courant lu sur le ruban :
  • le symbole que la machine doit écrire sur le ruban pour remplacer le symbole actuel (ça peut être le même).
  • si la tête de lecture et d'écriture doit être déplacée vers la droite ou vers la gauche sur le ruban.
  • le prochain état interne.

En fait, il y a une infinité de Machines de Turing (avec 2 états internes, ou 3, ou 4, ou 7562, ..., et qui manipulent 2 symboles, ou 3, ou 10, ...). De plus, pour chaque type de Machine de Turing, on peut imaginer beaucoup de tables de transitions différentes.
Dans ce challenge, vous allez manipuler une seule Machine de Turing, qui a :

• 6 états internes : A, B, C, D, E, F. L'état initial est A, et F est le seul état final.
• seulement 2 symboles, 0 et 1.
• Une table de transitions qui est la suivante :

Etat courant	Symbole courant		Symbole à écrire	Déplacer la tête vers la	Prochain état
A	0		1	DROITE	B
A	1		1	GAUCHE	C
B	0		1	DROITE	C
B	1		1	DROITE	B
C	0		1	DROITE	D
C	1		0	GAUCHE	E
D	0		1	GAUCHE	A
D	1		1	GAUCHE	D
E	0		1	DROITE	F
E	1		0	GAUCHE	A

Ceci est en fait une Machine de Turing remarquable (c'est le meilleur prétendant pour le castor affairé 5-state, 2-symbol pour ceux qui sont intéressés).
Maintenant, pour exécuter cette machine, nous avons juste besoin d'un ruban et d'une position initiale dessus. Prenons un exemple.
Sur le ruban, il y a une infinité de 0 et peut-être des 1. Le ruban peu être initialement blanc, ou pas. Nous allons vous fournir des rubans qui contiennent au moins plusieurs 1 initialement.
Prenons ce ruban initial :

...0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 ...
               |                              <- Position de la tête de lecture et d'écriture.

L'état initial est A, et nous lisons le symbole 0. La table de transition nous dit que nous devons écrire 1, aller vers la droite, et placer l'état interne à B.
Voici le nouvel état du ruban :

...0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 ...
                 |                     

Maintenant, puisque l'état courant est B et que le symbole courant est 1, nous devons écrire 1 (donc ne pas changer le symbole courant), aller vers la droite et rester dans le même état interne.
Maintenant le ruban est identique mais la tête a bougé :

...0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 ...
                   |                     

Et nous continuons comme ça, jusqu'à ce que nous atteignions l'état final. En fait, ça peut prendre très longtemps (dans ce cas 47 176 870 étapes si le ruban est initialement blanc !). Donc vous devrez juste renvoyer le ruban après la 1000e itération (si l'état final est atteint avant la 1000e itération, renvoyer alors l'état du ruban dans l'état final bien sur).
Le ruban initial est donné dans la variable tape. La position initiale de la tête sera toujours sur le premier symbole de ce ruban. Dans cet exemple, vous recevriez la variable :
tape = "0 1 1 0 1"
Gardez en tête que ce ruban est infini et qu'il est rempli de 0 partout ailleurs.

L'exécution complète de notre Machine de Turing sur cet exemple est donnée dans ce fichier.
Comme vous pouvez le voir, on atteint l'état final en 35 itérations.
Dans ce cas, vous devriez retourner :
final_tape_state = "1 0 1 0 0 1 0 0 1 1"
Notez qu'il y a des zéros à droite et à gauche, donc la réponse :
final_tape_state = "0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0"
est également valide par exemple.

Variables

Nom	Type		Description
Variables à récupérer
tape	Chaîne de caractères	char*	Le ruban initial. La tête de lecture et d'écriture est positionnée sur le premier symbole du ruban.
Variables à renvoyer
final_tape_state	Chaîne de caractères	char*	Le ruban dans son état final. Si l'état final n'est pas atteint avant la 1000e itération, renvoyer le ruban tel qu'il est après cette 1000e itération.