Структуры данных и модели вычислений

         

основываясь на своей неопубликованной работе


В 1943 году Э.Пост, основываясь на своей неопубликованной работе 1920-1922 годов, выдвинул еще один формальный эквивалент понятия вычислимой функции.

Еще одну формулировку дает теория алгоритмов Маркова (1951 г.).

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

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

Заметим, что разрабатываемые в настоящее время алгоритмические языки, составляющие математическое обеспечение современных вычислительных устройств, также можно использовать для определения понятия вычислимости. Более того, можно проследить тесную связь между упомянутыми здесь теоретическими моделями вычислений и реальным программированием. Так, -исчисление Черча является прообразом функционального программирования, реализованного в известном программистам языке ЛИСП, разработанном в 1961 году Дж.Маккарти, а модель Поста содержит идеи, реализованные в операторных языках типа Фортран, Алгол. Методы логического программирования реализованы в настоящее время в нескольких версиях языка Пролог.

Однако реальные языки программирования из-за своей громоздкости и избыточности выразительных средств малопригодны для теоретического анализа понятия вычислимости. Отметим также модели вычислительных устройств, получившие название РАМ (Равнодоступная Адресная Машина) и РАСП (Равнодоступная Адресная Машина С хранимой Программой).Эти модели в большей степени, чем, например, модель Тьюринга, отражают структуру современных вычислительных устройств.


Содержание  Назад  Вперед