 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Пример 7
Рис. 3.7. Диаграмма переходов машины «
– четное число»
Машина с диаграммой на рис. 3.7 вычисляет предикат « – четное число»: головка достигает конца числа в состоянии q2, если число единиц четно, и в состоянии q3, если число единиц нечетно, после чего она перемещается в исходное положение в состоянии q4 либо q5 и печатает Т или F соответственно.
Для того, чтобы этот предикат вычислялся с восстановлением, достаточно в петлях q4 и q5 не стирать, а сохранять единицы, т.е. заменить команды 
на команды 
.
Так как машина Тьюринга с алфавитом А* = {T, F} и командами q1 T 
qz F E и q1 F qz T E вычисляет отрицание логической переменной, то из вычислимости всюду определенного предиката 
следует вычислимость 
.
Пусть функция 
задана описанием: «если истинно, то 
, иначе 
». (Под «иначе» имеется в виду «если ложно»; если не определено, то также не определено.) Функция называется развилкой или условным переходом к 
и 
по условию .
Теорема 9. Если функции , и предикат вычислимы по Тьюрингу, то развилка и по условию также вычислима.
Доказательство. Пусть Т1 – машина с состояниями 
и системой команд 
, вычисляющая g1; Т2 – машина с состояниями 
и системой команд 
, вычисляющаяся g2; Тр вычисляет с восстановлением . Тогда машина Т, вычисляющая развилку и по условию , – это композиция Тр и машины Т3, система команд 
которой имеет следующий вид:
Т 
F 
.
Первые две из новых команд передают управление системе команд или в зависимости от значения предиката . Третья команда введена для того, чтобы Т3 имела одно заключительное состояние q2z. Отсутствие символа ленты в этой команде означает, что она выполняется при любом символе.
Построенную в теореме 9 машину Т будем называть развилкой машин Т1 и Т2 по условию Тр и обозначать Траз(Т1, Т2, ТР), а также изображать блок-схемой (рис. 3.8).
Рис. 3.8. Блок-схема развилки машин Траз(Т1, Т2, ТР).
Пусть функция задана описанием: «пока истинно , вычислять , иначе ». Функция называется повторением или циклом от и по условию .
Теорема 10. Если функции , и предикат вычислимы по Тьюрингу, то цикл и по условию также вычислим.
Доказательство. Сохраняя обозначения из доказательства предыдущей теоремы, введем машину Т, вычисляющую и по условию , – это композиция Траз и машины Т3, система команд которой имеет следующий вид:
Т F 
.
Первые две из новых команд передают управление системам команд или в зависимости от значений предиката . Третья команда отождествляет начальную вершину qp1 диаграммы машины Траз с конечной вершиной q1z диаграммы Т1 (т.е. после вычисления переходим к новой проверке условия ). Конечное состояние машины Т есть состояние q2z.
Построенную в теореме 10 машину Т будем называть циклом машин Т1 и Т2 по условию Тр и обозначать Тцикл(Т1, Т2, ТР), а также изображать блок-схемой (рис. 3.9).
Рис. 3.9. Блок-схема цикла машин Тцикл(Т1, Т2, ТР).
Пример 8. В примере 4 было описано построение машины Т+ для сложения двух чисел. На рис. 3.10 приведена диаграмма машины Т++ для сложения n чисел (n = 1, 2, …). Цикл из состояний q1, q2, q3 – это немного модифицированная и «зацикленная» машина Т+, в которой заключительное состояние совмещено с начальным. Сумма, полученная в очередной итерации цикла, является первым слагаемым следующего цикла. Состояние q4 реализует развилку. В нем проверяется условие – есть ли второе слагаемое. Если да (о чем говорит наличие маркера *), то происходит переход к следующему циклу; если нет (о чем говорит 
после единицы), то машина выходит из цикла.
Рис. 3.10. Диаграмма переходов машины Т++.
Благодаря вычислимости композиции, развилки и цикла, словесные описания и язык блок-схем можно сделать достаточно точным языком описания работы машин Тьюринга. Каждый блок – это множество состояний, в котором выделены начальное и заключительное состояния и система команд. Переход к блоку – это обязательно переход в его начальное состояние. Машина Тьюринга, описываемая блок-схемой, – это объединение состояний и команд, содержащихся во всех блоках. В частности, блоком может быть одно состояние. Блоки, вычисляющие предикаты, обозначим буквой Р.
Пример 9. На рис. 3.11 приведена блок-схема машины Тьюринга 
, осуществляющая умножение двух чисел: 
. Ее заключительное состояние – q03.
Рис. 3.11. Блок-схема машины .
Блоки реализуют следующие указания и вычисления:
P1 – вычислить с восстановлением предикат «оба сомножителя больше нуля»;
Т1 – стереть все непустые символы справа;
Т2 – установить головку у ячейки, следующей (вправо) за маркером *, маркер * заменить на ~;
Ткоп – см. пример 5, в котором команду 
надо заменить на команду 
~ 
; эта машина 
раз копирует 
; после i -го цикла она останавливается в конфигурации 
(~ 
~ 
;
Т3 – вернуть головку к крайнему слева непустому символу. После -го цикла этим символом оказывается ~ (или *, если а = 1) и тогда происходит выход из цикла и переход к 
;
работает как Т++ с той разницей, что числа, которые она суммирует, разделены двумя видами маркеров: ~ и *. Для этой цели ко всем командам с маркером * в левой части добавлены такие же команды для маркера ~.
Поиск по сайту: