§4.4. Алгоритмически неразрешимые задачи
В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому что его пока не придумали, а потому что он невозможен в принципе.
Разумеется, алгоритм надо понимать в смысле машин Тьюринга и рекурсивных функций (см. разделы 4.1, 4.2, 4.3). Сформулируем некоторые из этих задач. Доказывать их алгоритмическую неразрешимость мы не будем, так как это выходит далеко за рамки данного учебника.Проблема остановки машины Тьюринга. Машина Тьюринга – это объект, определяемый конечным числом параметров. Все частичные отображения одного конечного множества в другое могут быть эффективным образом перенумерованы. Поэтому каждой машине Тьюринга можно присвоить номер (натуральное число). Пусть 
машина Тьюринга с номером 
Некоторые машины, начинающие работать на пустой ленте, в конце концов останавливаются, а некоторые работают бесконечно долго. Возникает задача: по натуральному числу 
определить, остановится или нет машина Тьюринга 
запущенная на пустой ленте. Эта задача алгоритмически неразрешима. То есть не существует автоматической процедуры, для каждого решающей, останавливается или нет машина 
Это не исключает того, что для какой-либо конкретной машины мы установим, останавливается она или нет. Не существует метода, решающего это сразу для всех машин.
Проблема равенства слов. Группы и полугруппы часто задаются образующими элементами и определяющими соотношениями.
Например, группа
подстановок на трёхэлементном множестве имеет образующие элементы 
и 
и определяющие соотношения 
Каждый элемент из является произведением элементов 
и 
взятых, возможно, несколько раз, т.е. словом в алфавите 
причём это слово в общем случае не единственно. Например, 
и 
один и тот же элемент из 
Возникает вопрос: равны два данных слова в группе или нет? Существует ли алгоритм, решающий этот вопрос для любых двух слов? Для группы ответ положительный: алгоритм существует, и читатель сформулирует его без труда. Однако, существуют полугруппы (и группы), для которых такого алгоритма нет. Итак, пусть полугруппа 
задана образующими элементами 
и соотношениями 
(
слова от ), то в общем случае не существует алгоритма, определяющего для двух произвольных слов 
равны они как элементы из или не равны (т.е. следует равенство 
из равенств или не следует). Кроме того, в общем случае алгоритмически неразрешим вопрос о том, будет ли полугруппа 
конечной (или коммутативной, или периодической). Проблема истинности формулы. Всякая аксиоматическая теория (например, теория групп или элементарная геометрия) определяется наличием аксиом (будем считать, что их конечное число) и правил вывода утверждений из аксиом. Утверждения, выводимые из аксиом, называются теоремами. Примеры правил вывода:
1) всякая аксиома есть теорема;
2) если 
и 
теоремы, то 
теорема;
3) если и 
теоремы, то теорема.
Пусть дана правильно построенная формула (т.е. не произвольный набор значков, а формула, построенная с правильным употреблением логических связок, расстановки скобок и т.д.). Является ли теоремой, т.е. выводима ли из аксиом 
Существуют аксиоматические теории, для которых выяснить для произвольной формулы 
истинна ли она (т.е. является ли теоремой), алгоритмически неразрешимо.