Проблема останова заключается в том, чтобы по любой машине Тьюринга Т и слову Р в ее внешнем алфавите узнать, применима ли Т к начальной конфигурации q1Р. Проблема останова алгоритмически неразрешима, т.к. если бы она была разрешимой, то, взяв в качестве Р слово Код(Т), мы получили бы разрешимость проблемы самоприменимости.
Выявлению разрешимых и неразрешимых задач в различных разделах математики посвящено много исследований. Приведем без доказательства некоторые из таких проблем.
1. Проблема распознавания истинности формул элементарной арифметики. Формулы строятся с помощью арифметических действий (сложения и умножения), логических операций (логических связок и кванторов) и знака равенства. Проблема состоит в том, чтобы найти алгоритм, который по любой такой формуле определяет, истинна она или нет на натуральном ряду. Неразрешимость этой проблемы установил Гедель К. (1931).
2. Проблема разрешения для логики предикатов первого порядка. Нужно найти алгоритм, который бы проверил общезначимость формулы алгебры предикатов. Неразрешимость этой проблемы установил Черч А. (1936).
3. Проблема сочетаемости Поста. Конечное множество V пар слов в некотором алфавите называется сочетаемым, если для некоторых пар (A1,B1),…, (As,Bs) из V выполнено равенство A1…As=B1…Bs. Нужно найти алгоритм, который по всякому множеству V пар слов узнает сочетаемо оно или нет. Неразрешимость данной проблемы установил Пост Э. (1946).
4. Проблема представимости матриц. Рассматриваются (nxn)- матрицы над кольцом целых чисел Z. Пусть даны произвольные матрицы U1…Uq и U. Нужно иметь алгоритм, который бы решал, верно ли U =Ui ,…,Uip , для некоторых i1,…,ip. Неразрешимость
данной проблемы, начиная с n=4, установлена Марковым А.А. (1958).
5. Проблема тождества элементарных функций вещественного переменного. Определим класс термов Т индуктивно: x –переменная, п- число – термы. Если u,v – термы, то (u+v), (u*v),(u/v), sin(u), |u| — термы. Нужно иметь алгоритм, который по любым двум термам из Т узнает, задают ли они одну и ту же функцию одного вещественного переменного x. Неразрешимость данной проблемы установил Матиясевич Ю.В. (1973).
6. Проблема полноты автоматных базисов. Дан набор конечных автоматов (базис) с одним множеством входов и выходами, входящими в множество входов. Строятся схемы с помощью присоединения базисного автомата и введения обратной связи. Каждая схема реализует автомат. Если схемами в данном базисе может быть реализован любой автомат в данном алфавите, то базис называется полным, в противном случае – неполным.
Проблема полноты заключается в том, чтобы узнавать по заданному базису – является он полным или нет. Неразрешимость данной проблемы установил Кратко М.И.
(1966).
7. Десятая проблема Гильберта из 23 поставленным им в 1900 году формулируется так: «Пусть задано диофантово уравнение (многочлен вида p(x1,…,xn)=0) с произвольными неизвестными и целыми рациональными коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли уравнение в целых рациональных числах.» Неразрешимость 10-й проблемы Гильберта установлена Матиясевичем Ю.В. (1970).