Глава 2. ПРОГРАММИРОВАНИЕ, СТРУКТУРА ПРОГРАММ И ВЫЧИСЛИМОСТЬ

2.0. Важность понятия вычислимости

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

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

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

Вопрос „Для вычисления каких классов функций требуются автоматы со свойством можно сформулировать и так: „Для каких классов функций необходима программа, структура которой обладает свойством х?“.

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

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

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

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

Рис. 2.1. Этапы построения специализированной машины, определяемой программой.

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

Рис. 2.2. Управление операциями во время выполнения программы.

Запись данных в память эквивалентна изменению состояния памяти. Это соображение приводит нас к наиболее важному пункту. Статическая память имеет конечные размеры и поэтому может находиться лишь в конечном числе состояний. (Пусть конечная память содержит k битов информации. Тогда она может находиться только в различных состояниях). Процедурную часть можно считать множеством правил для изменения состояния статической памяти как функции (а)

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