Базовые программы для машины тьюринга реферат по дисциплине «Дискретная математика»
Вид материала | Реферат |
- Темы курсовой работы по дисциплине "дискретная математика" (Приложение к рабочей программе, 128.96kb.
- Джеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон, 42.79kb.
- Программа по дисциплине дискретная математика, 32.4kb.
- Учебная программа для специальности: (рабочий вариант) 1-310301-02 Математика (научно-педагогическая, 120.64kb.
- Сложность вычислений, 29.79kb.
- Методические указания к выполнению курсового проекта, курсовой работе, расчетно-графической, 346.86kb.
- Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
- Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
- Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
- Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Санкт-Петербургский государственный
инженерно-экономический университет»
Кафедра информационных систем в экономике
Михайлов Сергей, группа 3681
БАЗОВЫЕ ПРОГРАММЫ ДЛЯ МАШИНЫ ТЬЮРИНГА
Реферат по дисциплине «Дискретная математика»
Руководитель: Сергеев А.Н.
Санкт-Петербург
2010
Программа для машины Тьюринга записывается в таблицу. Строки –это символы внутреннего алфавита состояний машины Тьюринга. Столбцы – это символы внешнего алфавита. Ввод команд программы производится путём заполнения соответствующих ячеек таблицы. Используется следующий формат ввода: <символ> <сдвиг> <состояние>,
где <символ> – символ внешнего алфавита, который буден записан в обозреваемую ячейку;
<сдвиг> – один из символов Л, П или _ (пустой символ), означающих перевод каретки влево, вправо или отсутствие сдвига;
<состояние> – символы внутреннего алфавита состояний, в который переходит машина Тьюринга по окончании обозревания текущей ячейки.
Например, команда: ! П 2 – означает напечатать символ ! в обозреваемую ячейку, сдвиг каретки вправо и переход в состояние 2.
Вид используемой программы:

1.Перенос нуля (A) : 0s

Реализация:
Начальное состояние

Промежуточное состояние

Конечное состояние

Последним действием будет переход каретки влево и выход из алгоритма
2. Перенос слова (


Реализация:
Начальное состояние

Промежуточное состояние

Конечное состояние

Последним действием будет переход каретки вправо и выход из алгоритма
3. Правый сдвиг (Б+) : 0s

Реализация:
Начальное состояние

Конечное состояние

Последним действием будет переход каретки вправо и выход из алгоритма
4. Левый сдвиг (Б


Реализация:
Начальное состояние

Конечное состояние

Последним действием будет переход каретки влево и выход из алгоритма
5. Транспозиция (Т) :
01x0s

Реализация:
Начальное состояние

Промежуточное состояние


Конечное состояние

Последним действием будет переход каретки влево и выход из алгоритма
6. Циклический сдвиг (Цn) :
0s

Реализация:
Начальное состояние

Промежуточное состояние


Конечное состояние

Последним действием будет переход каретки вправо и выход из алгоритма
7. Копирование (Kn) :
0s

Реализация:
Начальное состояние

Промежуточное состояние


Конечное состояние

Последним действием будет переход каретки влево и выход из алгоритма
8. Разветвление (Ф) :

Реализация:
Возможности используемой программы не позволяют внедрение двух значений для завершающего состояния.
Алгоритм выглядит следующим образом

9. Вычитание (В


Реализация:
Начальное состояние

Конечное состояние

Последним действием будет переход каретки влево и выход из алгоритма
10. Удаление единиц слева (У) :
01x101x20…0s

Реализация:
Начальное состояние

Промежуточное состояние

Конечное состояние

Последним действием будет переход каретки влево и выход из алгоритма
Используемая программа:
Машина Тьюринга v1.1.12.41