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

Правила работы машины

Читайте также:
  1. A. Различаем правила и стратегии.
  2. AT СТАЦИОНАРНАЯ И AT ОПЕРАТИВНАЯ. ПОЗЫ AT. ПРАВИЛА ВЫПОЛНЕНИЯ AT
  3. I. Итоговая государственная аттестация включает защиту бакалаврской выпускной квалификационной работы
  4. I. Назначение и принцип работы зубофрезерных станков, работающих червячной фрезой
  5. I. Перед началом работы.
  6. I.1 Этапы работы над документом
  7. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Машина работает дискретно (пошагово). На каждом шаге происходит переход от одной конфигурации к другой. Перед началом работы машина находится в начальной конфигурации: СЗУ обозревает первую букву слова, машина находится в начальном состоянии q1. СЗУ считывает букву, находящуюся в обозреваемой ячейке. УУ обращается к программе машины: находит клетку, соответствующую считанной букве и состоянию машины.

Пусть в этой клетке находится тройка (a;q;s); тогда буква а заносится в обозреваемую ячейку, машина переходит в состояние q, а СЗУ совершает сдвиг на одну ячейку влево, если s=-1, на одну ячейку вправо, если s=+1, и остается на месте, если s=0. На этом завершается работа машины на первом шаге, и она готова к выполнению следующего аналогичного шага и т.д.

Работа машины продолжается до тех пор, пока в каком-то из шагов машина не придет в состояние q0. Устройство управления в этом случае останавливает машину. Возникшая конфигурация называется заключительной, а полученное слово - результатом применения машины к исходному слову.

Если И - исходное слово, Т - машина, то через Т(И) обозначается результат.

Определение. Говорят, что машина Т не применима к слову И, если в процессе применения её к слову она ни на каком из шагов не приходит в заключительное состояние q0.

Пример. Дана машина Тьюринга, складывающая натуральные числа, записанные в унарной системе счисления (напомним, что, например 510=+||унар). Программа этой машины задана таблицей:

Рисунок 18.1.

алфавит q1 q2 q3
| |q1+1 q3-1 |q3-1
+ |q1+1    
q2-1   q0+1

Выписать последовательно возникающие при работе этой машины конфигурации на исходном слове И=+|| (т.е. мы будем складывать два числа: 2 и 3).

Как видно из таблицы, у машины четыре состояния q0; q1, q2, q3 внешний алфавит состоит из трех символов | - единица; + - сложение; - пустой символ.

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

Изобразим схематично ленту для записей и слово И=+||, записанное на ней, стрелкой обозначено СЗУ, рядом со стрелкой - состояние машины.

Рисунок 18.2.

  | | + | | |  

↑(q1)

Перед началом работы машины СЗУ обозревает первую букву ячейки. УУ обращается к программе: буква |, состояние q1- переводит букву | в букву |, состояние q1 переводит в состояние q1 и делает шаг вправо (+1).

Рисунок 18.3.

  | | + | | |  

↑(q1)

СЗУ обозревает вторую ячейку. УУ обращается к программе: буква |, состояние q1 переводит | в |, q1 в q1 и делает шаг вправо (+1).

Рисунок 18.4.

  | | + | | |  

↑(q1)

буква +, состояние q1 - переводит + в |, q1в q1 и +1.

Рисунок 18.5.

  | | | | | |  

↑(q1)

буква |, состояние q1 - переводит | в |, q1 в q1 и +1.



Рисунок 18.6.

  | | | | | |  

↑(q1)

  | | | | | |  

↑(q1)

  | | | | | |  

↑(q1)

буква , состояние q1- переводит в , состояние q1 в q1 и -1.

Рисунок 18.7.

  | | | | | |  

↑(q2)

буква |, состояние q2 - переводит | в , состояние q2 в q2 и -1.

Рисунок 18.8.

  | | | | |  

↑(q3)

буква |, состояние q3 - переводит | в |, q3в q3 и -1.

Рисунок 4.1.9.

  | | | | |  

↑(q3)

  | | | | |  

↑(q3)

  | | | | |  

↑(q3)

  | | | | |  

↑(q3)

  | | | | |  

↑(q3)

буква , состояние q3, - переводит в , q3 в q0.

Рисунок 18.10.

  | | | | |  

↑(q0)

Машина пришла в заключительное состояние q0.

Результат работы машины:

Т(И) = Т( || + ) =

Nbsp;


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


<== предыдущая страница | следующая страница ==>
Описание машины Тьюринга| Композиция машин

mybiblioteka.su - 2015-2021 год. (0.028 сек.)