Базовые программы для машины тьюринга реферат по дисциплине «Дискретная математика»

Вид материала

Реферат

Подобный материал:

• Темы курсовой работы по дисциплине "дискретная математика" (Приложение к рабочей программе, 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) : 0s01^x => 0s₀1^x0

Реализация:

Начальное состояние




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




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





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


2. Перенос слова () : 01^x00s => 001^x0s₀

Реализация:

Начальное состояние




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




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



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


3. Правый сдвиг (Б⁺) : 0s1^x0 => 01^x0s₀

Реализация:

Начальное состояние




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



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


4. Левый сдвиг (Б) : 01^x0 s => 0s₀1^x0

Реализация:

Начальное состояние




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




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


5. Транспозиция (Т) :

01^x0s1^y0 => 01^y0s₀1^x0

Реализация:

Начальное состояние




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







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



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


6. Циклический сдвиг (Ц_n) :

0s1^x101^x201^x30…01^xn-101^xn => 0s₀1^x201^x30…01^xn01^x1

Реализация:

Начальное состояние




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






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





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


7. Копирование (K_n) :

0s1^x101^x201^x30…01^xn => 0s₁1^x101^x201^x30…01^xn 01^x101^x201^x30…01^xn

Реализация:

Начальное состояние




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






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



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

8. Разветвление (Ф) :




Реализация:

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

Алгоритм выглядит следующим образом




9. Вычитание (В) : 0s1^x0 => 00s₀1^x-10

Реализация:

Начальное состояние




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



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


10. Удаление единиц слева (У) :

01^x101^x20…0s1^xn0 => 0…0s₀1^xn0

Реализация:

Начальное состояние




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




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




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


Используемая программа:

Машина Тьюринга v1.1.12.41