Top 20

1 0x00h 702 pts
2 boris39 702 pts
3 neoxquick 683 pts
4 maf-ia 664 pts
5 thefinder 645 pts
6 benito255 609 pts
7 mego 591 pts
8 madbat2 582 pts
9 Mart 554 pts
10 tehron 504 pts
11 Kithyane 503 pts
12 plucth 481 pts
13 egosum 474 pts
14 CoYoTe99 417 pts
15 Undr 415 pts
16 Zeta 415 pts
17 loonies2 412 pts
18 Armavica 411 pts
19 vitalimarrenra 403 pts
20 b0n0n 396 pts

Classement complet

Shoutbox

20 Sep - 10:46 am

Bonjour à tous, j'ai créé un nouveau topic sur le forum concernant un problème que je rencontre sur plusieurs challenges, comme il n'est plus très actif, que j'aimerais pouvoir avancer sur ces challenges et que ce chat a une meilleure visibilité, je poste ce message ici en espérant qu'une âme charitable puisse m'aider en répondant à mon message sur le forum :)

3 Sep - 9:39 am

Ah ok je n'avais pas bien compris ton message original. Très bien, ce que tu peux faire c'est poster un message sur le forum avec le lien de téléchargement et les explications. Merci pour ta contribution !

1 Sep - 5:52 pm

Bonjour bonjour, je l'ai créé en Pharo, une implémentation récente du langage smalltalk.

31 Aug - 2:43 pm

Bonjour PharoGuy, re-bienvenue à toi ! Tu as créé cet objet en quel langage ?

30 Aug - 8:23 pm

Bonjour tout le monde ! je redécouvre ce site avec Pharo ! J'ai créé un objet qui gère la récupération et l'envoi des variables, ça pourrait intéresser ?

24 Jul - 5:30 pm

Ça devrait être à nouveau opérationnel, définitivement cette fois ci.

19 Jul - 8:42 pm

A nouveau ? On regarde ça !

16 Jul - 5:26 pm

Bonjour à tous :) Je viens d'essayer de valider le challenge "Wav ? (6)", et j'ai l'impression que la page "validation.php" est de nouveau en carafe.

15 Jul - 8:43 pm

Cool !! Merci beaucoup !!

9 Jul - 11:20 pm

Hello, je regarde ça dès que je peux, probablement demain

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.