Теория рекурсивных функций (например, машин Тьюринга) основана на пакетной модели вычислений, при этом результат вычислений получается, когда рекурсивная функция прекращает работу. Для открытых систем необходима иная теория вычислений, при которой предполагается, что обработка данных никогда не прекращается, а результат работы может потребоваться в процессе вычислений, более того, входные данные могут поступать из источников, не предвиденных до начала вычислений.
Асинхронные параллельные вычислительные системы используют элемент с двумя входами и двумя выходами, имеющий название арбитр. Арбитр — это основной компонент аппаратуры, отличающий параллельные асинхронные вычисления от последовательных синхронных. Арбитры принимают решения, для которых нет логического обоснования (доказательства), потому что решение невозможно вывести из знаний о структуре этой вычислительной системы и о ее входах.
Рис. 1. Арбитр с входными данными х и у и выходными данными х' и у'.
В самом глубоком смысле арбитры не эквивалентны машинам Тьюринга. На рис. 1 показан арбитр со входами х и у и выходами х' и у'.
Рис. 2. Если входные данные поступают в арбитр одновременно или почти одновременно, то на выходе получается один из показанных вариантов.
Арбитр принимает решение о порядке поступления на исто запросов. Если входы х и у поступили примерно в одно и то же время, результатом в конечном счете может быть одна из возможностей, показанных на рис. 2.
Выход арбитра не является простой логической функцией от входа, поскольку в арбире существенно учитывается параметр времени. Однако допустимое множество выходов может быть описано логически с использованием отношения особого логического следования:
(х = 1 и у = 1), следовательно
(либо
(х'=0 и у' = 1)
(х'=1 и у'=0))
Логика не позволяет определить, какая из возможностей осуществится. Системы с арбитрами не эквивалентны недетерминированной машине Тьюринга, поскольку арбитр может потребовать для принятия решения сколько угодно времени (скажем, пока выполняются другие вычисления). Если решение принимается недетерминированной машиной Тьюринга, то время, в течение которого она должна принять решение, определено до начала ее работы. Каждый отдельный выбор недетерминированной машины Тьюринга делается за один шаг.
Рис. 3. Входные данные арбитра, как правило, являются непрерывными сигналами в диапазоне от 1 до 0.
На практике на входы арбитра поступают аналоговые сигналы, которые принимают непрерывные значения в интервале от 0 до 1. Например, если входы в арбитр равны 0,97 и 0,96, то выход может быть таким, как показано на рис. 3.
Арбитр имеет только дискретные значения на выходе (0 или 1), несмотря на то что значения на входе непрерывны. Он дает определенное числовое решение исходя из непрерывного значения времени и двух входных значений. Вследствие непрерывности значений времени и входных сигналов арбитр невозможно строго смоделировать с помощью какой-либо машины с недетерминированными состояниями.
При параллельном вычислении арбитры используются многократно, так что число возможных выходных результатов растет в зависимости от времени экспоненциально. Поэтому реальную работу параллельной системы ЭВМ невозможно логически определить на основании входов в систему. Недетерминированность арбитров, используемых в открытой системе, приводит к тому, что они принимают решение, которое не может быть строго обосновано знанием структуры вычислительной системы и ее входных данных.
