Естественное обобщение тьюринговой модели вычислимости

Аннотация

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

Для анализа целенаправленного поведения могут быть использованы модели комбинированной временной и динамической логики. Такой анализ позволяет прийти к выводу, что существуют по крайней мере три вида элементарных правил, лежащих в основе сложного целенаправленного поведения: 1) пассивно-процессуальные – "Если имеет место процесс $P$, то ничего не делай, а дождись, когда он сам приведет тебя к искомой цели $G$"; 2) конструктивные – "Если имеет место $C$, выполни действие $d$, непосредственный результат которого и есть искомая цель $G$"; 3) конструктивно-процессуальные – "Если имеет место $C$, выполни действие $d$, чтобы его непосредственный результат $R$ инициировал процесс $P$, который и приведет к искомой цели $G$". Комбинированная логика позволяет определить условия корректности данных правил. Конструктивно-процессуальные правила обладают свойством универсальности, так как к ним редуцируемы два других вида правил.

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