图灵机

cjaizss

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include <assert.h>
   
5. 
   
6. int *tape;
   
7. int tape_len;
   
8. int tape_pos=0;
   
9. #ifdef START
   
10. #undef START
    
11. #endif
    
12. #ifdef ACCEPT
    
13. #undef ACCEPT
    
14. #endif
    
15. #ifdef REJECT
    
16. #undef REJECT
    
17. #endif
    
18. #ifdef BLANK
    
19. #undef BLANK
    
20. #endif
    
21. #define START 0
    
22. #define ACCEPT 1
    
23. #define REJECT 2
    
24. #define BLANK 0
    
25. int stat = START;
    
26. int max_stat = 3;/*:0:start,1:accept,2:reject,3~max_stat*/
    
27. int max_char = 1;/*0:balnk,1~max_char*/
    
28. typedef struct {
    
29.         int stat_now;
    
30.         int char_now;
    
31.         int stat_next;
    
32.         int char_next;
    
33.         int dir;/*0:tape_pos--,else:tape_pos++*/
    
34. } rule_t;
    
35. rule_t *rule;
    
36. int rule_len;
    
37. 
    
38. static void init_turing(const char* program)
    
39. {
    
40.         FILE* f;
    
41.         char s[100];
    
42.         char s2[100];
    
43.         int rule_alloc_len;
    
44. 
    
45.         tape_len = 1024*1024;
    
46.         tape = (int*)malloc(sizeof(*tape)*tape_len);
    
47.         rule_len = 0;
    
48.         rule_alloc_len = 100;
    
49.         rule = (rule_t*)malloc(sizeof(rule_t)*rule_alloc_len);
    
50.         f = fopen(program,"r");
    
51.         while(1) {
    
52.                 if(fgets(s,sizeof(s),f)==NULL)
    
53.                         break;
    
54.                 if(sscanf(s,"%s",s2)!=1)
    
55.                         continue;
    
56.                 if(strcmp(s2,"tape_len")==0) {
    
57.                         sscanf(s,"%s%d",s2,&tape_len);
    
58.                         tape = (int*)realloc(tape,sizeof(*tape)*tape_len);
    
59.                         continue;
    
60.                 }
    
61.                 if(strcmp(s2,"max_stat")==0) {
    
62.                         sscanf(s,"%s%d",s2,&max_stat);
    
63.                         assert(max_stat>REJECT);
    
64.                         continue;
    
65.                 }
    
66.                 if(strcmp(s2,"max_char")==0) {
    
67.                         sscanf(s,"%s%d",s2,&max_char);
    
68.                         assert(max_char>BLANK);
    
69.                         continue;
    
70.                 }
    
71.                 if(sscanf(s,"%d%d%d%d%d",
    
72.                                         &rule[rule_len].stat_now,
    
73.                                         &rule[rule_len].char_now,
    
74.                                         &rule[rule_len].stat_next,
    
75.                                         &rule[rule_len].char_next,
    
76.                                         &rule[rule_len].dir) == 5) {
    
77.                         if(max_char < rule[rule_len].char_now)
    
78.                                 max_char = rule[rule_len].char_now;
    
79.                         if(max_char < rule[rule_len].char_next)
    
80.                                 max_char = rule[rule_len].char_next;
    
81.                         if(max_stat < rule[rule_len].stat_now)
    
82.                                 max_stat = rule[rule_len].stat_now;
    
83.                         if(max_stat < rule[rule_len].stat_next)
    
84.                                 max_stat = rule[rule_len].stat_next;
    
85.                         rule_len++;
    
86.                         if(rule_len >= rule_alloc_len) {
    
87.                                 rule_alloc_len += 100;
    
88.                                 rule = (rule_t*)realloc(rule,sizeof(rule_t)*rule_alloc_len);
    
89.                         }
    
90.                 }
    
91. 
    
92.         }
    
93. 
    
94.         rule = (rule_t*)realloc(rule,sizeof(rule_t)*rule_len);
    
95.         fclose(f);
    
96. }
    
97. 
    
98. static void init_tape(void)
    
99. {
    
100.         int i;
     
101.         int x;
     
102. 
     
103.         memset(tape,0,sizeof(int)*tape_len);
     
104.         i=0;
     
105.         while(1) {
     
106.                 if(scanf("%d",&x)!=1)
     
107.                         break;
     
108.                 if(x<0||x>max_char)
     
109.                         fprintf(stderr,"%s:%d:input error",__FILE__,__LINE__);
     
110.                 else
     
111.                         tape[i++]=x;
     
112.         }
     
113. }
     
