Математическая логика и теория алгоритмов

системы матриц Ц U\,Ui,...,Uq порядка nxn, представима ли матрица U через матрицы UuUz.-.Uq. Частная проблема представимости матриц. Даны матрицы U ] ,Uj,-..,Uci порядка п х п . Требуется выяснить, существует ли алгоритм, посредством которого можно было бы узнавать для любой матрицы U того же порядка, представима ли она через U], Пъ..-, Uq. А. А. Марков построил систему из 102 матриц 6-го порядка, для которой доказал алгоритмическую неразрешимость частной проблемы представимости, откуда сразу следует алгоритмическая неразреши­ мость и общей проблемы представимости матриц для «>б (позже было доказано для п>А). 4. Проблема неразрешимости логики предикатов. Чёрчем доказано, что не существует алгоритма, который для любой формулы логики предикатов устанавливает, логически общезначима она или нет. 5. П р о б л е м а остановки. Тьюрингом доказано, что не сущест­ вует алгоритма, позволяющего выяснить; остановится или нет произвольная программа для произвольного заданного входа. Смысл этого утверждения для теоретического программирования состоит в следующем: не существует общего метода проверки программ на наличие в них бесконечных циклов. 6. Не существует алгоритма, позволяющего установить, вычисляет ли некоторая конкретная программа (на любом языке программирования) постоянную нулевую функцию Z ( x ) = 0 . Как следствие, можно утверждать, что проблема о том, вычисляют ли две произвольные программы одну и ту же одноаргументную функцию, тоже алгоритмически неразрешима. Тем самым получаем, что в об­ ласти тестирования компьютерных программ имеются принципиаль­ ные ограничения. Сделаем несколько замечаний. 1. Теоремы об алгоритмической неразрешимости утвервдают лишь то, что класс рассматриваемых задач достаточно обширен и для них нет одного разрешающего алгоритма, но не утвервдается вообще 250