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

в 1970 году советским математиком Ю.В. Матиясевичем, а несколько позже Г.В.Чудновским было доказано, что эта проблема алгоритмически неразрешима, т.е. алгоритм, который искали, не существует. Заметим, что не существует алгоритма, позволяющего выяснить наличие целых (диофантовых) корней для произвольного полинома от произвольного числа переменных. Для полиномов частного вида разрешающий алгоритм может существовать. Рассмотренная алгоритмически неразрешимая проблема считается 10-ой проблемой Гильберта. Рассмотрим еще несколько таких примеров. 2. Проблема распознавания применимости. Пусть задан нормальный алгоритм А и слово Р. Возможны случаи: - алгоритм А применим к слову Р, т.е. процесс переработки слова Р конечен; - алгоритм А бесконечно перерабатывает слово Р, т.е. неприменим к этому слову. Следовательно, возникает задача а{. применимлиАкР или нет. Учитывая, что нормальных алгоритмов А и слов Р может быть бесчисленное множество, получаем массовую проблему { ЙГ /} - проблему распознавания применимости произвольного нормального алгоритма к произвольному слову. Далее ставим вопрос: существует ли общий метод для решения всех задач этой проблемы, т.е. есть ли общий метод, который позволил бы выяснить применимость произвольного нормального алгоритма А к произвольному слову Р. Под общим методом будем понимать либо нормальный алгоритм, либо машину (алгоритм) Тьюринга. Теорема 5.7. Пе существует нормального алгоритма В, который позволил бы выяснить, применим или нет произвольный нормальный алгоритм А к произвольному слову Р. Теорему примем без доказательства. 3. Проблема эквивалентности слов. Пусть А - некоторый алфавит; Р я Q слова в этом алфавите;P ^ Q - ориентированная подстановка, т.е. когда вместо слова Р подставляется слово Q; P-Q - неориентированная подстановка, т.е. можно подставить либо вместо Р слово Q, либо наоборот, вместо Q слово Р. Из бесчисленного множества возможных подстановок в алфавите А задают некоторое конечное множество подстановок указанных видов и называют их допустимыми подстановками. Два слова R и S в алфавите А называются эквивалентными, если существует конечная последовательность слов Ri,R2,---,Rn (Ri=R, Rn=S) такая, что Ri+i получается из Ri в результате одной допустимой подстановки. Возникает следующая массовая проблема: для любых двух слов в данном алфавите требуется указать, эквивалентны они или нет - проблема 167