Cтраница 2
Невозможность решения этих задач была строго доказана. Неудача попыток решения некоторых проблем после того, как была доказана невозможность решения некоторых других проблем, породила определенную подозрительность. Ученые стали опасаться, что затрачивая без успеха свои усилия на решение некоторых проблем, они стараются достигнуть невозможного. Возникло мнение о необходимости выявления неразрешимых проблем. Для задач на отыскание алгоритма это должно сводиться к разработке методов доказательства несуществования алгоритма. [16]
В самом деле, оно слишком ограничительно уже потому, что в ней рассматриваются только меры информации шенноновского типа, хотя в дальнейшем могут быть найдены аналогичные характерйзации, включающие какие-нибудь другие функционалы. С другой стороны, класс допустимых функционалов нужно как-то ограничить, поскольку иначе нам следовало бы, например, считать, что само определение области достижимых скоростей является однобуквенной характеризацией. Хотя в настоящее время попытка дать общее определение кажется преждевременной, существует одно свойство однобуквенных характерйзации, которое, по нашему мнению, должно следовать из любого разумного определения. Именно, однобуквенная харак-теризация должна быть вычислимой и должна приводить к алгоритму, который решает, принадлежит ли данная точка пространства е-окрестности характеризуемого множества, используя при этом меньше чем ( 1 / г) к арифметических операций. Неизвестно, всегда ли существует такой полиномиальный алгоритм, например, для описания области достижимых скоростей произвольной сети источников. Отрицательный ответ на этот вопрос мог бы быть интерпретирован как доказательство несуществования однобуквенной характерйзации. [17]