Retour vers le site

Machine de Turing

Table des matières

  1. 1. Histoire
  2. 2. Définition
    1. 2.1. Composantes
    2. 2.2 Fonctionnement
  3. 3. Code
    1. 3.1. Exécution
    2. 3.2. Analyse
  4. 4. Bonus

1. Histoire

C’est en 1936 qu’apparait pour la première fois le terme de “Machine de Turing”. Il a été introduit par le chercheur britanique du même nom dans un article du nom de On Cumputable Numbers, With An Application To The Entscheidungsproblem qui répond au problème posé 8 ans auparavant par le mathématicien David Hilbert. Il s’agit du problème de la décidabilité (en allemand “Entscheidungsproblem”) soit: existe-t-il un algorithme qui décide si une proposition énoncée dans un système logique est valide ou non ?
Mais alors pourquoi sa proposition est-elle si célèbre ? Et bien, lors de sa découverte, les ordinateurs n’existaient pas. La raison principale tient à son extrême simplicité qui a permis d’établir des résultats sans nul doute beaucoup plus difficiles à démontrer avec des modèles moins rudimentaires. Cette machine est en fait le modèle le plus simple que l’on puisse concevoir et qui satisfait aux critères informels mais universels qui caractérisent un algorithme.1

Il faut garder à l’esprit que la machine de Turing est un modèle universel de calcul et qu’elle peut calculer tout ce que n’importe quel ordinateur physique peut calculer

2. Définition

2.1. Composantes

