Top 20

1 0x00h 701 pts
2 boris39 701 pts
3 neoxquick 682 pts
4 maf-ia 663 pts
5 thefinder 644 pts
6 benito255 608 pts
7 mego 591 pts
8 madbat2 581 pts
9 Mart 554 pts
10 Stupefy 533 pts
11 nikokks 513 pts
12 tehron 504 pts
13 Kithyane 502 pts
14 plucth 480 pts
15 egosum 473 pts
16 CoYoTe99 416 pts
17 Undr 415 pts
18 Zeta 415 pts
19 loonies2 411 pts
20 Armavica 410 pts

Classement complet

Shoutbox

12 May - 11:47 am

Working again now.

10 May - 4:05 pm

Hello, sorry for the late answer, in fact yes there is an issue with the mail, we will try to fix it quickly. Thanks for reporting

7 May - 6:07 pm

Hi there is a issue for the challenfe Email (number 21). I don't receive a mail on any of them: gmail, hotmail, yahoo. do i fail or is it the challenge ?

28 Feb - 10:35 am

Yes we fixed it

27 Feb - 10:00 pm

Thank you, just validated contest22. The solution checker seems to have been fixed.

27 Feb - 8:40 am

Yes several solutions are accepted of course. I will check one of your answers

26 Feb - 7:51 pm

No 500 error, but the solutions I'm submitting can be verified to be correct. It can't be that only one configuration is accepted, right? - as there are multiple correct configurations for each problem.

26 Feb - 5:54 pm

contest 22 is not concerned by the issue I found, and seems to be working (I suppose you don't have 500 error on this one ?). Your solutions are indeed rejected, but I did not check them yet

26 Feb - 3:25 pm

The validation for contest 22 also seems to be wrong (it's not accepting solutions that are clearly correct). I submitted bug report yesterday.

26 Feb - 9:59 am

Ok I fixed the issue It is higly possible that other challenges are impacted, so don't hesitate to tell meif you encounter this again. Thank you for reporting

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.