Лабораторная работа №9
I. Выяснить применима ли машина Тьюринга , задаваемой программой:
q 0 q 0R
q 1 q 1R
q 0 q 0 R
q 1 q 1L
q 0 q 0
q 1 q 1R
К следующим словам:
q 1
0
1
q 1 0 1
q 1 0 1
q 101
q 1 0 1
q 10 1
q 1 01
q 1 0 1
q 1 0 1
10)q 1 0 1
II. Построить машину Тьюринга, вычисляющую следующую функцию.
10)
11)
12)
13)
14)
15)
16)
17)
18)
19)
20)
21)
22)
23)
24)
25)
26)
27)
28)
29)
30)
Вопросы для самоконтроля
1 Что Вы понимаете под машиной Тьюринга?
2 Из каких частей состоит машина Тьюринга?
3 Дайте определение машинного слова.
4 Какая функция называется числовой?
5 Какая функция называется частично-числовой?
6 Дайте определение функции, вычислимой по Тьюрингу.
7 Какие функции называются простейшими?
8 Дайте определение операций суперпозиции, примитивной рекурсии и минимизации.
9 Сформулируйте тезис Черча.
10 Сформулируйте тезис Тьюринга.
11 Какая связь между функциями вычислимых по Тьюрингу и частично рекурсивными функциями?
Литература
1 Яблонский, С.В. Введение в дискретную математику [Текст]: учебное пособие для вузов по специальности «Прикладная математика»/ С.В.Яблонский. – М.: Наука, 1979. – 272с.
Учебное издание
Семенчук Владимир Николаевич
ДИСКРЕТНАЯ МАТЕМАТИКА
ПРАКТИЧЕСКОЕ ПОСОБИЕ для студентов 1 курса специальности 1–31 03 03 – «Прикладная математика»
Редактор В.И. Шкредова
Корректор В.Н. Калугина
Лицензия № 02330/0133208 от 30.04.04.
Подписано в печать __________. Формат 60х84 1/16.
Бумага писчая № 1. Гарнитура «Таймс» . Усл. п. л._____.
Уч.-изд.л.______ . Тираж 120 экз. Заказ №__________.
Отпечатано с оригинала-макета на ризографе
учреждения образования
«Гомельский государственный университет
имени Франциска Скорины»
Лицензия № 02330/0056611 от 16.02.04.
246019, Г. Гомель, ул. Советская, 104