114. 
     
115. static int work_turing(void)
     
116. {
     
117.         int i;
     
118. 
     
119.         init_tape();
     
120.         while(1) {
     
121.                 for(i=0;i<rule_len;i++)
     
122.                         if((rule[i].stat_now == stat)
     
123.                                         && (rule[i].char_now == tape[tape_pos]))
     
124.                                 break;
     
125.                 if(i>=rule_len) {
     
126.                         fprintf(stderr,"%s:%d:ERROR RULES:stat=%d,char=%d\n",__FILE__,__LINE__,stat,tape[tape_pos]);
     
127.                         exit(1);
     
128.                 }
     
129.                 stat = rule[i].stat_next;
     
130.                 tape[tape_pos] = rule[i].char_next;
     
131.                 if(rule[i].dir)
     
132.                         tape_pos++;
     
133.                 else
     
134.                         tape_pos--;
     
135.                 if(stat <= REJECT)
     
136.                         break;
     
137.         }
     
138.         return stat;
     
139. }
     
140. 
     
141. void write_result(const char* filename)
     
142. {
     
143.         FILE *f;
     
144.         int i,j;
     
145. 
     
146.         for(i=tape_len-1;i>=0;i--)
     
147.                 if(tape[i] != BLANK)
     
148.                         break;
     
149.         for(j=0;j<=i;j++)
     
150.                 printf("tape[%d]\t%d\n",j,tape[j]);
     
151.         if(filename == NULL)
     
152.                 return;
     
153.         f = fopen(filename,"wb");
     
154.         fwrite(tape,sizeof(int),i+1,f);
     
155.         fclose(f);
     
156. }
     
157. 
     
158. int main(int argc,char**argv)
     
159. {
     
160.         int ret;
     
161. 
     
162.         init_turing(argv[1]);
     
163. 
     
164.         ret = work_turing();
     
165.         switch(ret) {
     
166.                 case ACCEPT:
     
167.                         printf("RESULT:ACCEPT!\n");
     
168.                         break;
     
169.                 case REJECT:
     
170.                         printf("RESULT:REJECT!\n");
     
171.                         break;
     
172.                 default:
     
173.                         printf("%s:%d:ret=%d\n",__FILE__,__LINE__,ret);
     
174.                         break;
     
175.         }
     
176. 
     
177.         if(argc == 3)
     
178.                 write_result(argv[2]);
     
179.         else
     
180.                 write_result(NULL);
     
181. 
     
182.         return 0;
     
183. }
     

复制代码

cjaizss

二进制加1
用1代表1，用2代表0
程序
# cat rule
max_stat 3
max_char 2
0 0 2 0 1
0 2 1 1 1
0 1 3 2 1
3 0 1 1 1
3 2 1 1 1
3 1 3 2 1
每行5个数，
当前状态 当前位置纸带值 下个状态 纸带改变值 读写头方向(1向右，0向左)
图灵机读写头初始位置为0位置，初始无法向左
# echo 1 1 1 2 2 1 | ./a.out rule
RESULT:ACCEPT!
tape[0] 2
tape[1] 2
tape[2] 2
tape[3] 1
tape[4] 2
tape[5] 1
解释一下:
1 1 1 2 2 1
表示二进制100111
出来的数表示是
101000

cjaizss

cjaizss 发表于 2012-11-13 13:28
二进制加1
用1代表1，用2代表0
程序

# echo |./a.out rule
RESULT:REJECT!
无值图灵机转到拒绝状态

cjaizss

复制二进制数
程序
#cat rule_copy
stat    tape    Nstat   Ntape   DIR
0       0       2       0       1
0       1       3       5       1
0       2       4       6       1
3       0       5       0       1
3       1       3       1       1
3       2       3       2       1
4       0       6       0       1
4       1       4       1       1
4       2       4       2       1
5       0       7       1       0
5       1       5       1       1
5       2       5       2       1
6       0       7       2       0
6       1       6       1       1
6       2       6       2       1
7       0       8       0       0
7       1       7       1       0
7       2       7       2       0
8       1       9       1       0
8       2       9       2       0
8       3       10      1       0
8       4       10      2       0
8       5       1       1       1
8       6       1       2       1
9       1       9       1       0
9       2       9       2       0
9       3       11      3       1
9       4       11      4       1
9       5       11      5       1
9       6       11      6       1
11      1       3       3       1
11      2       4       4       1
10      3       10      1       0
10      4       10      2       0
10      5       1       1       1
10      6       1       2       1
程序运行
# echo 1 | ./a.out rule_copy
RESULT:ACCEPT!
tape[0] 1
tape[1] 0
tape[2] 1
# echo 1 2 | ./a.out rule_copy
RESULT:ACCEPT!
tape[0] 1
tape[1] 2
tape[2] 0
tape[3] 1
tape[4] 2
# echo 1 2 1 1 2 1 1 1 2 | ./a.out rule_copy
RESULT:ACCEPT!
tape[0] 1
tape[1] 2
tape[2] 1
tape[3] 1
tape[4] 2
tape[5] 1
tape[6] 1
tape[7] 1
tape[8] 2
tape[9] 0
tape[10]        1
tape[11]        2
tape[12]        1
tape[13]        1
tape[14]        2
tape[15]        1
tape[16]        1
tape[17]        1
tape[18]        2

