А) Отсутствие общего метода решения задачи

Проблема 1. Распределение девяток в записи числа .

Определим функцию f(n) = i, где n – количество девяток подряд в десятичной записи числа , а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5. Задача состоит в вычислении функции f(n) для произвольно заданного n.

Поскольку число является иррациональным и трансцендентным, то мы не знаем никакой информации о распределении девяток (равно как и любых других цифр) в десятичной записи числа . Вычисление f(n) связано с вычислением последующих цифр в разложении , до тех пор, пока мы не обнаружим n девяток подряд, однако у нас нет общего метода вычисления f(n), поэтому для некоторых n вычисления могут продолжаться бесконечно – мы даже не знаем в принципе (по природе числа ) существует ли решение для всех n.

Проблема 2. Вычисление совершенных чисел (совершенные числа – это числа, которые равны сумме своих делителей, например: 28 = 1+2+4+7+14).

Определим функцию S(n) = n-ое по счёту совершенное число и поставим задачу вычисления S(n) по произвольно заданному n. Нет общего метода вычисления совершенных чисел, мы даже не знаем, множество совершенных чисел конечно или счетно, поэтому наш алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел при поиске n-ого совершенного числа – означает ли это, что его вообще не существует?

Проблема 3. Десятая проблема Гильберта.

Пусть задан многочлен n-ой степени с целыми коэффициентами – P, существует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?

Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.