Комбинаторный автомат — более рафинированный родственник конечного автомата. Конечный автомат (КА) специфицируется заданием конечного набора данных на входе, конечного набора внутренних состояний, конечного набора данных на выходе и указанием сопряженного с ними набора отношений перехода от состоянию к состоянию. Внутреннее состояние КА — это простой элемент Si, лишенный внутренней структуры; это же справедливо для данных на входе и на выходе. Отношения перехода специфицируют для каждой возможной пары данных на входе и внутренних состояний новое внутреннее состояние и имеющийся на выходе результат. Если дано начальное состояние какого-то КА, то эти отношения перехода от состояния к состоянию специфицируют, каким образом он будет изменяться во времени и что он будет давать на выходе в зависимости от того, что он получает на входе. Вычислительная структура КА представляет собой этот относительно простой набор отношений перехода от состояния к состоянию в наборе неструктурированных состояний.

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

Комбинаторные автоматы (КоА) ничем не отличаются от КА, за исключением того, что их внутренние состояния структурированы. Состояние комбинаторного автомата представляет собой вектор [S1, S2,…,Sn]. Этот вектор может быть конечным или бесконечным, но я сосредоточусь на первом случае. Элементы этого вектора можно мыслить в качестве компонентов внутреннего состояния; они соответствуют клеткам клеточного автомата или ячейкам ленты и состоянию управляющего устройства машины Тьюринга. Каждый элемент Si может иметь конечное множество значений Sij, где Sij — j-e возможное значение i– го элемента. Эти значения можно трактовать в качестве «подсостояний» общего состояния. Данные на входе и на выходе имеют аналогичную комплексную структуру: первые являют собой вектор [I1,…, Ik], вторые — вектор [О1,…, Оm].

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

Теперь мы уже можем дать объяснение имплементации. Вычисления, такие как КоА — это абстрактные объекты, формальная структура которых определяется их состояниями и отношениями перехода от состояния к состоянию. Физические системы — это конкретные объекты, каузальная структура которых определяется их внутренними состояниями и каузальными отношениями между ними. В неформальном плане мы говорим, что физическая система имплементирует вычисление, если каузальная структура этой системы отражает формальную структуру вычисления. То есть, система имплементирует вычисление, если можно установить такое соответствие между состояниями этой системы и вычислительными состояниями, при котором каузально соотнесенные физические состояния соответствуют формально соотнесенным формальным состояниям.

Эта интуитивная идея может быть напрямую использована для получения представления об имплементации в случае КоА. Физическая система имплементирует КоА, если можно так разложить внутренние состояния системы на подсостояния, и данные системы на входе и на выходе — на подсостояния этих данных, и так соотнести подсостояния системы с подсостояниями КоА, что отношения каузального перехода от состояния к состоянию для физических состояний, данных на входе и на выходе отражают формальные отношения перехода от состояния к состоянию для соответствующих формальных состояний, данных на входе и на выходе.

Формальный критерий имплементации КоА выглядит таким образом:

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

Могло бы показаться, что КоА немногим лучше КА. В конце концов, для любого конечного КоА мы можем найти соответствующий ему КА с тем же поведением на входе — выходе. Но между ними все же есть существенные различия. Первое и главное из них состоит в том, что условия имплементации для КоА гораздо более ограничены, чем аналогичные условия для КА. Имплементация КоА предполагает сложное каузальное взаимодействие множества отдельных частей; и поэтому КоА-описание может передавать каузальную организацию системы с гораздо большей степенью детализации. Во-вторых, КоА позволяют сформулировать единое объяснение условий имплементации, значимое как для конечных, так и для бесконечных машин. И, в-третьих, КоА может напрямую отражать комплексную формальную организацию вычислительных объектов, таких как машины Тьюринга и клеточные автоматы. В соответствующих КА была бы утрачена большая часть этих структурных моментов.