Top 20

1 0x00h 696 pts
2 boris39 696 pts
3 neoxquick 677 pts
4 maf-ia 659 pts
5 eax 658 pts
6 thefinder 640 pts
7 benito255 605 pts
8 nikokks 598 pts
9 mego 589 pts
10 madbat2 580 pts
11 plucth 562 pts
12 Mart 550 pts
13 Stupefy 530 pts
14 rostale 516 pts
15 tehron 503 pts
16 Kithyane 498 pts
17 egosum 471 pts
18 malose 428 pts
19 CoYoTe99 415 pts
20 Undr 413 pts

Classement complet

Shoutbox

6 Nov - 8:17 am

Bonjour, un léger problème sur l'épreuve 10 : Une fois réussie, le champ "points earned" indique 72 au lieu de 7 En revanche sur le site le nombre de points comptabilisés est bien 7 Merci pour ce site génial !

21 Oct - 9:48 pm

Équation du challenge 52 corrigée, merci

16 Oct - 8:43 am

Bonjour, il y a aussi un problème d'affichage "invalid equation" dans le challenge 52. Merci

14 Oct - 8:57 pm

Barbapapou l'équation du challenge 29 a été corrigée

4 Oct - 10:30 am

Bonjour, il y a un problème avec l'affichage d'une équation dans le challenge 29

24 Aug - 7:10 pm

@rostale, en effet l'épreuve 21 ne fonctionne plus depuis un moment, pour l'instant on a pas prévu de temps pour la réparer je pense qu'on va finir par la supprimer tout simplement. @nikokks, ok je t'envoie un mail

22 Aug - 11:40 pm

Salut Metatr0n. pourrait on avoir une discussion en MP. J'imagine que tu as mon mail. Ce serait pour discuter de microcontest en general.

28 Jul - 10:38 pm

Pouvez-vous vérifier l'épreuve Email (21) ? En effet, je ne reçois pas d'email de la part du site. Merci

28 Jul - 7:29 pm

Bonjour et merci. Cependant, j'ai résolu le challenge qui me posait pb, donc plus rien à demander... pour l'instant.

28 Jul - 1:48 pm

Ça devrait être réparé maintenant

Connexion
Mot de passe oublié

Supportez nousx

Vous aimez µContest ?
Supportez nous en votant (fun et difficulté) pour µContest sur WeChall :)
Si vous ne l'avez pas encore fait, profitez-en pour lier votre compte
Wechall à µContest pour pouvoir voter !

Merci

Liste des épreuves :: Divers :: Turing Machine I (45)

Résumé

ID : 45
Points : 11
Validations :
Page de l'épreuve
Reporter un bug

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 courantSymbole courant Symbole à écrireDéplacer la tête vers laProchain état
A01DROITEB
A11GAUCHEC
B01DROITEC
B11DROITEB
C01DROITED
C10GAUCHEE
D01GAUCHEA
D11GAUCHED
E01DROITEF
E10GAUCHEA


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
tapeChaîne de caractèreschar*Le ruban initial. La tête de lecture et d'écriture est positionnée sur le premier symbole du ruban.
Variables à renvoyer
final_tape_stateChaîne de caractèreschar*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.