КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Функции для построения схем(программ) машин Тьюринга
|
|
|
|
Конструирование машин Тьюринга
Начальные конфигурации машины Тьюринга
Применение машин Тьюринга к словам
Задания к выполнению работы
1. Определить, какую функцию вычисляет машина Тьюринга с программой команд, представленных в таблице:
| Состояние машины | 
| 
|
| 
| 
|
2. Убедиться, что машина с алфавитом 
и программой
| Состояние машины |
|
|
|
| 
| 
|
| 
| 
|
| 
| 
|
| 
| 
|
| 
| |
| 
|
|
|
| |
| 
| 
|
|
| |
| 
| 
|
каждое слово длины 
алфавита перерабатывает в слово длины r (r – остатокот деления числа на 3).
3.Рассмотреть, как работает машина Тьюринга, заданная функциональной схемой (табл.10.5),
Таблица 10.5
| Состояние машины Тьюринга | Последовательность букв внешнего алфавита (слова) | ||
|
| 
| 
| |
| 
| 
| 
|
| 
| 
| 
|
| 
| 
| 
|
| 
| 
| 
|
и показать в соответствии с вариантом задания все конфигурации тактов работы машины до их повторения или останова, если начальная конфигурация имеет вид, определенный табл. 10.6.
Таблица 10.6
| № варианта | Начальная конфигурация | № варианта | Начальная конфигурация |
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
| ||
| 
|
1. Построить в соответствии с заданным вариантом машину Тьюринга, реализующую алгоритм вычисления функций, представленных в табл. 10.7. Записать все конфигурации тактов работы машины при 
равном номеру варианта задания.
Таблица 10.7
| № варианта | 
| № варианта |
| № варианта |
|
| 
| ||||
| 
| 
| |||
| 
| 
| |||
| 
| 
| |||
| 
| 
| |||
| 
| 
| |||
| 
| 
| |||
| 
| 
| |||
| 
| 
| |||
| 
| 
|
2. Построить машину Тьюринга, которая из подряд записанных единиц оставляла бы на ленте единицы, также записанных подряд, если 
, и работала бы вечно, если 
или 
.
3. Построить машину Тьюринга, которая применима ко всем словам в алфавите 
и делает следующее: любое слово 
, где 
или 
(
), преобразует в слово 
.
4. Построить машину Тьюринга для вычисления функции
5. Построить машину Тьюринга для вычисления функции
6. Записать в алфавите программу работы машины Тьюринга для вычисления функции
|
|
|
|
|
Дата добавления: 2017-02-01; Просмотров: 125; Нарушение авторских прав?; Мы поможем в написании вашей работы!