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

Оракульная МТ

Как и в предыдущем случае здесь две головки (обычная и оракульная), но и две ленты (обычная и оракульная). Во множестве состояний выделены два особых: состояние вопроса к оракулу qc и резюмирующее состояние qr. Обе головки управляются одним управляющим устройством. В начальный момент времени на обычной ленте записано входное слово I, начиная с ячейки с номером 1. Все остальные ячейки обеих лент пусты.

Работа оракульной машины Тьюринга (ОМТ) почти аналогична работе двухленточной МТ. Разница в следующем. Если управляющее устройство оказывается в состоянии qc, то поведение на следующем шаге зависит от фиксированной оракульной функции g:A*®A*.

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

Пусть y - слово, записанное на оракульной ленте, начиная с первой ячейки и до ячейки, над которой находится головка. Если головка находится левее ячейки с номером один, то полагается, что y - некоторая заранее оговоренная постоянная. За данный такт на оракульной головке записывается слово g(y), начиная с первой ячейки. Остальная часть ленты стирается, а головка обозревает ее первую ячейку.

То есть мы имеем как бы комбинацию обычной машины Тьюринга М и некоторого оракула g. Вообще говоря, для одной и той же задачи могут быть использованы разные оракулы. Поэтому можно искусственно вычленить ту часть программы ОМТ, которая касается работы обычной головки. Она ведь не касается действий оракульной головки. Именно эту часть программы называют программой ОМТ. Обозначим ее через M. В случае же рассмотрения конкретного оракула g всю программу целиком будем обозначать через Mg, и называть релятивизированной программой ОМТ.


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


Читайте в этой же книге: Введение | Некоторые необходимые определения и понятия. | Задачи, алгоритмы | Алгоритм | Нормальные алгорифмы Маркова (НАМ). | Одноленточная МТ | Кодировки входных данных. | О мерах сложности | Теоремы сравнения | Задача о кратчайшем (минимальном) остове (остовном дереве). |
<== предыдущая страница | следующая страница ==>
Недетерминированная МТ| Равнодоступная адресная машина (РАМ) и некоторые другие подходы.

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