- •Министерство образования Республики Беларусь
- •Введение
- •Тема 1 булевы функции
- •Основные понятия по теме
- •Лабораторная работа №1
- •Вопросы для самоконтроля
- •Литература
- •Тема 2 нормальные формы булевых функций
- •Основные понятия по теме
- •Лабораторная работа №2
- •Вопросы для самоконтроля
- •Литература
- •Тема 3 минимизация булевых функций
- •Основные понятия по теме
- •Лабораторная работа №3
- •Лабораторной работе №4
- •Вопросы для самоконтроля
- •Лабораторной работе №5
- •Вопросы для самоконтроля
- •Лабораторная работа №6
- •Вопросы для самоконтроля
- •Литература
- •Тема 7 конечные автоматы
- •Основные понятия по теме
- •Лабораторная работа №7
- •Вопросы для самоконтроля
- •Литература
- •Тема 8 рекуррентные функции
- •Основные понятия по теме
- •Лабораторная работа №8
- •Лабораторная работа №9
- •Вопросы для самоконтроля
- •Литература
Лабораторная работа №9
I. Выяснить применима ли машина Тьюринга , задаваемой программой:
q0 q0R
q1 q1R
q0 q0R
q1 q1L
q0 q0
q1 q1R
К следующим словам:
q101
q101
q101
q101
q101
q101
q101
q101
q101
10)q101
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