Некоторые алгоритмически неразрешимые задачи в информатике:

• Проблема останова. 1 Нужно выяснить по данной программе, остановится она или нет. 2
• 10-я проблема Гильберта. 12 Для многочлена с целыми коэффициентами и несколькими переменными нужно узнать, есть ли у него решение. 2
• Проблема умирающей матрицы. 4 Для данного конечного множества квадратных матриц n × n нужно определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. 4
• Проблема единичной матрицы. 4 Для данного конечного множества квадратных матриц n × n нужно определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее единичную матрицу. 4