Специальная математика. Соловьев А.Е. - 66 стр.

Теорема: Алгоритмически неразрешимых задач больше, чем алгоритмически разрешимых.
Доказательство: Мощность множества функций (если угодно – задач) даже заведомо
ограничено:
                           f
                        N  N

 не менее, чем континуум- 1
Количество же вычислимых функций (если угодно – алгоритмов) счетно, т.е. 0.
Действительно, всякий алгоритм конечен, следовательно, он может быть записан конечной
строкой букв русского алфавита. А полученные конечные строки можно расположить в
лексикографическом (алфавитном) порядке, то есть пересчитать.
Таким образом, 1 - 0 = 1

                     6.2. Конкретизация понятия алгоритма

Поскольку определить, что такое алгоритм, невозможно, то были предложены и успешно
используются паллиативы, которые назовем конкретизациями понятия алгоритма. Наиболее
известны следующие:
1. -нотация.
2. Рекурсивные функции.
3. Машины Тьюринга.
4. Нормальные алгорифмы Маркова.

В связи с этим задача переформулируется следующим образом:
Задача алгоритмически разрешима, если для нее можно построить -нотацию (рекурсивную
функцию, машину Тьюринга, нормальный алгорифм Маркова). И наоборот, если
невозможно построить -нотацию и т.п., то задача алгоритмически неразрешима. Важно,
что все конкретизации алгоритма равнообъемны, то есть одновременно могут или не могут
быть построены для исследуемых задач.

                            6.3. Сложность вычислений

В качестве небольшого, но важного отступления отметим в данном разделе, что
алгоритмическая разрешимость еще не означает, что задача может быть реально решена.
Дело в том, что для нас на практике задача, решение которой требует тысячу лет или
ресурсы, превышающие все вычислительные ресурсы планеты, тоже неразрешима.
И здесь вступает в силу «математика практической осуществимости»…Такого рода
проблемами занимается теория сложности вычислений.
Рассмотрим для иллюстрации таблицу, в которой четыре столбца, соответствующие
«абстрактному» объему исходных данных (n)
Три строки соответствуют различным «функциям сложности вычислений». В таблице
приведены времена вычислений в зависимости от объема данных и сложности вычислений
(F).

     n   10          30             50             60
F
n        10-5 cек    3010-6 cек.   3010-6 cек.   3010-6 cек.
n5       0.1 cек.    24.3 cек.      5.2 мин.       13 мин.
2n       10-3 cек.   17.9 мин.      35.7 лет       366 столетий


                                          — 66 —