Premier exemple de machine de Turing

Une machine de Turing pour le langage X = {aⁿbⁿ | n ≥ 0}

Un machine M qui accepte le langage X est la suivante

l'ensemble des états est Q = {0, 1, 2, 3, 4},
l'alphabet d'entrée est Σ = {a, b},
l'alphabet de bande est Γ = {a, b, A, B, #},
l'état initial est q₀ = 0,
le seul état final est l'état 4,
l'ensemble des transitions est décrit par la figure ou le tableau ci-dessous. Cette machine est déterministe.

Fig 1 - Diagramme des transitions

Fonction de transition.
δ	a	b	A	B	#
0	1,A,R			3,B,R
1	1,a,R	2,B,L		1,B,R
2	2,a,L		0,A,R	2,B,L
3				3,B,R	4,#,R
4

Voici le calcul de la machine avec l'entrée aaabbb.

Calcul avec l'entrée aaabbb.
No	Configuration	No	Configuration	No	Configuration	No	Configuration	No	Configuration
0	0aaabbb	6	2AaaBbb	12	AA2aBBb	18	AAAB2BB	24	AAABBB3#
1	A1aabbb	7	A0aaBbb	13	A2AaBBb	19	AAA2BBB	25	AAABBB#4#
2	Aa1abbb	8	AA1aBbb	14	AA0a1BBb	20	AA2ABBB
3	Aaa1bbb	9	AAa1Bbb	15	AAA1BBb	21	AAA0BBB
4	Aa2aBbb	10	AAaB1bb	16	AAAB1Bb	22	AAAB3BB
5	A2aaBbb	11	AAa2BBb	17	AAABB1b	23	AAABB3B