Skip to content

Instantly share code, notes, and snippets.

@Vftdan

Vftdan/Func8.tsv

Last active December 8, 2018 10:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Vftdan/ece3038f8e2259f51a4e495c7f817496 to your computer and use it in GitHub Desktop.
Save Vftdan/ece3038f8e2259f51a4e495c7f817496 to your computer and use it in GitHub Desktop.
Download ZIP
Turing Machine program for function F(A, B, C) = A and (B equiv C)
Raw
Func8.tsv
Q\A _ * 0 1 x Комментарии
IN halt * l q1 0 l q1 1 l q1
q1 * r LP
LP _ l q2 * r LP 0 r LP 1 r LP x r LP
q2 * n C0 _ l C0 _ l C1
C0 * l q3 0 l C0 1 l C0
q3 * n D1 x l D1 x l D0 x l q3
C1 * l q4 0 l C1 1 l C1
q4 * n D0 x l D0 x l D1 x l q4
D0 * l q5 0 l D0 1 l D0
q5 * l F0 x l F0 x l F0 x l q5
D1 * l q6 0 l D1 1 l D1
q6 * l F0 x l F0 x l F1 x l q6
F0 0 r EX * l F0 0 l F0 1 l F0
F1 1 r EX * l F1 0 l F1 1 l F1
EX _ l CL * r q7 0 r EX 1 r EX x r EX
q7 _ l CL * n EX 0 l LP 1 l LP x r EX
CL _ r q8 * l CL 0 l CL 1 l CL x l CL
q8 _ r q9 0 r q8 1 r q8
q9 _ l qa _ r q9 _ r q9 _ r q9 _ r q9
qa _ l qa halt halt
Raw
Markov008.mrk
//Читать_снизу_вверх
*CL->CL
0CL|->0
1CL|->1
E*0->*0L//Продолжить_основной_цикл
E*1->*1L//Продолжить_основной_цикл
E*->*E
E0->0E
E1->1E
E->CL//Не_нашли_цифры=>Начинаем стирать
*F0->F0*
0F0->F00
1F0->F01
*F1->F1*
0F1->F10
1F1->F11
F->E//Проверка_наличия_неиспользованных_цифр
*Dq0->F0*
*Dq1->F0*
0Dq0->F0//F=0
0Dq1->F0
1Dq0->F0
1Dq1->F1//F=1
*D0->Dq0*//Нашли_*
0D0->D00
1D0->D01
*D1->Dq1*//Нашли_*
0D1->D10
1D1->D11
*Cq0->Dq1*
*Cq1->Dq0*
0Cq0->D1//B=0;C=0;B==C=1
0Cq1->D0//B=0;C=1;B==C=0
1Cq0->D0//B=1;C=0;B==C=0
1Cq1->D1//B=1;C=1;B==C=1
*C0->Cq0*//Нашли_*
0C0->C00
1C0->C01
*C1->Cq1*//Нашли_*
0C1->C10
1C1->C11
L*->*L
L0->0L
L1->1L
*Lq->Cq0*
0Lq->C0//С=1
1Lq->C1//С=0
L->Lq//Основной_цикл
->*L//Вход
Raw
post_export.txt
[<][2][00(0)]
[<][3][0(0)0]
[<][4][(0)00]
[V][5][(1)00]
[?][9,6][(?)xx; Начало основного цикла]
[>][7][1(x)x]
[>][8][1x(x)]
[>][5][(x)xx]
[<][10][1x(x)000]
[?][11,15][1x(?)]
[<][12][1(x)0]
[?][24,13][1(?)0]
[<][14][(1)10]
[<][10][1x(x)110]
[X][16][1x(1) -> 1x(0)]
[<][17][1(x)1 -> 1(x)0]
[?][18,35][1(?)1 -> 1(?)0]
[V][19][1(0)1 -> 1(1)0; C = 0]
[<][20][(1)10 | (1)x1]
[<][21][1x(x)]
[?][23,22][1x(?)]
[<][19][1(x)1]
[<][24][1(0)0]
[<][25][(1)00]
[<][26][1x(x)100]
[?][27,31][1x(?)]
[<][28][1(x)0]
[?][72,29][1(?)0]
[<][30][(1)10]
[<][26][1x(x)110]
[X][32][1x(1) -> 1x(0)]
[<][33][1(x)1 -> 1(x)0]
[?][34,51][1(?)1 -> 1(?)0]
[V][67][1(0)1 -> 1(1)0]
[<][36][(1)10 | (1)x1; C = 1]
[<][37][1x(x)]
[?][39,38][1x(?)]
[<][35][1(x)1]
[<][40][1(0)0]
[<][41][(1)00]
[<][42][1x(x)100]
[?][43,47][1x(?)]
[<][44][1(x)0]
[?][56,45][1(?)0]
[<][46][(1)10]
[<][42][1x(x)110]
[X][48][1x(1) -> 1x(0)]
[<][49][1(x)1 -> 1(x)0]
[?][50,67][1(?)1 -> 1(?)0]
[V][51][1(0)1 -> 1(1)0; (B == C) = 0]
[<][52][(1)10 | (1)x1]
[<][53][1x(x)]
[?][55,54][1x(?)]
[<][51][1(x)1]
[<][56][1(0)0]
[<][57][(1)00]
[<][58][1x(x)100]
[?][59,63][1x(?)]
[<][60][1(x)0]
[?][83,61][1(?)0]
[<][62][(1)10]
[<][58][1x(x)110]
[X][64][1x(1) -> 1x(0)]
[<][65][1(x)1 -> 1(x)0]
[?][66,83][1(?)1 -> 1(?)0]
[V][83][1(0)1 -> 1(1)0]
[<][68][(1)10 | (1)x1; (B == C) = 1]
[<][69][1x(x)]
[?][71,70][1x(?)]
[<][67][1(x)1]
[<][72][1(0)0]
[<][73][(1)00]
[<][74][1x(x)100]
[?][75,79][1x(?)]
[<][76][1(x)0]
[?][83,77][1(?)0]
[<][78][(1)10]
[<][74][1x(x)110]
[X][80][1x(1) -> 1x(0)]
[<][81][1(x)1 -> 1(x)0]
[?][82,91][1(?)1 -> 1(?)0]
[V][83][1(0)1 -> 1(1)0]
[<][84][(x)xx; F = 0]
[?][87,85][(?)xx]
[<][86][xx(x)1xx]
[<][83][x(x)x1xx]
[V][88][(0)00 -> (1)00]
[>][89][1(0)0]
[>][90][10(0)]
[V][100][10(1)]
[<][92][(x)xx; F = 1]
[?][95,93][(?)xx]
[<][94][xx(x)1xx]
[<][91][x(x)x1xx]
[V][96][(0)00 -> (1)00]
[>][97][1(0)0]
[V][98][1(1)0]
[>][99][11(0)]
[V][100][11(1)]
[>][101][(x)xx; Начало проверки наличия неиспользованных аргументов]
[?][113,102][(?)xx]
[>][103][1(x)x]
[?][105,104][1(?)x]
[>][100][11(x)]
[>][106][10(x)]
[?][107,100][10(?)]
[>][108][(x)xx]
[?][113,109][(?)xx]
[>][110][1(x)x]
[>][111][1x(x)]
[?][112,8][1x(?)]
[<][103][1(x)0]
[<][114][1x(x)000; Конец основного цикла; начало удаления "*" и "X"]
[?][115,120][1x(?)]
[<][116][1(x)0]
[?][118,117][1(?)0]
[X][118][1(0)0]
[<][119][(1)00]
[X][113][(0)00]
[<][121][1(x)1]
[<][122][(1)x1]
[S][][(1)x1]
Raw
post_labeled.txt
_ - 000
* - 100
0 - 101
1 - 111
X - 110
https://drive.google.com/file/d/1suf3yPh7Ze1Vhj-FF2iSLRoUoA0jJgfE/view?usp=sharing
---
In:
1. [<][2][00(0)]
2. [<][3][0(0)0]
3. [<][4][(0)00]
4. [V][5][(1)00]
Lp:
5. [?][9,6][(?)xx]
6. [>][7][1(x)x]
7. [>][8][1x(x)]
8. [>][5][(x)xx]
9. [<][10][1x(x)000]
10. [?][11,15][1x(?)]
11. [<][12][1(x)0]
12. [?][24,13][1(?)0]
13. [<][14][(1)10]
14. [<][10][1x(x)110]
15. [X][16][1x(1) -> 1x(0)]
16. [<][17][1(x)1 -> 1(x)0]
17. [?][18,35][1(?)1 -> 1(?)0]
18. [V][19][1(0)1 -> 1(1)0]
C0:
19. [<][20][(1)10 | (1)x1]
20. [<][21][1x(x)]
21. [?][23,22][1x(?)]
22. [<][19][1(x)1]
C0_q3:
23. [<][24][1(0)0]
24. [<][25][(1)00]
25. [<][26][1x(x)100]
26. [?][27,31][1x(?)]
27. [<][28][1(x)0]
28. [?][72,29][1(?)0]
29. [<][30][(1)10]
30. [<][26][1x(x)110]
31. [X][32][1x(1) -> 1x(0)]
32. [<][33][1(x)1 -> 1(x)0]
33. [?][34,51][1(?)1 -> 1(?)0]
34. [V][67][1(0)1 -> 1(1)0]
C1:
35. [<][36][(1)10 | (1)x1]
36. [<][37][1x(x)]
37. [?][39,38][1x(?)]
38. [<][35][1(x)1]
C1_q4:
39. [<][40][1(0)0]
40. [<][41][(1)00]
41. [<][42][1x(x)100]
42. [?][43,47][1x(?)]
43. [<][44][1(x)0]
44. [?][56,45][1(?)0]
45. [<][46][(1)10]
46. [<][42][1x(x)110]
47. [X][48][1x(1) -> 1x(0)]
48. [<][49][1(x)1 -> 1(x)0]
49. [?][50,67][1(?)1 -> 1(?)0]
50. [V][51][1(0)1 -> 1(1)0]
D0:
51. [<][52][(1)10 | (1)x1]
52. [<][53][1x(x)]
53. [?][55,54][1x(?)]
54. [<][51][1(x)1]
D0_q5:
55. [<][56][1(0)0]
56. [<][57][(1)00]
57. [<][58][1x(x)100]
58. [?][59,63][1x(?)]
59. [<][60][1(x)0]
60. [?][83,61][1(?)0]
61. [<][62][(1)10]
62. [<][58][1x(x)110]
63. [X][64][1x(1) -> 1x(0)]
64. [<][65][1(x)1 -> 1(x)0]
65. [?][66,83][1(?)1 -> 1(?)0]
66. [V][83][1(0)1 -> 1(1)0]
D1:
67. [<][68][(1)10 | (1)x1]
68. [<][69][1x(x)]
69. [?][71,70][1x(?)]
70. [<][67][1(x)1]
D1_q6:
71. [<][72][1(0)0]
72. [<][73][(1)00]
73. [<][74][1x(x)100]
74. [?][75,79][1x(?)]
75. [<][76][1(x)0]
76. [?][83,77][1(?)0]
77. [<][78][(1)10]
78. [<][74][1x(x)110]
79. [X][80][1x(1) -> 1x(0)]
80. [<][81][1(x)1 -> 1(x)0]
81. [?][82,91][1(?)1 -> 1(?)0]
82. [V][83][1(0)1 -> 1(1)0]
F0:
83. [<][84][(x)xx]
84. [?][87,85][(?)xx]
85. [<][86][xx(x)1xx]
86. [<][83][x(x)x1xx]
87. [V][88][(0)00 -> (1)00]
88. [>][89][1(0)0]
89. [>][90][10(0)]
90. [V][100][10(1)]
F1:
91. [<][92][(x)xx]
92. [?][95,93][(?)xx]
93. [<][94][xx(x)1xx]
94. [<][91][x(x)x1xx]
95. [V][96][(0)00 -> (1)00]
96. [>][97][1(0)0]
97. [V][98][1(1)0]
98. [>][99][11(0)]
99. [V][100][11(1)]
Ex:
100. [>][101][(x)xx]
101. [?][113,102][(?)xx]
102. [>][103][1(x)x]
103. [?][105,104][1(?)x]
104. [>][100][11(x)]
105. [>][106][10(x)]
106. [?][107,100][10(?)]
Ex_q7:
107. [>][108][(x)xx]
108. [?][113,109][(?)xx]
109. [>][110][1(x)x]
110. [>][111][1x(x)]
111. [?][112,8][1x(?)]
112. [<][103][1(x)0]
Cl:
113. [<][114][1x(x)]
114. [?][115,120][1x(?)]
115. [<][116][1(x)0]
116. [?][118,117][1(?)0]
117. [X][118][1(0)0]
118. [<][119][(1)00]
119. [X][113][(0)00]
120. [<][121][1(x)1]
121. [<][122][(1)x1]
122. [S][][(1)x1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment