Навигация:

Главная Случайная страница Обратная связь ТОП Интересно знать Избранные Новые материалы

Топ:

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...

Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...

Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...

Интересное:

Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...

Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...

Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...

Дисциплины:

Автоматизация Антропология Археология Архитектура Аудит Биология Бухгалтерия Военная наука Генетика География Геология Демография Журналистика Зоология Иностранные языки Информатика Искусство История Кинематография Компьютеризация Кораблестроение Кулинария Культура Лексикология Лингвистика Литература Логика Маркетинг Математика Машиностроение Медицина Менеджмент Металлургия Метрология Механика Музыкология Науковедение Образование Охрана Труда Педагогика Политология Правоотношение Предпринимательство Приборостроение Программирование Производство Промышленность Психология Радиосвязь Религия Риторика Социология Спорт Стандартизация Статистика Строительство Теология Технологии Торговля Транспорт Фармакология Физика Физиология Философия Финансы Химия Хозяйство Черчение Экология Экономика Электроника Энергетика Юриспунденкция

Практическая работа №4 Количество часов, отводимых на выполнение практической работы 2ч

2017-06-11

424

0.00 из 5.00 0 оценок

Заказать работу

Содержание

⇐ ПредыдущаяСтр 5 из 5

Тема: Решение задач по теме «Машины Тьюринга»

Цель: наработка навыка конструирования машин Тьюринга и применения машин к словам.

Общие теоретические сведения:

Машина Тьюринга включает в себя:

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 с.

Тишин В. В. Дискретная математика в примерах и задачах. — СПб.: БХВ-Петербург, 2008. — 352 с: ил. — (Учебная литература для вузов)

⇐ Предыдущая 1 2 3 45
Поделиться с друзьями:

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...