joker0910

回复 2# cjaizss


跑到 tape[3] 1 已经ACCEPT了？
   

cjaizss

joker0910 发表于 2012-11-17 22:34
回复 2# cjaizss

恩,后面不用算了

cjaizss

翻转
stat    tape    Nstat   Ntape   DIR
0       0       2       0       1
0       1       3       5       1
0       2       4       5       1
3       0       5       0       0
3       1       3       1       1
3       2       3       2       1
3       3       5       3       0
3       4       5       4       0
4       0       6       0       0
4       1       4       1       1
4       2       4       2       1
4       3       6       3       0
4       4       6       4       0
5       1       7       3       0
5       2       8       3       0
5       3       10      3       1
5       4       10      4       1
5       5       10      5       1
6       1       7       4       0
6       2       8       4       0
6       3       10      3       1
6       4       10      4       1
6       5       10      6       1
7       1       7       1       0
7       2       7       2       0
7       3       9       3       1
7       4       9       3       1
7       5       9       5       1
8       1       8       1       0
8       2       8       2       0
8       3       9       4       1
8       4       9       4       1
8       5       9       6       1
9       1       3       3       1
9       2       4       4       1
9       3       10      3       1
9       4       10      4       1
10      0       11      0       0
10      3       10      3       1
10      4       10      4       1
11      3       11      1       0
11      4       11      2       0
11      5       1       1       1
11      6       1       2       1
测试
# echo 1 2 1 1 2 1 1 1 2 | ./a.out rule
RESULT:ACCEPT!
tape[0] 2
tape[1] 1
tape[2] 1
tape[3] 1
tape[4] 2
tape[5] 1
tape[6] 1
tape[7] 2
tape[8] 1

joker0910

原来打纸带真的可以编程～～ 嗯，怎么个思路？ 想做个规则，有心无力啊...

cjaizss

下面这个效率高一些

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. #include <assert.h>
   
6. 
   
7. int *tape;
   
8. int tape_len;
   
9. int tape_pos=0;
   
10. #ifdef START
    
11. #undef START
    
12. #endif
    
13. #ifdef ACCEPT
    
14. #undef ACCEPT
    
15. #endif
    
16. #ifdef REJECT
    
17. #undef REJECT
    
18. #endif
    
19. #ifdef BLANK
    
20. #undef BLANK
    
21. #endif
    
22. #define START 0
    
23. #define ACCEPT 1
    
24. #define REJECT 2
    
25. #define BLANK 0
    
26. int stat = START;
    
27. int max_stat = 3;/*:0:start,1:accept,2:reject,3~max_stat*/
    
28. int max_char = 1;/*0:balnk,1~max_char*/
    
29. typedef struct {
    
30.         int stat_next;
    
31.         int char_next;
    
32.         int dir;/*0:tape_pos--,else:tape_pos++*/
    
33. } rule_t;
    
34. rule_t **rule;
    
35. 
    
36. static void init_turing(const char* program)
    
