Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆

Приклад 7 Завдання

Машина, яка обчислює функцію

Розв’язання

Початок:

y

x

↑ Стан 1

Кінцевий стан:

xy

↑

 

I

1

 

1L2

2

0L3

1L2

3

 

1L4

4

0R93

1R5

5

 

0R6

6

0R6

1R7

7

0R8

1R7

8

0L9

1L8

9

0L10

1L8

10

0L10

1L11

11

0R28

1R12

12

 

0R13

13

0R13

1R14

14

0R15

1R14

15

1L16

1R14

16

0L17

 

17

0L17

1L18

18

0R23

1R19

19

 

0R20

20

0R20

1R21

21

1L22

1R21

22

0C17

1L22

23

 

1R24

24

1R24

1L25

25

 

0R26

26

0L27

1R26

27

 

1C8

28

 

1R29

29

0R29

1R30

30

0R31

1R30

31

0L32

1R30

32

0L32

1C33

33

 

1L34

34

0L35

1L34

35

 

1L36

36

0R77

1R37

37

 

0R38

38

0R38

1R39

39

0L40

1R39

40

0L41

1L40

41

0L42

1L40

42

0L42

1L43

43

0R60

1R44

44

 

0R45

45

0R45

1R46

46

0R47

1R46

47

1L48

1R46

48

1L49

 

49

1L49

1L50

50

OR55

1L51

51

 

1L52

52

0R52

1L53

53

1L54

1L53

54

0C49

1L54

55

 

1L56

56

1R56

1L57

57

 

0R58

58

1L59

1R58

59

 

1C40

60

 

1R61

61

0R61

1R62

62

0R63

1R62

63

0R64

1R62

64

0R64

1C65

65

0L66

1L65

66

0R71

1R67

67

1R68

 

68

0L69

1R68

69

 

0L70

70

 

0L65

71

0L72

1R71

72

 

0L73

73

1L74

1L73

74

0R71

1R75

75

0L80

1R75

76

 

1C81

77

0R78

1R77

78

0L79

1R78

79

0L76

0L79

80

 

0L76

81

0L82

1L81

82

0R85

1R83

83

0R83

1R84

84

0L33

1R84

85

0R85

1R86

86

0L87

1R86

87

 

0L88

88

1L89

1L88

89

0R90

1R91

90

0L88

1R90

91

0L92

1R91

92

 

1C0

93

0R94

1R93

94

0R94

1R95

95

0L96

1R95

96

1C92

0L96

1-7 – видалення з однієї "I".

8-32 – послідовне коментуємо управо по стрічці, видаляючи при цьому палички з .

33-80 – виконуємо перемножування всіх (детально воно описане в машині, що будує ).

81-86 – йде перевірка, є ще що перемножити чи ні.

87-92 – множення закінчене, тепер треба змістити результат .

93-96 – реалізація випадку окремо.

Приклад 8

Завдання

Для функції rest(x,y)x побудувати машину Т’юринга, дослідити її на рекурсивність та побудувати нормальний алгоритм Маркова.

Розв’язання

Машина Тьюринга

Правила машини Т’юринга.

Правила описуються наступним чином. Є три стовпчика: перший - номер стану, другий – дії машини, якщо у поточній клітинці 0, третій - дій машини, якщо у клітинці 1. Дії записуються наступним чином. Спершу йде той символ, який буде записуватись в поточну клітинку. Потім - символ, який визначає напрямок руху каретки. І останній - стан, в який машина переходить. Так, наприклад, 0<68 означає, що у клітинку записується 0, каретка рухається вліво на одну клітинку і машина переходить у стан 68. Літера S означає кінець роботи машини.

№

I

0

0L68

1

0L2

1L1

2

0R60

1L2

3

0R10

0R4

4

0R5

1R4

5

0R6

1R5

6

1L7

1R6

7

0L8

1L7

8

0L9

1L8

9

1R3

1L9

10

1R11

11

0L12

12

0L13

1L12

13

0L13

1L14

14

0R15

1L14

15

1R16

16

1R35

17

0R18

1R17

18

0R18

1R19

19

1R20

1R19

20

0L24

0L21

21

0L22

1L21

22

0L22

1L23

23

1R16

1L23

24

0L25

1L24

25

0L25

1L26

26

1R27

1L26

27

0R28

1R27

28

0R28

1R29

29

0L34

0L30

30

0L31

lLЗО

31

0L31

0R32

32

0R32

1R33

33

1R29

1R33

34

0R10

1L36

35

0R37

1L36

36

0R17

37

0R37

1R38

38

1R53

1R38

39

0R40

1L39

40

0R41

0R40

41

0L42

42

0L42

1R43

43

0R44

44

1R45

45

0R45

1R46

46

0L49

1L47

47

0L48

48

0L48

1R44

49

0L50

50

0L50

1R51

51

1R52

52

0L89

53

0L54

1L39

54

0L55

1L54

55

ОL55

1L56

56

ОR58

1R57

57

0L55

58

1R59

59

0R59

0R40

60

1R61

61

0R62

1LЗ

62

0L63

0R62

63

0L63

1R64

64

0S0

65

1R66

66

0R67

67

1R52

68

1L69

69

0R70

1R71

70

0S0

1R70

71

0L72

lL71

72

0R73

1L72

73

0R80

0R74

74

0R75

1R74

75

0R76

1R75

76

1L77

1R76

77

0L78

1L77

78

0L79

1L78

79

1R73

1L79

80

0R87

0R81

81

0R82

1R81

82

0R83

1R82

83

1L84

1R83

84

0L85

1L84

85

0L86

1L85

86

1R80

1L86

87

0R88

1R87

88

0L1

1R88

89

0R90

1R89

90

1R91

91

1L92

92

1L93

93

0L94

94

0R95

1L94

95

1R96

96

0S0

0L97

97

0L98

1L97

98

0R99

1L98

99

1R100

100

0R135

1R101

101

0R117

0R102

102

0R103

1R102

103

0R103

1R104

104

0R105

1R104

105

0R106

1R105

106

0R106

1R107

107

0L112

0R108

108

0R109

1R108

109

lL110

1R109

110

0L111

lL110

111

1R107

lL111

112

0L113

1L112

113

0L115

1L114

114

0L115

1L114

115

0L116

1L115

116

1R101

1L116

117

0R118

1R117

118

0R119

1R118

119

1R120

1R119

120

0L121

1R120

121

0L122

122

0L123

1L122

123

0L125

1L124

124

1R96

1L124

125

0L126

0L125

126

0R127

0L126

127

1R128

128

0R128

1R129

129

0L132

1L130

130

0L131

131

0L131

1R127

132

0L133

133

0L133

1R134

134

0S0

135

0R136

0R135

136

0R137

0R136

137

0L138

0R137

138

0L138

1R134

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]