Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
 2017-06-11 |
 389 |
из
5.00
|
Заказать работу |
|
|
|
|
Тема: Решение задач по теме «Машины Тьюринга»
Цель: наработка навыка конструирования машин Тьюринга и применения машин к словам.
Общие теоретические сведения:
Машина Тьюринга включает в себя:
1. Внешний алфавит - конечное множество символов 
. В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ Внешний алфавит - конечное множество символов 
обозначает пробел.
2. Внутренний алфавит - конечное множество символов 
. Для любой машины число состояний фиксировано. Два состояния имеют особое назначение 
- начальное состояние машины, 
- заключительное состояние (стоп-состояние).
3. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».
4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.
5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ
6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.
7. Работа машины Тьюринга:
8. Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии 
, считывает входной символ 
и по таблице работы совершает операцию сдвига 
, переходя в состояние 
, при этом входное слово заменяется на 
:
|
|
9. 
10. Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.
Задание на практическую работу:
Вариант №1
ВАРИАНТ 2
Технология работы:
Задание №1
Выбрать тестовое слово, подходящее к условия данной задачи.
Составить алгорит по которому данное слов преобразуется в желаемое.
Составить порограмму машины тьюрига.
Проверить правильность составления машины на контрольном слове
Ззадание №2
Данное слово разместить на ленте, установить УГ в указанное место. Поэтапно выполнять программу машины исходя из правил.
Контрольные вопросы:
1. Необходимость уточнения понятия алгоритма.
2. Машина Тьюринга.
3. Машина Тьюринга и современные ЭВМ.
4. Основная гипотеза теории алгоритмов (тезис Тьюринга).
5. Операции над машинами Тьюринга..
6. Вычислимость функций на машине Тьюринга.
7. Теорема Поста.
8. Алгебраически неразрешимые проблемы.
9. Неразрешимость проблемы самоприменимости.
10. Понятие сложности вычисления.
Список рекомендуемой литературы
1. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. — 2-е изд., стер. — М.: Издательский центр «Академия», 2008. — 448 с.
|
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!