Cтраница 4
Во втором разделе статьи дается мотивировка определения мер сложности вычислений и приводится несколько примеров. Затем выводятся некоторые основные свойства, которые выполняются для всех мер сложности. Показывается, например, что для каждой меры сложности существуют сколь угодно сложные функции, принимающие только значения О, 1, и что не существует рекурсивного отношения между величиной функции и ее сложностью. С другой стороны, показано, что любые две меры сложности рекурсивно ограничивают друг друга. Позднее будет показано, что это верно не для всякой рекурсивной функции. Наше доказательство основано на прямой диагональной процедуре и не опирается на теорему о рекурсии, которая использовалась в первоначальном доказательстве. Для этой меры сложности трудность доказательства значительно уменьшается по сравнению с первоначальными трудностями. Теорема об ускорении имеет странное следствие: какие бы две универсальные машины мы ни взяли ( неважно, насколько более быстрой и мощной является одна из них), существуют такие функции, которые нельзя вычислить быстрее на более мощной машине. Эго следует из того, что для любого алгоритма, который мы используем для вычисления такой функции на более мощной машине, существует другой алгоритм, настолько быстрый, что даже на медленной машине он выполняется быстрее, чем первый алгоритм на быстрой машине. [46]
В такой общей формулировке утверждение неверно, что будет показано. Как считается в литературе, правильная формулировка была впервые дана Бибербахом [2] в его учебнике теории функций. Правда, там была дана правильная формулировка только первого утверждения теоремы 1.4.1. Доказательство, приведенное в настоящем обзоре, восходит к самому Адамару. Оно представляет собой не что иное, как мою интерпретацию текста Адамара. По моему мнению первоначальное доказательство Адамара много лучше всего, что сделали более поздние исследователи, желавшие внести упрощения, но нанесшие ущерб строгости выводов. [47]