ГЛАВА Х. ПРЕОБРАЗОВАНИЕ ТАКТНОСТИ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН

§ 10.1. Общие соображения о преобразовании тактности.

Определение понятий изображения и воспроизведения

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

Пусть задана П-машина . Подадим на вход машины какую-либо последовательность символов , например , и рассмотрим ленту, соответствующую этой последовательности .

Выберем теперь каким-либо способом возрастающую последовательность тактов

например нулевой, второй, пятый такт и т. д., и выпишем из ленты П-машины (из табл. 10.1) столбцы, соответствующие этой последовательности.

Выписанные столбцы образуют табл. 10.2.

Таблица 10.1

Таблица 10.2

Введем в рассмотрение новую тактность, приняв момент и за момент наступления такта. Тогда табл. 10.2 приобретает вид табл. 10.3, которая может рассматриваться как результат работы некоторой иной последовательностной машины .

Таблица 10.3

Если заданная лента машины S (табл. 10.1), а значит, и перестроенная из нее лента (табл. 10.3) конечны, то П-машина G, ревизующая ее, заведомо существует (см. § 8.2).

Для наглядности представим себе работающую П-машину, освещаемую в моменты вспышками стробоскопа. Тогда нам покажется, будто бы она перерабатывает последовательность в последовательность в соответствии с табл. 10.3, в то время как на самом деле П-машина работает в соответствии с табл. 10.1.

Предположим теперь, что моменты (в нашем примере со стробоскопом — моменты вспышек) выбраны столь удачно по отношению к П-машине , что какую бы входную последовательность П-машина перерабатывала, начиная с какого угодно начального состояния наблюдая ее лишь в моменты , мы видим такую переработку входной последовательности в выходную, которую могла бы осуществить некоторая иная Я-машина G, начинающая работать с некоторого, быть может для каждой входной последовательности иного, начального состояния .

В этом случае мы будем говорить, что осуществляется преобразование тактности — П-машина S, работающая в тактности, которую мы в дальнейшем условно будем называть быстрой, преобразуется в П-машину G, работающую в тактности, которую мы далее будем условно называть медленной .

Мы будем говорить также, что П-машина изображает в медленной тактности П-машину .

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

Это означает, что для различных входных последовательностей одному и тому же состоянию могут соответствовать различные начальные состояния машины G. Для того чтобы найти начальное состояние машины G, надо, помимо состояния машины S, наперед знать, какая входная последовательность будет подана на вход машины S. Возникает ситуация, весьма похожая на ту, с которой мы встречались в гл. IX при определении понятия эквивалентности П-машины. В гл. IX нам удалось сузить формулировку понятия эквивалентности так, чтобы выбор начального состояния не требовал априорного знания входной последовательности.

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

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

Алгоритм выбора возрастающей последовательности будем называть законом преобразования тактности.

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

При таком определении понятия изображения начальное состояние машины G определяется по начальному состоянию «быстрой» машины S и лишь по первому символу входной последовательности.

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

Со случаем такого рода мы столкнемся далее в § 10.2, где множество будет состоять из последовательностей, содержащих лишь один символ. Изображение, вообще говоря, неоднозначно: при заданном законе преобразования тактности заданная машина S может изображать много различных машин: .

Этот вывод верен и в том случае, когда ограничения множества входных последовательностей машины G не происходит, т. е. когда .

По аналогии с понятием относительной эквивалентности (см. гл. IX) можно ввести и понятие относительного изображения. Определение относительного изображения отличается от определения изображения лишь тем, что быстрая машина S может получать не любую входную последовательность, а только последовательность, принадлежащую заданному множеству допустимых входных последовательностей машины .

Будем говорить в этом случае, что машина S изображает машину G относительно множества .

При множество может совпадать с , быть уже или шире его, пересекаться с ним и т. д. В частности, если , множество может быть ограниченным, и наоборот, может быть .

Естественно, что изображение машиной S какой-либо машины G тесно связано с выбираются моменты . (моменты вспышек стробоскопа). Эти моменты могут быть выбраны, вообще говоря, и так, что машина S не изображает никакую последовательностную машину.

Выбор моментов . может зависеть от входной последовательности выходной последовательности , последовательности состояний машины S и времени .

«Часы», выдающие сигналы о наступлении медленных тактов , должны воспринимать время t и символы и (или некоторые из этих символов), которые связаны с работой быстрой машины . «Часы» реализуют любой алгоритм, перерабатывающий эту последовательность символов в последовательность .

Мы предположим, что часы сами являются конечным автоматом с выходным преобразователем, работающим в той же быстрой тактности, что и П-машина . Входной алфавит этого автомата получается объединением алфавитов или некоторых из них в зависимости от того, чем определяется выбор тактов . Процесс выработки сигнала о наступлении медленного такта может тогда рассматриваться как представление события на входе в автомат-часы. Можно показать, Что в этом случае (при таких часах) П-машина S всегда изображает какую-либо П-машину .

В связи с введением понятий изображения (относительного изображения) и преобразования тактности возникают следующие задачи:

1. Задана машина , множество и «часы» (т. е. автомат А с преобразователем ). Требуется найти хотя бы одну машину G, которую машина изображает относительно , и ее множество допустимых входных последовательностей .

2. Заданы машина и машина G. Требуется определить, существует ли такой закон преобразования тактности, при котором машина изображает машину G, и если да, то найти его (построить автомат А и преобразователь Ф «часов»).

Аналогичная задачу возникает и для относительного изображения (в этом Случае следует еще определить множество ).

3. Задана машина S, множество и закон преобразования тактности. Требуется построить минимальную (или одну из минимальных) машину , которую машина S изображает относительно , и найти ее множество допустимых входных последовательностей .

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

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

Рис. 10.1.

В моменты . наблюдаются не пары (), а пары .

Мы этого расширения не делаем, так как далее оно нам не потребуется.

Пусть теперь задан закон преобразования тактности, две машины — «медленная» G и «быстрая» S и множество допустимых входных последовательностей машины G. Задание машины G и множества означает, что можно определить любой вариант работы машины G, т. е. определить результат переработки машиной G любой входной последовательности из при любом начальном состоянии .

Обратимся теперь к определению понятия . относительного воспроизведения.

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

В случае, когда , относительное воспроизведение переходит в воспроизведение.

Во избежание путаницы в дальнейшем, обратим внимание на то, что понятия изображения и воспроизведения (как относительного, так и безотносительного) совершенно различаются и даже в известном смысле противоположны. В самом деле, при изображении требуется, чтобы любой вариант работы быстрой машины S, рассматриваемой в моменты . совпадал с одним из вариантов работы медленной машины G; при воспроизведении же требуется, чтобы для любого варианта работы медленной машины G нашелся такой вариант работы быстрой машины S, который, будучи рассмотрен в моменты , совпал бы с заданным вариантом работы машины .

Можно привести примеры, когда машина изображает машину G, но не воспроизводит ее; можно также привести примеры, когда машина воспроизводит, но не изображает машину .

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

Множество допустимых входных последовательностей для быстрой машины , которая воспроизводит относительно заданного ) заданную машину G, также определяется неоднозначно; более того, в ряде случаев множество может содержать новые входные символы, которые не появлялись в последовательностях множества .

В самом -согласно определению, для каждой последовательности и состояния при воспроизведении найдется хотя бы одна соответствующая ей последовательность , подаваемая на вход машины S. Однако в общем случае заданным может соответствовать не одна, а много (даже бесконечное число) различных последовательностей . Из всех последовательностей , соответствующих всем при любых , может быть образовано много (может быть даже бесконечное число) различных множеств . причем каждое из множеств содержит хотя бы одну последовательность соответствующую любым заданным .

Каждое из множеств можно рассматривать как множество допустимых входных последовательностей для быстрой машины 5, воспроизводящей относительно машину G. Выбор того или иного из этих множеств определяется дополнительными соображениями практического порядка. Иногда в качестве множества допустимых входных последовательностей для машины S удобно брать множество или же множество Е (которое годится во всех случаях).

При воспроизведении возникают такие же задачи, как и при изображении, — по заданным «часам» и одной из машин построить другую машину, или по заданным двум машинам построить "часы", а также задача минимизации.

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

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

Введенные выше формально определения поясним теперь на двух простых примерах.