"Interaction Nets" по-русски
Apr. 4th, 2013 01:44 pmЯ перевел на русский язык седьмую главу "Interaction-Based Models of Computation" из учебника "Models of Computation: An Introduction to Computability Theory" (Maribel Fernández). Исходник и PDF доступны на ShareLaTeX по следующему адресу:
https://www.sharelatex.com/project/515429c83d69291740451afe
В этой главе изучаются сети взаимодействия - модель вычислений, которую можно рассматривать как представителя класса моделей, основанных на идее "вычислений через взаимодействие". Сети взаимодействия являются графической моделью вычислений, изначально введенной как обобщение структур доказательств линейной логики. Данный формализм используется для описания алгоритмов и анализа их сложности, а также как язык низкого уровня, в который можно компилировать другие языки программирования. Особенно интересны сети взаимодействия тем, что они могут быть реализованы с разумной эффективностью.
Системы сетей взаимодействия определяются двумя множествами: набором агентов и набором правил взаимодействия. Агенты играют роль логических символов, а правила взаимодействия определяют их смысл. Также возможна аналогия с электрическими цепями, где агенты играют роль узлов цепи, а связи между агентами служат ветвями, соединяющими узлы. Наконец, мы можем просто считать агенты некоторыми объектами, выполняющими вычисления, при этом правила взаимодействия описывают их поведение.
Здесь дается общее представление о парадигме взаимодействия, приводятся примеры использования сетей взаимодействия для представления алгоритмов, а также показывается, как другие модели вычислений представляются в виде сетей взаимодействия.
https://www.sharelatex.com/project/515429c83d69291740451afe
В этой главе изучаются сети взаимодействия - модель вычислений, которую можно рассматривать как представителя класса моделей, основанных на идее "вычислений через взаимодействие". Сети взаимодействия являются графической моделью вычислений, изначально введенной как обобщение структур доказательств линейной логики. Данный формализм используется для описания алгоритмов и анализа их сложности, а также как язык низкого уровня, в который можно компилировать другие языки программирования. Особенно интересны сети взаимодействия тем, что они могут быть реализованы с разумной эффективностью.
Системы сетей взаимодействия определяются двумя множествами: набором агентов и набором правил взаимодействия. Агенты играют роль логических символов, а правила взаимодействия определяют их смысл. Также возможна аналогия с электрическими цепями, где агенты играют роль узлов цепи, а связи между агентами служат ветвями, соединяющими узлы. Наконец, мы можем просто считать агенты некоторыми объектами, выполняющими вычисления, при этом правила взаимодействия описывают их поведение.
Здесь дается общее представление о парадигме взаимодействия, приводятся примеры использования сетей взаимодействия для представления алгоритмов, а также показывается, как другие модели вычислений представляются в виде сетей взаимодействия.