Une machine de Turing est composé de 4 éléments:2

  1. Un Ruban Infini: divisé en case contenant chacune un symbole ou rien .
  2. Une Une tête de lecture/écriture : elle permet de :
    - déchiffre le ruban
    - le modifier
    - se déplacer de gauche à droite dessus.
  3. Un Registre d’étât : Enregistre l’état courant de la machine.
  4. Une table d’actions : qui indique à la machine quel symbole écrire sur le ruban, comment déplacer la tête de lecture (par exemple «←\leftarrow» pour une case vers la gauche, «→\rightarrow» pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l’état courant de la machine.

2.2 Fonctionnement

Le fonctionnement de la machine de Turing est alors le suivant : à chaque étape de son calcul, la machine évolue en fonction de l’état dans lequel elle se trouve et du symbole inscrit dans la case du ruban où se trouve la tête de lecture. Ces deux informations permettent la mise à jour de l’état de la machine grâce à la fonction de transition. À l’instant initial, la machine se trouve dans l’état ρ0\rho_0, et le premier symbole du ruban est l’entrée du programme. La machine s’arrête lorsqu’elle rentre dans un état terminal. Le résultat du calcul est alors le mot formé par les symboles successivement lus par la machine.

3. Code

Voici un code d’une machine de Turing fonctionnel que j’ai réalisée en python.

import time

def open_file(name):
    file = open(name + '.txt', 'r')
    read_file = file.read()
    prgm = []
    decoupage = read_file.split('\n')
    for i in range(len(decoupage)):
        prgm.append(decoupage[i].split(' '))
    file.close()    
    return prgm


class Run:
    def __init__(self):
        self.head_pos = 0
        self.entree = list(input("Initial tape: "))
        self.state = input('Initial state: ')

    def read(self, letter):
        if letter == '_':
            if self.entree[self.head_pos] != ' ':
                return False
        elif letter == '*':
            if self.entree[self.head_pos] == ' ':
                return False
        elif letter != self.entree[self.head_pos]:
            return False
        return True

    def write(self, letter):
        if letter == '_':
            self.entree[self.head_pos] = ' '
        elif letter != '*':
            self.entree[self.head_pos] = letter

    def move(self, direction):
        if direction == 'r':
            if self.head_pos < (len(self.entree) - 1):
                self.head_pos += 1
            else:
                self.entree += ' '
                self.head_pos += 1
        if direction == 'l':
            if self.head_pos > 0:
                self.head_pos -= 1
            else:
                self.entree.insert(0, ' ')

    def mod_state(self, state):
        if state == 'halt':
            print("Final tape: {}".format(''.join(self.entree)))
            quit()
        else:
            self.state = state

    def line(self, prgm):
        while 1:
            for i in range(len(prgm)):
                if prgm[i] != ' ':
                    if prgm[i][0] == self.state:
                        lecture = self.read(prgm[i][1])
                        if lecture:
                            self.write(prgm[i][2])
                            self.move(prgm[i][3])
                            self.mod_state(prgm[i][4])



program = open_file('prgm')
Run().line(program)

Voici un programme pour cette machine.

gauche 0 _ r defile_d0
gauche 1 _ r defile_d1
gauche _ _ * true

droite * * l droite
droite _ _ r gauche

defile_d0 * * r defile_d0
defile_d0 _ _ l is0

defile_d1 * * r defile_d1
defile_d1 _ _ l is1

is0 0 _ l droite
is0 1 _ l false
is0 _ _ * true
is1 1 _ l droite
is1 0 _ l false
is1 _ _ * true

false * _ l false
false _ n r false1
false1 _ o * halt

true _ y r true1
true1 _ e r true2
true2 _ s * halt

Ce programme permet de déterminer si l’entrée fournie est un palindrome binaire 3 ou non.

3.1. Exécution

Examinons l’exécution pas à pas de ce programme de recherche de palindrome binaire pour le nombre 101 et l’état initial de gauche.
Les instructions ce lisent de la façon suivante :

gauche 0 _ r defile_0
état de départ si la lecture vaut 0 on écrit un espace on bouge à droite état d’arrivée

Faisons notre exemple pas à pas :

Execution Ruban de départ Commande Ruban d’arrivée Etat d’arrivée
1 “101” gauche 1 _ r defile_1 ” 01” defile_d1
2 ” 01” defile_d1 * * r defile_d1 ” 01” defile_d1
3 ” 01” defile_d1 * * r defile_d1 ” 01” defile_d1
4 ” 01_” defile_d1 _ _ l is1 ” 01” is1
5 ” 01” is1 1 _ _ l droite ” 0 ” droite
6 ” 0 ” droite * * l droite ” 0 ” droite
7 “_0” droite _ _ r gauche ” ” gauche
8 ” 0 ” gauche _ _ * true ” ” true
9 ” _ ” true _ y r true1 ” y ” true1
10 ” y_” true1 _ e r true2 ” ye” true2
11 ” ye_” true2 _ s * halt ” yes” halt

Le mot-clé halt signifie que l’on arrête la machine.

3.2. Analyse

On commence tout d’abord par lire le premier chiffre de gauche qui est un 1 et on l’efface.
On se dirige donc vers le dernier chiffre pour vérifier s’il s’agit aussi d’un 1 puis on l’efface.
On continue l’opération jusqu’à ce qu’il ne reste plus aucuns chiffres.
Ainsi, on affiche le message “yes”.

4. Bonus

Voici pour les esprits tordu (dont je fais partie) une version intéressante de la machine de turing cette fois-ci en bash (Pour vous montrer que cette machine peut être codée avec presque n’importe quoi) : 4

#!/bin/bash
#turing.sh V0.21
# This is an turing machine implemented in Bash.


if [ -z "$1" ]; then
    echo "You should specify an input file!" 1>&2
    exit 1
fi
oldIFS=$IFS
state=0
line=0
endless=1

bandwidth=79
pos=0
alpha[0]=" "
alpha[1]="1"
alpha[2]="0"
alphasize=2

#Init Band

IFS=$'\n'
echo "# opening: $1"
for l in $(cat $1 |sed "s/\#.*//g"|sed "/^\s*$/d"|sed "s/^\s*//g"|sed "s/\s*$//g")
do
    p=0
    cor=0
    ((line+=1))
    echo -n "$line: "
        echo $l>&2
    case ${l:0:1} in
        "<"|"I")
        it=""
        for i in `seq 2 ${#l}`; do
            c=${l:(($i-1)):1}
            cok=0
            for j in $(seq 0 $alphasize)
            do
                if [ "$cok" -eq "0" ]; then
                    if [ "$c" == "${alpha[$j]}" ]; then
                        cok=1
                    fi
                fi
            done
            if [ "$cok" == "1" ]; then
                band[(($p-$cor))]=$c
                it="$it$c"
            else
                echo "# Ignoring character '$c' @$line:$pos." >&2
                ((cor+=1))
            fi
            ((p+=1))    
        done
        echo "# (I@    0)  $it">&2

        ;;
    "!"|"S")
        state=${l:1}
        echo "# S:  $state"
        ;;
    "."|"P")
        pos=${l:1}
        echo "# P:  $pos"
        ;;
    "L")
        bandwidth=$((${l:1}-1))
        echo "# L:  $bandwidth"
        ;;
    "@"|"A")
        p=1
        al=""
        alphasize=$((${#l}-1))
        for i in $(seq 2 ${#l})
        do
            c=${l:(($i-1)):1}
            alpha[$p]=$c
            al="$al$c"

            ((p+=1))
        done
        echo "# A:  $al ($alphasize symbols)"
    ;;
    *)
        IFS=","
        a=($l)
        count=0
        while [ -n "${a[$count]}" ]
        do
            ((count+=1))
        done
        
        if [ "$count" -ne "5" ]; then
            echo "# Missformed Statedescription @$line -- ignoring (program will not work properly)" >&2
            echo "#   Statedescribtion looks like: State,Symbol expected,Symbol to write,Headdirection,Next State">&2
        else
            stat="${a[0]}"
            expect="${a[1]}"
            write="${a[2]}"
            move="${a[3]}"
            next="${a[4]}"
            #echo "# State: $stat"
            #echo "#   expecting:  $expect"
            #echo "#   write:      $write"
            #echo "#   move to:    $move"
            #echo "#   next state: $next"
            if [ "$next" == "F" ]; then
                endless=0
            fi
            index=$(($stat*($alphasize+1)))

            #case $expect in
            #   # " "->((index+=0))->dumm
            #   "0")
            #       ((index+=1))
            #   ;;
            #   "1")
            #       ((index+=2))
            #   ;;
            #esac

            ok=0
            off=0
            wok=0
            #echo $alphasize
            IFS=$oldIFS#$"\n"
            for i in $(seq 0 $alphasize)
            do
                #echo "\$i=\"$i\""
                #echo "\$alpha[$i]=${alpha[$i]}"
                if [ "$ok" -ne "1" ]; then
                    if [ "$expect" == "" -o "$expect" == "${alpha[$i]}" ]; then
                        ((index+=$off))
                        ok=1
                    fi
                fi
                if [ "$wok" -eq "0" ]; then
                    if [ "${alpha[$i]}"=="$write" ]; then
                        wok=1
                    fi
                fi
                ((off+=1))
            done

            if [ "$ok" -eq "0" ]; then
                echo "# Unspecified symbol '$expect' expected @$line">&2
                exit 1
            fi
            if [ "$wok" -eq "0" ]; then
                echo "# Should write unspecified symbol '$write' @$line">&2
                exit 1
            fi

            eval "states_write[$index]=\"$write\""
            eval "states_move[$index]=\"$move\""
            eval "states_next[$index]=\"$next\""
        fi
        IFS=$oldIFS
    esac
done

echo P: $pos

if [ "$endless" -eq "1" ]; then 
    echo -n "## This seems to be an endless turing machine. Do you realy want to start it? [y/N] ">&2
    read -n 1 ant
    echo >&2
    if [ "$ant" != "y" ]; then
        exit 0
    fi
fi

echo $state
cycles=0
until [ "$state" == "F" ]
do
    ((cycles+=1))
    echo -n "# ($state@$(echo $cycles|gawk '{ printf "%5d\n", $1 }'))  "
    for i in $(seq 0 $bandwidth)
    do
        if [ "$i" -eq "$pos" ]; then
            echo -n "_${band[$i]}_"
        else
            echo -n "${band[$i]}"
        fi
    done
    echo

    #Read
    data=${band[$pos]}
    #echo "$state*($alphasize+1)"
    index=$(($state*($alphasize+1)))
    ok=0
    off=0
    IFS=$oldIFS
    #echo "# Data: $data@$pos"
    for i in $(seq 0 $alphasize)
    do
        if [ "$ok" -ne "1" ]; then
            #echo "\"$data\"==\"${alpha[$i]}\""
            if [ "$data" == "" -o "$data" == "${alpha[$i]}" ]; then
                #echo "# Found ${alpha[$i]}@$i+$off"
                ((index+=$off))
                ok=1
            fi
        fi
        ((off+=1))
    done
    if [ "$ok" -eq "0" ]; then
        echo "# Unspecified symbol '$data'!">&2
        exit 1;
    fi
    

    #case $data in
    #   "0")
    #       ((index+=1))
    #   ;;
    #   "1")
    #       ((index+=2))
    #   ;;
    #esac
    
    #Write
    #echo "## Writing: ${states_write[$index]}@$index"
    if [ -z "${states_write[$index]}" ]; then
        echo "## State: ($state,$data) is not defined! Halted.">&2
        exit 1
    fi
    band[$pos]=${states_write[$index]}

    #Move Head
    case ${states_move[$index]} in
        "<")
            ((pos-=1))
        ;;
        ">")
            ((pos+=1))
        ;;
    esac
    
    if [ "$pos" -lt "0" ]; then
        #pos=$bandwidth
        pos=0
        for (( i=bandwidth-1;i>0;i-- ))
            do
                band[i]="${band[$i-1]}"
            done
        band[0]=" "
    fi
    # if [ "$pos" -gt "$bandwidth" ]; then
    #   pos=0
    # fi

    #jump to next state
    #echo "$index: ${states_next[$index]}"
    state=${states_next[$index]}

    if [ "$state" == "F" ]; then
        ((cycles+=1))
        echo -n "# ($state@$(echo $cycles|gawk '{printf "%5d",$1}'))  ">&2
        for i in $(seq 0 $bandwidth)
        do
            echo -n "${band[$i]}">&2
        done
        echo>&2
        echo "# Reached final state. Needed $cycles cycles">&2
    fi
    #t=$(($state * ($alphasize+1)))
    
    #for i in $(seq 0 $alphasize)
    #do
    #   if  [ -z "${states_write[$(($t+$i))]}" ]; then
    #       echo "## State '$state' is not well defined!">&2
    #       exit 1;
    #   fi  
    #done
done

echo "### END ###"
exit 0

PS:

Je n’ai pas trouvé l’occasion de placer une formule de mathématique dans mon rapport. Voici la formule de Taylor-Young tirée de mon cours de math si jamais: f(x)=α∑i=0n(x−α)nn!f(n)(α)+o(xn),f(x) est n fois dérivable sur ℝ,α∈ℝf(x) \underset{\alpha}{=} \sum_{i=0}^{n}{\frac{(x-\alpha)^n}{n!}f^{(n)}(\alpha)} + o(x^n), f(x) \text{ est } n \text{ fois dérivable sur } \mathbb{R}, \alpha \in \mathbb{R}.

  1. Histoire de la machine : ici↩︎

  2. Son fonctionnement : ici↩︎

  3. Un palindrome binaire est un nombre binaire pouvant se lire de la même manière en partant de la gauche et de la droite (Ex: 1001)↩︎

  4. La machine de Turing en bash : ici↩︎