deep-econom (deep_econom) wrote,
deep-econom
deep_econom

Category:

о неразрешимости общей проблемы разрешимости

во всяких достаточно простых системах (но с достаточно сложной (богатой) структурой) не существует универсальных алгоритмов решения многих проблем

---
НЕВОЗМОЖНОСТЬ АЛГОРИФМОВ ТОЖДЕСТВА И ДЕЛИМОСТИ В ТЕОРИИ АССОЦИАТИВНЫХ СИСТЕМ
Доказательства этих теорем основаны на идеях и результатах Чёрча, Тьюринга, Россера и Поста.
стр.22.

стр.32
Это дало возможность установить ряд важных отрицательных
результатов — теорем невозможности алгорифмов.
Сюда относится прежде всего теорема Черча [12] о неразрешимости общей «проблемы разрешимости» исчисления предикатов.
В качестве более конкретных результатов можно
указать доказательство неразрешимости ряда проблем общей теории
ассоциативных систем [1; 2; 4; 5; 14] и теории целочисленных матриц [3; 16].


Марков А. А. Избранные труды. Т. II. Теория алгорифмов и
конструктивная математика, математическая логика, информатика и смежные
вопросы. — М.: Изд-во МЦНМО, 2003. — XXII+ 626 с.
http://lib1.org/_ads/E7E80A7DE9F77B263C8DF2122F940F9A
---
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 0 comments