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

Пример 7

Читайте также:
  1. X. примерный перечень вопросов к итоговой аттестации
  2. В некоторых странах, например в США, президента заменяет вице-
  3. Вания. Одной из таких областей является, например, регулирова-
  4. Виды знания. Контрпример стандартному пониманию знания
  5. Власть примера. Влияние с помощью харизмы
  6. Внешний долг (внешняя задолженность): пример России
  7. Вопрос 11. Герои романтических поэм М. Ю. Лермонтова (на примере одного произведения).
  8. Вопрос 2 Проверка и оценка в задачах со случайными процессами на примере решения задач экозащиты, безопасности и риска.
  9. Вопрос 8. Герои романтических поэм А. С. Пушкина (на примере одного произведения).
  10. Второй пример абстрактного синтеза
  11. Выбор канала распределения. Факторы, влияющие на выбор канала распределения.. Пример выбора канала распределения.
  12. Выравнивание производства в системы управления производством на примере фирмы «Тойота».

Рис. 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) и тогда происходит выход из цикла и переход к ;

работает как Т++ с той разницей, что числа, которые она суммирует, разделены двумя видами маркеров: ~ и *. Для этой цели ко всем командам с маркером * в левой части добавлены такие же команды для маркера ~.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.)