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