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

в 70-е годы XX в. советскими математиками Ю. В. Мати- ясевичем и Г. В. Чудновским было доказано, что эта проблема алгоритмически неразреатима, т.е. алгоритм, который искали, не существует. Заметим, что не существует алгоритма, позволяющего выяснить наличие целых (диофантовых) корней для произвольного полинома от произвольного числа переменных. Для полиномов частного вида разрешающий алгоритм может существовать. § 13. Примеры алгоритмически неразрешимых массовых проблем В предыдущем параграфе уже рассматривалась одна из алгорит­ мически неразрешимых массовых проблем - 10-я проблема Гиль­ берта. Рассмотрим еще несколько таких примеров. \.П р о б л е м а распознаванияприменимости. Пусть задан нор­ мальный алгоритм Л и слово Р. Возможны два случая: 1) алгоритм Л применим к слову Р , т.е. процесс переработки слова Р конечен; 2) алгоритм А бесконечно перерабатывает слово Р , т.е. не при­ меним к этому слову. Следовательно, возникает задача а-,\ применим л и А к Р или нет. Учитывая, что нормальных алгоритмов А и слов Р может быть бесчисленное множество, получаем массовую проблему {а,} - проблему распознавания применимости произвольного нормального алгоритма к произвольному слову. Далее ставим вопрос: существует ли общий метод для решения всех задач этой проблемы, т.е. есть ли общий метод, который позволил бы выяснить применимость произвольного нормального алгоритма А к произвольному слову Р . Под общим методом будем понимать либо нормальный алгоритм, либо машину (алгоритм) Тьюринга, 248