37. {
    
38.         FILE* f;
    
39.         int i,j;
    
40.         char s[100];
    
41.         char s2[100];
    
42.         int stat_now,char_now,stat_next,char_next,dir;
    
43. 
    
44.         tape_len = 1024*1024;
    
45.         tape = (int*)malloc(sizeof(*tape)*tape_len);
    
46.         f = fopen(program,"r");
    
47.         while(1) {
    
48.                 if(fgets(s,sizeof(s),f)==NULL)
    
49.                         break;
    
50.                 if(sscanf(s,"%d%d",&stat_now,&char_now)!=2)
    
51.                         continue;
    
52.                 if(max_stat < stat_now)
    
53.                         max_stat  = stat_now;
    
54.                 if(max_char < char_now)
    
55.                         max_char = char_now;
    
56.         }
    
57.         fclose(f);
    
58.         rule = (rule_t**)malloc(sizeof(rule_t*)*(max_stat+1));
    
59.         rule[0] = (rule_t*)malloc(sizeof(rule_t)*(max_stat+1)*(max_char+1));
    
60.         for(i=1;i<=max_stat;i++)
    
61.                 rule[i]=rule[i-1]+(max_char+1);
    
62.         for(i=0;i<=max_stat;i++)
    
63.                 for(j=0;j<max_char;j++) {
    
64.                         rule[i][j].stat_next = REJECT;
    
65.                         rule[i][j].char_next = j;
    
66.                         rule[i][j].dir = 1;
    
67.                 }
    
68.         f = fopen(program,"r");
    
69.         while(1) {
    
70.                 if(fgets(s,sizeof(s),f)==NULL)
    
71.                         break;
    
72.                 if(sscanf(s,"%s",s2)!=1)
    
73.                         continue;
    
74.                 if(strcmp(s2,"tape_len")==0) {
    
75.                         sscanf(s,"%s%d",s2,&tape_len);
    
76.                         tape = (int*)realloc(tape,sizeof(*tape)*tape_len);
    
77.                         continue;
    
78.                 }
    
79.                 if(sscanf(s,"%d%d%d%d%d",
    
80.                                         &stat_now,
    
81.                                         &char_now,
    
82.                                         &stat_next,
    
83.                                         &char_next,
    
84.                                         &dir) == 5) {
    
85.                         rule[stat_now][char_now].stat_next = stat_next;
    
86.                         rule[stat_now][char_now].char_next = char_next;
    
87.                         rule[stat_now][char_now].dir = dir;
    
88.                 }
    
89. 
    
90.         }
    
91. 
    
92.         fclose(f);
    
93. }
    
94. 
    
95. static void init_tape(void)
    
96. {
    
97.         int i;
    
98.         int x;
    
99. 
    
100.         memset(tape,0,sizeof(int)*tape_len);
     
101.         i=0;
     
102.         while(1) {
     
103.                 if(scanf("%d",&x)!=1)
     
104.                         break;
     
105.                 if(x<0||x>max_char)
     
106.                         fprintf(stderr,"%s:%d:input error",__FILE__,__LINE__);
     
107.                 else
     
108.                         tape[i++]=x;
     
109.         }
     
110. }
     
111. 
     
112. static int work_turing(void)
     
113. {
     
114.         int stat_now,char_now;
     
115. 
     
116.         init_tape();
     
117.         while(1) {
     
118.                 stat_now = stat;
     
119.                 char_now = tape[tape_pos];
     
120.                 stat = rule[stat_now][char_now].stat_next;
     
121.                 tape[tape_pos] = rule[stat_now][char_now].char_next;
     
122.                 if(rule[stat_now][char_now].dir)
     
123.                         tape_pos++;
     
124.                 else
     
125.                         tape_pos--;
     
126.                 if(stat <= REJECT)
     
127.                         break;
     
128.         }
     
129.         return stat;
     
130. }
     
131. 
     
132. void write_result(const char* filename)
     
133. {
     
134.         FILE *f;
     
135.         int i,j;
     
136. 
     
137.         for(i=tape_len-1;i>=0;i--)
     
138.                 if(tape[i] != BLANK)
     
139.                         break;
     
140.         for(j=0;j<=i;j++)
     
141.                 printf("tape[%d]\t%d\n",j,tape[j]);
     
142.         if(filename == NULL)
     
143.                 return;
     
144.         f = fopen(filename,"wb");
     
145.         fwrite(tape,sizeof(int),i+1,f);
     
146.         fclose(f);
     
147. }
     
148. 
     
149. int main(int argc,char**argv)
     
150. {
     
151.         int ret;
     
152. 
     
153.         init_turing(argv[1]);
     
154. 
     
155.         ret = work_turing();
     
156.         switch(ret) {
     
157.                 case ACCEPT:
     
158.                         printf("RESULT:ACCEPT!\n");
     
159.                         break;
     
160.                 case REJECT:
     
161.                         printf("RESULT:REJECT!\n");
     
162.                         break;
     
163.                 default:
     
164.                         printf("%s:%d:ret=%d\n",__FILE__,__LINE__,ret);
     
165.                         break;
     
166.         }
     
167. 
     
168.         if(argc == 3)
     
169.                 write_result(argv[2]);
     
170.         else
     
171.                 write_result(NULL);
     
172. 
     
173.         return 0;
     
174. }
     
175. 
     

复制代码

zj47596731

mark