В 30-х и 40-х годах прошлого столетия в Англии, США и в СССР математикипредприняли попытку формализовать интуитивное понятие алг

В 30-х и 40-х годах прошлого столетия в Англии, США и в СССР математики предприняли попытку формализовать интуитивное понятие алгоритма. В Англии А. Тьюринг в 1937 году ввел понятие машины, позднее названной его именем, в США в 30-х – 40-х годах Черч, Клини и Пост ввели понятие рекурсивной функции и эффективной вычислимости и, наконец, в конце 40-х и начале 50-х годов прошлого столетия в СССР А.А. Марков ввел понятие нормального алгоритма (или алгорифма, как называл его сам автор). Эти объекты служили как средства для переработки информации, для чего служит и любой алгоритм в интуитивном смысле. Форма задания исходной информации, подлежащей переработке для этих объектов различна, но эти формы могут быть сведены одна к другой с помощью соответствующих перекодировок, и главный вопрос состоял в сравнении их возможностей. В результате исследований этих объектов была доказана их взаимная эквивалентность [1] и это обстоятельство подтолкнуло авторов этих объектов провозгласить соответствующие тезисы, суть которых состоит, скажем, на примере машины Тьюринга, в следующем: если имеется некоторый алгоритм в интуитивном смысле, то можно построить машину Тьюринга, эквивалентную этому алгоритму. В настоящей работе мы опровергаем тезис Тьюринга, а вместе с ним и тезисы Черча и Маркова в силу эквивалентности соответствующих формальных понятий алгоритмов [1]. В перечислительной комбинаторике [2], обычно, дается бесконечный класс конечных множеств Si , где i пробегает некоторое множество индексов I (такое, как множество неотрицательных целых чисел N ), и мы хотим сосчитать комбинаторное число Si элементов в каждом Si «одновременно». Множества Si мы будем называть комбинаторными множествами. 25 Однако для наших целей достаточно знать определенный ответ на вопрос: « Si полином или нет от i ». В случае утвердительного ответа на вопрос нам достаточно доказать, что   S i k i  O , где k некоторая константа. Определение 1. Множество Si называется полиномиальным, если   S i k i  O , где k некоторая константа; в противном случае оно называется неполиномиальным. Формулировка проблемы: пусть Si − комбинаторное множество и x − некоторый объект с легко проверяемым, (за полиномиальное число шагов от длины входа), признаком (свойством)  . Необходимо построить алгоритм, который не менее, чем за Si число шагов определяет: Si x  или Si x  . Предлагается следующий алгоритм решения проблемы: мы предполагаем, что конечное множество Si объектов находится в некоторой емкости  . Из емкости  мы извлекаем последовательно без возвращения все объекты до последнего включительно. Для последнего объекта мы проверяем наличие свойства  . Если последний извлеченный объект обладает свойством  , то проблема решена, т.е. Si x  . Если этот объект не обладает свойством  , то все извлеченные из  объекты мы возвращаем в  и возобновляем процесс извлечения из  объектов, но при этом, при каждом очередном извлечении объекта, проверяем, обладает ли извлеченный объект свойством  . Если для некоторого Si Si  m,m  , шага объект будет обладать свойством  , то проблема решена, т.е. Si x  . Если для Si m  ни один из извлеченных объектов не обладает свойством  , то проблема также решена, только в этом случае в  нет объекта со свойством  , т.е. Si x  . Из построенного алгоритма следует теорема.