amoweb.fr

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 ces machines utilise la base 1. Pour représenter 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 dont obtenir :
10000000000000000

Analysons le programme :
q0 1 D q1 # On conserve le 1er 1 : pour faire 0
q1 1 0 q2 # Suppressions des 1 inutiles
q2 0 D q1

q1 0 0 q3 # Retour à la position initiale
q3 0 G q3

Un 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 somme 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 executer 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 correspondant à 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