Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
 2017-06-11 |
 392 |
из
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 с.
|
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!