Xavier Nayrac

Rubyiste accro au TDD, serial blogger, apprenti data scientist, heureux utilisateur de Vim, accordéoniste.
Si vous vous sentez particulièrement généreux, suivez moi sur Twitter.

Une machine de Turing en Ruby - Une bande de données infinie

| Comments

Niveau : facile

Dans la définition d’une machine de Turing on trouve:

Le ruban est supposé être de longueur infinie vers la gauche ou vers la droite, en d’autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. — Wikipédia

C’était une grande limitation de l’implémentation de ma machine de Turing que d’avoir une bande de taille fixe. Avec la nouvelle version, cette limitation est désormais levée.

Permettre à la bande de grandir à l’infini (en théorie, hein, parce que en pratique on est toujours limité par la mémoire de l’ordinateur) est finalement très simple:

lib/turing_machine/tape.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
module TuringMachine

  class Tape

    BLANK_SYMBOL = '0'

    def initialize(data = BLANK_SYMBOL)
      @symbols = data.scan(/./)
      @index = 0
    end

    [...]

    def shift_left
      if @index == 0
        @symbols.unshift(BLANK_SYMBOL)
      else
        @index -= 1
      end
    end

    def shift_right
      @symbols.push(BLANK_SYMBOL) if @index == @symbols.size - 1
      @index += 1
    end

    [...]

Voici quelques explications.

@symbols = data.scan(/./)

Dans le constructeur, on se sert de String#scan pour construire un tableau avec les données initiales de la bande. Par exemple:

1
2
>> "110".scan(/./)
#=>["1", "1", "0"]
@index = 0

Dans le constructeur toujours, la position de la tête de lecture est initialement à zéro.

def shift_left
  if @index == 0
    @symbols.unshift(BLANK_SYMBOL)
  else
    @index -= 1
  end
end

Lorsqu’on bouge la tête de lecture à gauche, nous avons deux cas possibles. Soit la tête de lecture est déjà dans la position la plus à gauche (if @index == 0) et dans ce cas il faut créer une nouvelle cellule en tête du tableau:

1
2
>> ["1", "2"].unshift("0")
#=>["0", "1", "2"]

Soit la tête de lecture est dans une autre position, et il suffit de la décaler d’un cran vers la gauche (@index -= 1).

def shift_right
  @symbols.push(BLANK_SYMBOL) if @index == @symbols.size - 1
  @index += 1
end

Lorsqu’on bouge la tête de lecture à droite, il faut ajouter une cellule à la fin du tableau (@symbols.push) seulement si la tête de lecture est placée toute à droite du tableau (@index == @symbols.size - 1).

Dans tous les cas, il faut déplacer la tête de lecture d’un cran à droite (@index += 1).

Articles connexes

Commentaires