ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. Теория вычислительных процессов

• Название: Теория вычислительных процессов
• Анкор: ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.doc
• Дата: 01.04.2018
• Размер: 2.17 Mb.
• Имя файла: ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.doc
• Тип: Документы; #17485
• страница: 12 из 20

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

Первый закон касается оператора выбора. Он гласит, что два процесса, определенные с помощью оператора выбора, различны, если на первом шаге они предлагают различные альтернативы или после одинакового первого шага ведут себя по-разному. Если же множества начального выбора оказываются равными и для каждой начальной альтернативы дальнейшее поведение процессов совпадает, то, очевидно, что процессы тождественны.

L1.(х:А Р(х)) = (у: В Q(у))  (А=В AND х А.Р(х) = Q(х))

Этот закон имеет ряд следствий:

L1A.СТОП (a P).

Доказательство.

ЛЧасть = (х: {} P) (х: {a} Р) = ПРЧасть, так как {} {a}.

L1B.(с Р) ≠ ( d Q), если с ≠d.

Доказательство. Так как, {с} ≠ {d}.

L1C.(с Р | d Q) = (d Q| с Р).

L1D.(с Р) = (с Q)  Р =Q.

Доказательство.Так как, {с} = {с}.

С помощью этих законов можно доказывать простые теоремы.

Пример 3.5. (мон шок мон шок СТОП) (мон СТОП).

Доказательство. Следует из L1B и L1A.

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

L2.Если F(X) - предваренное выражение, то:

(Y = F(Y))  (Y = X.F(X)).

Как прямое следствие получаем, что X.F(X) является решением соответствующего уравнения.

L2A.X.F(X) = F(X.F(X)).

Пример 3.6. Пусть ТА1 = (мон ТА2), а ТА2 = (шок ТА1). Требуется доказать, что ТА1 = ТАП.

Доказательство. ТА1 = (мон ТА2) =по определению ТА1

= (мон (шок ТА1)) по определению ТА2

Таким образом, ТА1 является решением того же рекурсивного уравнения, что и ТАП. Так как это уравнение предварённое, оно имеет единственное решение. Значит, ТА1 = ТАП.
Реализация процессов
Любой процесс Р, записанный с помощью введенных обозначений, можно представить в виде (х: В F(х)), где F—функция, ставящая в соответствие множеству символов множество процессов. Множество В может быть пустым (в случае P= СТОП), может содержать только одинэлемент (в случае префикса) или — более одного элемента (в случае выбора).

Таким образом, каждый процесс можно рассматривать как функциюF с областью определения В (множество начальных событий), и областью значения {F(й)  x B}.

Такой подход позволяет представить любой процесс как функцию в некотором подходящем функциональном языке программирования, например в ЛИСПе. Каждое событие из алфавита процесса представлено атомом ("мон"). При этом если символ не может быть начальным событием процесса, то результатом функции будет специальный символ "BLEEP". Например, для процесса (х: {} СТОП(х)) значением функции будет"BLEEP", что обозначим

СТОП =x. "BLEEP".

Если же аргумент является событием, возможным для процесса, результатом функции будет другая функция, определяющая последующее поведение процесса.

Пример 3.7. Функция, реализующая процесс (c Р) может иметь вид:

префикс(c, Р) = х. if x= с then Рelse "BLEEP".

Пример 3.8. Функция, реализующая двуместный выбор (c Р  d Q) может иметь вид:

выбор(c, d, Р, Q) = х. if x= с then Р else if x= d then Qelse "BLEEP".

Оказывается возможным прямое кодирование рекурсивных уравнений:

Пример 3.9. ТАП = префикс("мон", префикс("шок", ТАП)).
Протоколы
Протоколом поведения процесса называется конечная последовательность символов, фиксирующая события, в которых процесс участвовал до некоторого момента времени. Можно представить себе наблюдателя с блокнотом, который следит за процессом и записывает имя каждого происходящего события.

Будем обозначать протокол последовательностью символов, разделенной запятыми и заключенной в угловые скобки, например, протокол <х, у> состоит из двух событий — х и следующего за ним у, <x> - cостоит из одного события х,а протокол<> - пустой протокол.

Пример 3.10. Протокол простого торгового автомата ТАП в момент завершения обслуживания первых двух покупателей: <мон, шок,мон,шок>.

