Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






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






В 1936 г. Тьюринг предложил модель абстрактной вычислительной машины, которая уточняла понятие алгоритма и оперировала с неограниченными ресурсами.

При желании можно создать реальную модель машины Тьюринга, но ресурсы такой машины становятся ограниченными.

Машина Тьюринга преобразует какие-либо объекты (например, строку символов, принадлежащих некоторому алфавиту) в некоторый искомый результат. При этом, хотя слова алгоритма машины Тьюринга могут иметь некоторый смысл, для теории алгоритмов это несущественно.

Для записи слов в машине Тьюринга используется бесконечная лента с последовательным доступом.

 

 


А – внешний алфавит машины Тьюринга.

Некоторый алфавит Р=р1, р2, …рn, характеризующий состояние машины в конкретный момент времени, называют внутренним алфавитом.

Состояние движения ленты описывается множеством возможных состояний -¥, …, dj, …, d0, d1, …, +¥.

Опишем принцип работы машины Тьюринга.

1) Чтение ai из ячейки d0, на которой позиционируется головка чтения/записи (R/W Head). Состояние машины в этот момент определяется pj.

Начальный кортеж: {ai, d0, p0}

2) В зависимости от значений ai и pj изменяется поведение машины:

{ax, dy, pz}

Данный кортеж означает: записать вместо ai символ aх, переместить головку чтения/записи в позицию dy, блоку управления перейти в состояние pz.

3) Если после второго шага состояние машины Тьюринга описывается исходным кортежем, то машина останавливается. Иначе – повтор пункта 2.

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

  p1 p2 pj pm
a0            
a1            
a2            
           
ai       {ax dy pz}    
           
an            

 

Если работа машины Тьюринга конечна во времени, то говорят, что она применима к исходному данному. Некоторое слово, записанное на ленте в момент остановки машины Тьюринга, будет результатом работы.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал