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

Теперь мы переходим к вопросу о том, как можем мы построить такой механизм, который осуществлял бы декодирование автоматически. Мы ищем теперь не восстановленное сообщение, а машину, которая могла бы его восстановить. Как должна строиться такая машина? Для описания ее нам потребуется, конечно, обычное множество преобразований ( 4/1).

Один из возможных методов, который мы и будем здесь использовать, состоит в следующем: процедуру предыдущего параграфа переводят в механическую форму, используя то обстоятельство, что каждый переход дает информацию о том значении параметра, при котором он совершался. Для этого нам нужна машина, которая принимала бы на входе некоторый переход и выдавала на выходе соответствующее значение параметра., Но ясно, что знание того, какой произошел переход, т. е. каковы значения i и j в выражении Xi > Xj. равносильно знанию того, какое значение имеет вектор (Z, j). Ведь переход тоже можно рассматривать как вектор с двумя составляющими. Поэтому мы можем вводить переходы в обратный преобразователь, коль скоро вход последнего состоит из двух параметров, первый из которых принимает значение предшествующего состояния в переходе, а второй - значение последующего состояния.

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

Предположим, что он начинает работу с состояния г и что ему дается вход
Q S S R Q S R R Q; тогда его выходом будет r q s s r q s r r q, т. е. после первой буквы он просто повторяет вход, но на один шаг позже. Два таких преобразователя, соединенных последовательно, повторят сообщение на два шага позже и т. д. Ясно, что в принципе получить задержку нетрудно.

Предположим, что первый, кодирующий преобразователь задается таблицей

Нам требуется, например, машина, которая:
при входе А, А будет выдавать S

и т. д.

(Вход А,С для этой машины исключается, ибо кодирующий преобразователь никогда не выдаст такого перехода.) Наши три машины соединяются следующим образом:

Задерживатель имеет простую форму

а обратный преобразователь - форму

входом в которую служит вектор:
(состояние задерживателя, состояние кодирующего преобразователя).

В этом случае обратный преобразователь выдает ту же самую последовательность, которая была введена в кодирующий преобразователь. Так, предположим, что в кодирующий преобразователь было введено Q, вызвавшее в нем переход А D. Это означает, что обратный преобразователь получит D непосредственно из кодирующего преобразователя (ибо кодирующий преобразователь находится в состоянии D), а из задерживателя получит а ,(ибо кодирующий преобразователь был в А на предыдущем шаге). Со входом (a,D) обратный преобразователь перейдет в состояние Q, с которого мы и начали. И то же самое для всех остальных состояний, которые могут вводиться в кодирующий преобразователь.

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

Упр. 1. Почему нельзя использовать в качестве примера кодирующий преобразователь из  8/5?

Упр. 2. Закончите построение приведенного выше обратного преобразователя.

Упр. 3. Постройте в табличной форме двухшаговый задерживатель.