Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Машина Поста
Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Всего команд шесть:
N. → J | сдвиг вправо |
N. ← J | сдвиг влево |
N. 1 J | запись метки |
N. 0 J | удаление метки |
N. ? J1, J0 | если в ячейке есть метка, то перейти к j1 строке программы, иначе перейти к j0 строке программы. |
N. Stop | остановка |
где N. — номер строки, J — строка на которую переходит управление далее.
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:
работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
работа может закончиться командой Stop;
работа никогда не закончится.
Пример: вычитание натуральных чисел P — Q
Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»
v
00111110111000
P Q
Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:
1. 0 - стираем левый символ у Q
2. →
3. ? 5, 4
4. Stop - стоп если затерли Q=0
5. ←
6. ? 7, 5 - цикл поиска P
7. 0 - стираем правый символ у P
8. →
9. ? 1, 8 - ищем Q
Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)
- Учебно-методический комплекс дисциплины для обучающегося «Информатика» для всех специальностей
- Силлабус дисциплины для студентов
- 1. Информация о дисциплине
- 2. Краткое описание дисциплины.
- 3. Пререквизиты дисциплины
- 4. Постреквизиты дисциплины
- 5. Календарно-тематический план.
- 6. Литература для изучения
- 7. Критерии оценки
- 8. Требования преподавателя
- 2. Тезисы лекций
- Тема 1. Информатика – предмет и задачи. Основные категории и понятия информатики
- Роль информатики в информационном обществе
- Тема 2. Начала общей теории информации. Понятие информации.
- Тема 3. Арифметические основы информатики. Формы представления информации. Системы счисления. Действия в различных системах счисления.
- Тема 4. Логические основы информатики
- Тема 5 . Архитектура персонального компьютера. Информационно-логические основы построения
- Тема 6. Алгоритмические основы информатики
- 6.1 Понятие алгоритма, его основные свойства
- 6.2. Машина Тьюринга и машина Поста
- Устройство машины Тьюринга
- Описание машины Тьюринга
- Тема 7.Основные конструкции программирования. Структурное программирование. Процедурное программирование. Объектно-ориентированное программирование.
- Тема 8. Состояние и тенденции развития программного обеспечения
- Тема 9. Операционные системы. Роль операционной системы в организации работы пользователя на персональном компьютере. Операционные системы и их основные функции
- Классификация ос
- Тема 10. Операционная система ms-dos
- Тема 11. Операционные системы Windows. Концепция операционных систем Windows.
- Объекты Windows
- Тема 12. Сервисное программное обеспечение. Общие сведения об архивации файлов. Программы-архиваторы.
- Программы архивирования данных
- Тема 13. Прикладные программные продукты. Классификация прикладного программного обеспечения.
- Тема 14. Тестовый процессор ms Word
- 14.1. Система обработки текстов (основные возможности, классификация). Ms Word. Элементы экрана.
- Установка основных параметров шрифта
- 14.2. Оформление текста. Работа с таблицей. Вставка файла, рисунка. Редактор формул ms Equation.
- Математические операторы и операторы сравнения
- Тема 15. Табличный процессор ms Excel
- 15.1. Назначение основные возможности Excel. Элементы экрана
- Добавление пиктограмм в одно из пиктографических меню
- Рабочие таблицы Excel предназначены для анализа данных, представленных в строках и столбцах. Они хранятся в файлах, которые называются рабочими книгами.
- Правка Перейти адрес клетки переход в нужную клетку
- 15.2. Режим вычисления. Оформление таблиц. Оформление таблиц. Печать. Диаграмма.
- 15.3. Работа с большими таблицами. Справочная система ms Excel.
- Тема 16. Использование спп Power Point для создания бизнес плана. Информационные системы (ис). Создание презентации. Оформление.
- Тема 17. Основы технологии работы в субд ms Access
- Тема 18. Сеть Internet и ее применение. Основные понятия Internet. Программа Internet Explorer. Поиск информации. Поисковые системы. Почта.
- Тема 19. Компьютерные вирусы и приемы борьбы с ними (понятие компьютерного вируса, средства защиты, методика защиты).
- Лабораторная работа №4 Создание прайс-листа счёта
- Лабораторная работа №5 Статистические расчеты Microsoft Excel.
- Пуск – Программы - Microsoft Access
- 2.1.1 Запрос, отбирающий данные из одной таблицы по условию
- 2.2 Запросы, которые отбирают данные из нескольких таблиц
- 2.3 Модификация данных с помощью запросов
- 2.3.1 Запросы, которые изменяют значение группы записей
- Тема: Создание форм
- 3.1 Создание форм для просмотра и ввода данных
- 3.2.Создание форм с подчиненной формой
- Краткое описание семинарских и практических занятий (планы, задания для проведения семинарских и практических занятий, срсп, срс)
- Задания для самопроверки и подготовки к экзамену, в том числе тесты
- В) объединение
- 6. Перечень основной и дополнительной литературы, в том числе на электронных носителях
- Дополнительная литература
- Справочная литература
- Нормативная литература
- Интернет-источники
- Глоссарий