Об одном алгоритме, не согласующемся с тезисами Тьюринга, Черча и Маркова Кочкарев Б. С.

В 30-ых и 40 -х годах прошлого столетия в Англии, США и в СССР математики предприняли попытку формализовать интуитивное понятие алгоритма. Тьюринг ввел понятие машины, позднее названной его именем, в США в 30-ых - 40ых годах Черч, Клини и Пост ввели понятие рекурсивной функции и эффективной вычислимости и, наконец, в конце 40-х и в начале 50 ых годов прошлого столетия в СССР А. А. Марков ввел понятие нормального алгоритма. Эти объекты служили как средства для переработки информации, для чего служит и любой алгоритм в интуитивном смысле. Форма задания исходной информации, подлежащей переработке для этих объектов различна, но эти формы могут быть сведены одна к другой с помощью соответствующих перекодировок и главный вопрос состоял в сравнении их возможностей. В результате исследований этих объектов была доказана их взаимная эквивалентность и это обстоятельство подтолкнуло авторов этих объектов провозгласить соответствующие тезисы, суть которых, скажем, на примере машины Тьюринга, в следующем: если имеется некоторый алгоритм в интуитивном смысле, то можно построить машину Тьюринга, эквивалентную этому алгоритму. В работе [ 1 ], которую мы опубликовали еще в 1914 году, мы опровергаем тезис Тьюринга, а вместе с ним и тезисы Черча и Маркова в силу эквивалентности соответствующих формальных понятий алгоритмов. Поскольку отзывов на нашу указанную опубликованную работу не было, мы решили еще раз об этом упомянуть в этой публикации.

Литература:

[ 1 ] Кочкарев Б. С. Об одном алгоритме, не согласующемся с тезисами Тьюринга, Черча и Маркова