Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

эквивалентности слов. Марков и Пост доказали, что данная проблема тоже алгоритмически неразрешима. 4. Проблема представимости матриц. Пусть Ui,U2,...,Uq - матрицы порядка пхп. Будем говорить о матрице U того же порядка, что она представима через Ui,U2,...,Uq, если для некоторого целого положительного t и целых чисел Г1,Г2,..Г( из ряда \ имеет место равенство и =Url''Ur2''...''Urt. Общая проблема представимости матриц. Дано целое положительное число п, требуется выяснить, существует ли алгоритм, посредством которого можно было бы узнавать для любой системы матриц U,Ui,U2,...,Uq порядка п х п, представима ли матрица U через матрицы Ui, U2,..., Uq. Частная проблема представимости матриц. Даны матрицы Ui,U2,...,Uq порядка пхп. Требуется выяснить, существует ли алгоритм, посредством которого можно было бы узнавать для любой матрицы U того же порядка, представима ли она через Ui,U2,...,Uq. А. А. Марков построил систему из 102 матриц 6-го порядка, для которой доказал алгоритмическую неразрешимость частной проблемы представимости, откуда сразу следует алгоритмическая неразрешимость и общей проблемы представимости матриц для (позже было доказано для п>4). 5. Проблема неразрешимости логики предикатов. Черчем доказано, что не существует алгоритма, который для любой формулы логики предикатов устанавливает, логически общезначима она или нет. 6. Проблема остановки. Тьюрингом доказано, что не существует алгоритма, позволяющего выяснить: остановится или нет произвольная программа для произвольного заданного входа. Смысл этого утверждения для теоретического программирования состоит в следующем: не существует общего метода проверки программ на наличие в них бесконечных циклов. 7. Пе существует алгоритма, позволяющего установить, вычисляет ли некоторая программа (на любом языке программирования) постоянную нулевую функцию Z(x)=0. Как следствие, можно утверждать, что проблема о том, вычисляют ли две произвольные программы одну и ту же одноаргументную функцию, тоже алгоритмически неразрешима. Тем самым получаем, что в области тестирования компьютерных программ имеются принципиальные ограничения. Сделаем несколько замечаний. 1. Теоремы об алгоритмической неразрешимости утверждают лишь то, что класс рассматриваемых задач достаточно обширен и для них нет одного разрешающего алгоритма, но не утверждается вообще неразрешимость этих задач. Для каждой конкретной задачи, например, для каждого данного слова Р, может быть, и можно выяснить, применим к нему данный нормальный 168