Протокол того же автомата перед тем, как второй покупатель вынул свою шоколадку: <мон, шок, мон>.
Операции над протоколами
Протоколам принадлежит основная роль в фиксировании, описании и понимании поведения процессов. В этом разделе мы исследуем некоторые общие свойства протоколов и операций над ними. Введем следующие обозначения:

s, t, u - протоколы,

S, Т, U - множества протоколов,

f,g,h– функции.

Конкатенация

Наиболее важной операцией над протоколами является конкатенация s^t, которая строит новый протокол из пары протоколов s и t, просто соединяя их в указанном порядке. Например,

<мон, шок>^<мон> = <мон, шок, мон>.

Самые важные свойства конкатенации — это ее ассоциативность и то, что пустой протокол <> служит для нее единицей:

L1.s^<> = <>^s.

L2.s^(t^u) = (s^t)^u.

Пусть f —функция, отображающая протоколы в протоколы. Она называется строгой, если отображает пустой протокол в пустой протокол:f(<>) = <>.

Будем говорить, что функция f дистрибутивна, если f(s^t) = f(s)^f(t).

Все дистрибутивные функции являются строгими.

Если n— натуральное число, то tⁿ будет обозначать конкатенацию n копий протокола t. Отсюда следует:

L3.tⁿ⁺¹=t^tⁿ.

L4.(s^t)ⁿ⁺¹ = s^(t^s)ⁿ^t.

Сужение

Выражение (tА) обозначает протокол t, суженный на множество символов А; он строится из t отбрасыванием всех символов, не принадлежащих А.

Сужение дистрибутивно и поэтому строго.

L1.<>A= <>.

L2.(s^t)A= (sA)^(tA).

Эффект сужения на одноэлементных последовательностях очевиден:

LЗ.<х>А=<х>, если х А.

L4.<y>А=<>,если y А.

Приведенные ниже законы раскрывают взаимосвязь суженияи операций над множествами.

L5.s{} = <>.

L6.(sA)B= s(A B).

Голова и хвост

Если s — непустая последовательность, обозначим ее первый элемент s₀, а результат, полученный после его удаления — s’. Например, <x,y, х>₀ = x,<х, у, х>’ = y. Обе эти операции не определены для пустой последовательности.

L1.(<x>^s)₀ = х.

L2.(<x>^s)’ = s.

L3.s = (<s₀>^s’), если s <>.

Следующий закон предоставляет удобный метод доказательства равенства или неравенства двух протоколов:

L4.s = t  (s = t = <> OR (s₀= t₀ AND s’ = t’)).

Звёздочка

Множество А* — это набор всех конечных протоколов (включая <>), составленных из элементов множества А. После сужения на А такие протоколы остаются неизменными, Отсюда следует простое определение:

А*= {s (sA) = s}.

Приведенные ниже законы являются следствиями этого определения:

L1.<> А*.

L2.<x> А*x А.

L3.(s^t) А*s А*AND t А*.

Они обладают достаточной мощностью, чтобы определить, принадлежит ли протокол множеству А*. Например, если х А,а y А,то

<x,y> А*(<x>^<y>) А*

( А*)AND ( А*)по L3

 T AND F=Fпо L2.

Порядок

Если s— копия начального отрезка t, то можно найти такое продолжение и последовательности s, что s^и= t.Определим отношение порядка

s t = (u.s^и= t)

и будем говорить, что s является префиксомt. Например:<х, у> <х, у,z>. Отношение является частичным упорядочением и имеет своим наименьшим элементом <>. Об этом говорят законы

L1.<> sнаименьший элемент.

L2.s sрефлексивность.

L3.s t AND t s t= sантисимметричность.

L4.s t ANDt u s uтранзитивность.

Следующий закон вместе с L1 позволяет определить, является ли справедливым отношение s t:

L5.(^s) tt <> AND x= t₀ AND s t’.

Будем говорить, что функция f из множества протоколов во множество протоколов монотонна, если она сохраняет отношение порядка , т. е. f(s) f(t) всякий раз, когда s t.

Длина

Длину протокола t будем обозначать #t. Например, #<х, у,z> = 3.

Следующие законы определяют операцию #:

L1.#<> = 0.

L2.# = 1.

L3.#(s ^t) = #s + #t.

Число вхождений символах в протокол s определяется как:

s х= #(s{х}).