Discussion :

[acacia]

Bonsoir à tous,
j'ai besoin de votre aide concernant une fonction de transition de la machine de turing qui est supposée faire le calcul suivant:
faire l'addition de deux entiers puis convertir le résultat en décimal!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# Add two numbers, according the the Boolos, et al., conventions.  
 
# Erase a one and move to the right (state 0).  If the first square is
# blank, move to the right and halt (state 1).  Else, keep moving to
# the right until you find a blank (state 2).  Write 1 there (state
# 2), move to the left until you find a blank (state 3).  When you do,
# move back right (state 3) and erase a 1 and move right again (state
# 4).  Halt.
 
# St R W M New
(0,1, ,1,r)    # In state 0, if I see a 1, 
	   # write a blank and move right and goto state 1.
	   # State 0: start state -- erase a one
 
(1, , ,99,r)   # The first number was 0, so I'm okay.
(1,1,1,2,r)    
           # State 1: 
(2, ,1,3,l)    # Put a 1 in the first blank.
(2,1,1,2,r)  
(3, , ,4,r)    # Look for first blank 
(3,1,1,3,l)  
(4,1, ,99,r)   # Erase first 1 and halt
 
(4, , ,1000,r)  # Former halt state.
(3,1,1,1000,r)  # Former halt state.
(2,1,1,1000,r)  # Former halt state.
(99, , ,1000,r)  # Former halt state.
(99,1,1,1000,r)  # Former halt state.
(0, , ,1000,r)  # Former halt state.
# Change 1111 to 4.
 
(100, ,0,200,r)  
(100,1,1,140,r)  
(101, ,*,104,l)  
(102, ,1,103,r)  
(103, , ,103,r)  
(103,1, ,106,l)  
(103,*, ,107,l)  
(104, ,1,105,r)  
(104,0,1,105,r)  
(104,1,2,105,r)  
(104,2,3,105,r)  
(104,3,4,105,r)  
(104,4,5,105,r)  
(104,5,6,105,r)  
(104,6,7,105,r)  
(104,7,8,105,r)  
(104,8,9,105,r)  
(104,9,0,104,l)  
(105,*,*,103,r)  
(105,0,0,105,r)  
(105,1,1,105,r)  
(105,2,2,105,r)  
(105,3,3,105,r)  
(105,4,4,105,r)  
(105,5,5,105,r)  
(105,6,6,105,r)   
(105,7,7,105,r)  
(105,8,8,105,r)  
(105,9,9,105,r)  
(106, , ,106,l)  
(106,*,*,104,l)  
(107, , ,107,l)  
(107,*, ,107,l)  
(140,1,1,140,r)   #Put an end of string marker
(140, ,*,141,l)  
(141,1,1,141,l)   #Goto lefthand 1
(141, , ,142,r)  
(142,1, ,101,l)  
 
 
(1000, , ,100,l)  #Goto start state, machine u2d
(1000,1,1,100,l)  #Goto start state, machine u2d

[PRomu@ld]

Et ta question ?

[acacia]

Et ta question ?

La question était: comment fonctionne cette machine en dessus?

et y a t-il une autre idée pour faire la somme sur une seule bande? j'ai su le faire avec 3 bandes, l'une contient le premier nombre et la seconde contient le second, et la troisième contiendra le résultat de la somme, je l'ai faite avec deux états sans et avec retenue.