Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Построение машины тьюринга

Читайте также:
  1. II. Расчет объема памяти информационно-логической машины (ИЛМ).
  2. Бинарное дерево. Построение бинарного дерева
  3. БЛОК-СХЕМА МАШИНЫ ТЬЮРИНГА
  4. Боковой увод и поворачиваемость машины
  5. Большое обсуждение стиральной машины
  6. В) Построение оценки эмпирической функции распределения и формирование классификационной шкалы
  7. Влияние эксплуатационных факторов на топливную экономичность машины

 

Машина Тьюринга – абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

 

В состав машины Тьюринга входит ограниченная слева и бесконечная справа лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

 

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

 

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены кактерминальные, и переход в любое из них означает конец работы, остановку алгоритма.

 

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Условие МТ3:

M2    
B1 0RB1 1SB0(1)
B2 1LB2 1SB0(2)

 

M4    
D1 0RD2 1SD0(1)
D1 1LD1 1SD0(2)

 

M3    
C1 1RC1 0RC2
C2 0SC0(1) 1SC0(2)

 

M4    
A1 0RA1 0SA2
A2 0SA1 1RA2

 

 


MT3    
B1 0LB1 1SB0(1)
B2 1LB2 1SBO(2)
D1 0RD2 1SD0(1)
D2 1LD1 1SD0(2)
C1 1RC1 0RC2
C2 0SC0(1) 1SC0(2)
A1 0RA1 0SA2
A2 0SC0 1RA2

 

MT3 MT3    
B1 0RB1 1SD1 1RF2
B2 1LB2 1SC1 0SB1
D1 0RD2 1SD0 1SC1
D2 1LD1 1SD0 1SA1
C1 1RC1 0RC2 0RC2
C2 0SA1 1SB1 1SF1
A1 ORA1 0SA2 0SA2
A2 0SA1 1RA2 1RA2

 


Дата добавления: 2015-07-16; просмотров: 47 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ| БЛОК-СХЕМА МАШИНЫ ТЬЮРИНГА

mybiblioteka.su - 2015-2024 год. (0.007 сек.)