- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 16.2. Примеры построения машины Тьюринга
Пример:Рассмотрим решение задачи о добавлении 1 к унарному числу посредством машины Тьюринга. Внешний алфавит может быть задан множеством, где 1 соответствует заполненной секции, а– пустому знаку, причём заполненные следуют друг за другом подряд. Внутренний алфавит задаётся множеством, гдесоответствует рабочему состоянию ЛУ, а– остановке. Набор всех правил преобразования (логическая функция) может быть представлен функциональной схемой:
Составляется функциональная схема в виде таблицы таким образом, что знаки, обозначающие колонки и строки, определяют входные параметры ЛУ, а в ячейке таблицы на их пересечении стоит выходная команда. В частности, если головка машины обозревает секцию ленты со знаком 1 и машина находится в рабочем состоянии (), то результатом её работе на данном такте должно стать повторение 1 в данной секции и переход на одну секцию вправо R (при этом, как указывалось, лента сдвигается влево) – эта команда записывается как. Если же в обозреваемой секции, а состояние ЛУ, тобудет заменён 1, сдвига ленты производиться не будет и машина остановится –. При комбинации на входе, как и, машина находится в нерабочем состоянии – не происходит ни изменения конфигурации, ни движения – по этой причине такие комбинации в функциональных схемах в дальнейшем отображаться не будут.
Пусть начальной является конфигурация 11111. Тогда работа машины в соответствии с описанной логической функции будет происходить следующим образом:
Такт 1:обозревается 1, в ЛУ состояние; выходная команда, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо; следовательно, образуется промежуточная конфигурация 11111;
Такт 2:аналогичным образом осуществляется переход к конфигурации 11111;
Такт 3:переход к конфигурации 11111;
Такт 4: переход к конфигурации 11111(здесь для лучшего понимания правыйуказан в явном виде);
Такт 5:обозревается, в ЛУ состояние; выходная команда– вместов ячейку записывается 1, сдвига нет, работа прекращается; конечная конфигурация 111111.
Задача решена.
Пример:
Имеется запись многоразрядного целого числа в десятичной системе счисления; построить машину Тьюринга, которая обеспечивала бы вычисление значение.
Используем внешний алфавит , в котором символсоответствует пустому знаку. Внутренний алфавит, как и в предыдущей задаче, образуется двумя состояниями – рабочим () и остановкой () (). Исходное число, а также результат –– записываются в десятичной системе, причём, цифры размещаются по одной в соседних ячейках без пропусков. Функциональную схему представляется таблицей (для удобства строка будут соответствовать состоянию, а столбцы – знакам внешнего алфавита):
a |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 | |
Пусть начальной конфигурацией будет .
Такт 1:, т.е. 9 заменяется на 0 и головка сдвигается на разряд десятков – промежуточная конфигурация.
Такт 2:, т.е. 1 заменяется на 2 и произойдёт остановка с конечной конфигурацией, т.е. получен результат сложения 219+1.
Пусть начальной будет конфигурация .
Такт 1:, т.е. сформируется промежуточная конфигурация;
Такт 2:– возникнет конфигурация;
Такт 3:– возникнет;
Такт 4:– возникнети работа прекращается.
Таким образом, описанный алгоритм действительно обеспечивает суммирование любого целого десятичного числа и единицы. Ясно также, что при необходимости произвести сложение не с единицей, а с каким-то целым , то данный алгоритм необходимо повторитьраз. Умножение целых чисел также может быть сведено к сложению числа с самим собой. Следовательно, машины Тьюринга обладают важным свойством – возможностью построения новой машины путём объединения уже имеющихся – такая операция называетсякомпозицией.
По своему устройству машина Тьюринга крайне примитивна. Она намного проще самых первых компьютеров. Примитивизм состоит в том, что у неё предельно прост набор элементарных операций, производимых головкой – считывание и запись, а также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а путём последовательного перемещения вдоль ленты. По этой причине даже такие простые действия как сложение или сравнение двух символов машина Тьюринга производит за несколько шагов, а обычные операции сложения и умножения требуют весьма большого числа элементарных действий. Однако машина Тьюринга была придумана не как модель (прототип) реальных вычислительных машин, а для того, чтобы показать принципиальную (теоретическую) возможность построения сколь угодно сложного алгоритма из предельно простых операций, причём сами операции и переход от одной к последующей машина выполняет автоматически.