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