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

Вид материалаРеферат
Подобный материал:
Федеральное агентство по образованию


Государственное образовательное учреждение

высшего профессионального образования

«Санкт-Петербургский государственный

инженерно-экономический университет»


Кафедра информационных систем в экономике


Михайлов Сергей, группа 3681


БАЗОВЫЕ ПРОГРАММЫ ДЛЯ МАШИНЫ ТЬЮРИНГА


Реферат по дисциплине «Дискретная математика»


Руководитель: Сергеев А.Н.


Санкт-Петербург

2010


Программа для машины Тьюринга записывается в таблицу. Строки –это символы внутреннего алфавита состояний машины Тьюринга. Столбцы – это символы внешнего алфавита. Ввод команд программы производится путём заполнения соответствующих ячеек таблицы. Используется следующий формат ввода: <символ> <сдвиг> <состояние>,


где <символ> – символ внешнего алфавита, который буден записан в обозреваемую ячейку;

<сдвиг> – один из символов Л, П или _ (пустой символ), означающих перевод каретки влево, вправо или отсутствие сдвига;

<состояние> – символы внутреннего алфавита состояний, в который переходит машина Тьюринга по окончании обозревания текущей ячейки.


Например, команда: ! П 2 – означает напечатать символ ! в обозреваемую ячейку, сдвиг каретки вправо и переход в состояние 2.


Вид используемой программы:




1.Перенос нуля (A) : 0s01x => 0s01x0

Реализация:

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




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




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





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


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

Реализация:

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




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




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



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


3. Правый сдвиг (Б+) : 0s1x0 => 01x0s0

Реализация:

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




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



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


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

Реализация:

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




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




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


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

01x0s1y0 => 01y0s01x0

Реализация:

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




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







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



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


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

0s1x101x201x30…01xn-101xn => 0s01x201x30…01xn01x1

Реализация:

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




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






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





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


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

0s1x101x201x30…01xn => 0s11x101x201x30…01xn 01x101x201x30…01xn

Реализация:

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




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






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



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

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




Реализация:

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

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




9. Вычитание (В) : 0s1x0 => 00s01x-10

Реализация:

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




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



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


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

01x101x20…0s1xn0 => 0…0s01xn0

Реализация:

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




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




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




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


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

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