Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Реферат'
Катализаторы - вещества, изменяющие скорость химической реакции, которые могут участвовать в реакции, входить в состав промежуточных продуктов, но не...полностью>>
'Документ'
Современные дидактические средства математического развития дошкольников: значение и место в образовательном процессе (на примере развивающих игр, бл...полностью>>
'Методичні рекомендації'
З метою удосконалення механізму адміністрування відшкодування податку на додану вартість та налагодження ефективного контролю за станом та порядком о...полностью>>
'Документ'
Audi A8 3.2 FSI Quattro c двигателем 3.2 литра и автоматической коробкой передач Tiptronic - надежный, динамичный и стильный автомобиль. Этот автомоб...полностью>>

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

Главная > Реферат
Сохрани ссылку в одной из сетей:

Федеральное агентство по образованию

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

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

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

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

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

Михайлов Сергей, группа 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



Скачать документ

Похожие документы:

  1. Учебная программа для высших учебных заведений по специальности 40 03 01 «искусственный интеллект» Составители

    Программа
    Ю.Г. Приходько - доцент кафедры интеллектуальных информационных технологий Белорусского государственного университета информатики и радиоэлектроники, кандидат технических наук,
  2. Рабочая программа Наименование дисциплины дискретная математика по направлению подготовки

    Рабочая программа
    Цель преподавания дисциплины - обучение студентов принципам построения информационных систем, автоматизирующих операции с данными, и практическим навыкам работы с этими системами.
  3. Рекомендации по проведению занятий 10

    Контрольные вопросы
    Могилев, Александр ВладимировичПрактикум по информатике: Учебное пособие для студентов высших учебных заведений/ Н.И. Пак, Е.К. Хеннер; Хеннер, Евгений Карлович.
  4. Учебно-методический комплекс по дисциплине 230100 Теория алгоритмов Направление подготовки

    Учебно-методический комплекс
    Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Армавирская государственная педагогическая академия»
  5. Аннотации к программам дисциплин (модулей) (2)

    Программа
    Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: «Философия», «Политология», «Социология», «Культурология», «Мировая художественная культура», а также курсов по выбору, рекомендуемых

Другие похожие документы..