Une machine de Turing est une représentation mathématique d'un ordinateur. Elle dispose d'un ruban (tape), sur lequel elle peut se déplacer vers la gauche ou vers la droite, lire et écrire un caractère.
Pour représenter les chiffres, cette machine utilise la base 1. Pour le chiffre 0, elle place un barre (1) sur le ruban, pour représenter le chiffre 2, elle en place 3...
Malgré sa simplicité, cette machine est capable de calculer toutes les fonctions récursives.
Petit exemple :
Un exemple très simple est la fonction Zéro. C'est une fonction constante, qui pour n'importe quel nombre renvoie 0. Rappelons-nous qu'avec notre machine le 0 s'écrit avec une barre (1).
Si nous prenons le ruban contenant le chiffre 4 :
11111000000000000
Nous devrions donc obtenir :
10000000000000000
Analysons le programme :
q0 1 D q1 # On conserve le 1er 1 : pour faire 0
q1 1 0 q2 # Suppression des 1 inutiles
q2 0 D q1
q1 0 0 q3 # Retour à la position initiale
q3 0 G q3
Une machine de Turing dispose d'un algorithme très simple, celui-ci a même été reproduit mécaniquement ou optiquement !
Une instruction se compose de 4 parties :
L'état initial, la condition, l'action et l'état final.
Par exemple pour la première : q0 1 D q1
Au début nous sommes toujours à l'état 0. Le premier élément du ruban est 1.
Notre machine va dont recherche un instruction commençant par q0 1, ensuite elle va exécuter l'instruction contenue dans la seconde partie de l'instruction.
Ici : D q1 : Elle doit donc avancer vers la Droite sur le ruban et passer à l'état q1.
Elle va maintenant recherche une instruction correspondante à l'état q1 et qui a comme condition l'élément courant du ruban : ici 1 et nous exécutons l'action 0 (remplacer l'élément courant du ruban par 0) et passer à l'état q2.
Pour résumer, les actions dont elle dispose sont :
G : Aller à gauche
D : Aller à droite
1 : Écrire un 1
0 : Écrire un 0
et parfois :
* : Écrire une * pour délimiter deux nombres par exemple
Une machine de Turing en Python :
Cette machine est capable de gérer un nombre infini d'état.
# -*- coding: utf-8 -*-
#
# uTuring
#
# Copyright (c) 2010 Amaury GRAILLAT
# Licensed under the GNU GPL license.
# See http://www.gnu.org/licenses/gpl.html
# amoweb.fr
#
# File exemple :
# # Zero function You can comment a line with #
# q0 1 0 q1 {Stat} {Condition} {Action (1, 0, *, L or R)} {Final stat}
# q1 0 D q0
# q0 0 1 q2
#
# =1111000000000000000000:0 ={tape}:{Initial stat (optional)}
#
import os
INDD = 0 ; COND = 1 ; ACTN = 2 ; INDF = 3
ruban = [] ; instr = []
k = 0 # position sur le ruban
q = '0' # état
# Trouve l'instruction correspondant à la condition et
def searchInstruction(q,k) :
# print "searchInstruction(%s,%s)"%(q,k)
for i in instr :
if i[INDD] == q and i[COND] == ruban[k] :
return i
return [0,0,0,0]
def monospace(str) :
str = str.replace("\t", " ");
while str.count(" ") > 0 :
str = str.replace(" ", " ");
return str
if __name__ == '__main__' :
print("Welcome to uTurning : ")
# Charge le programme depuis le fichier :
with open("program.txt") as program :
for instruction in program :
# Charge le ruban
if instruction[0:1] == "=" :
# Partie donnée
for s in instruction :
if s == ':' :
break
elif s != '\n' and s != '=' :
ruban.append(s)
# Position d'origine (facultative)
if len(instruction.split(':')) > 1 :
k = int(instruction.split(':')[1])
# Fin du fichier :
elif instruction[0:3] == "EOF" :
break
# Charge une instruction
elif instruction != '\n' and instruction[0:1] != "#":
instruction = monospace(instruction);
if len(instruction.split(' ')) > 3 :
qStrI = instruction.split(' ')[0]
qStrF = instruction.split(' ')[3]
instr.append([qStrI[1:len(qStrI)], instruction.split(' ')[1],
instruction.split(' ')[2], qStrF[1:len(qStrF)-1]])
# Exceptions :
if len(ruban) == 0 :
print "TAPE missing : example : =11100000:0"
exit()
if len(instr) == 0 :
print "Instructions missing : example : q0 1 0 q2 "
exit()
# Exécution des instructions :
curInst = searchInstruction(q, k)
while curInst != [0,0,0,0] :
# Affiche le ruban :
print (''.join(ruban)) + " (q" + q + ")"
print " "*k + "^"
# Interprête les instructions :
if curInst[ACTN] == 'D' or curInst[ACTN] == 'R' :
k = k + 1
elif curInst[ACTN] == 'G' or curInst[ACTN] == 'L':
k = k - 1
elif k < 0 :
print "Warning ! Out of range : k = -1 ---> k = 0"
else :
ruban[k] = curInst[ACTN]
# Nouvel état
q = curInst[INDF]
curInst = searchInstruction(q, k)
# Affiche le ruban final :
print (''.join(ruban)) + " (q" + q + ")"
print " "*k + "^"
Et quelques exemples (à copier coller dans un fichier program.txt à coté du programme python) :
# Fonction successeur : q0 1 D q0 q0 0 1 qa qa 1 G qa qa 0 D q2 =1111100000000000:0 EOF ---------------------------- # Couples d'entiers : # Suppression : q0 1 D q0 Q0 * * Q1 q1 * 0 q2 q1 1 0 q2 q2 0 D q1 Q1 0 0 Q3 Q3 0 G Q3 Q3 1 1 Q4 Q4 1 G Q4 Q4 0 D Q5 =111*1111000000000000000000
