Author Archives: demensdeum

Представляю вашему вниманию перевод первых страниц статьи Алана Тьюринга – “О ВЫЧИСЛИМЫХ ЧИСЛАХ С ПРИЛОЖЕНИЕМ К ПРОБЛЕМЕ РАЗРЕШЕНИЯ” 1936 года. Первые главы содержат описание вычислительных машин, которые в дальнейшем стали основой для современной вычислительной техники.

Полный перевод статьи и пояснение можно прочитать в книге американского популяризатора Чарлза Петцольда, под названием “Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга” (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Оригинальная статья:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

—

О ВЫЧИСЛИМЫХ ЧИСЛАХ С ПРИЛОЖЕНИЕМ К ПРОБЛЕМЕ РАЗРЕШЕНИЯ

А. М. ТЬЮРИНГ

[Получено 28 мая 1936 г. — Прочитано 12 ноября 1936 г.]

«Вычислимые» (computable) числа могут быть кратко описаны как действительные числа, выражения которых в виде десятичных дробей исчислимы (calculable) конечным числом средств. Хотя на первый взгляд в данной статье как вычислимые рассматриваются именно числа, почти так же легко определять и исследовать вычислимые функции целой переменной, действительной переменной, вычислимой переменной, вычислимые предикаты и тому подобное. Однако же, фундаментальные проблемы, связанные с указанными вычислимыми объектами, в каждом случае одни и те же. Для детального рассмотрения в качестве вычислимого объекта я выбрал именно вычислимые числа потому, что методика их рассмотрения наименее громоздкая. Надеюсь в скором времени описать взаимоотношения вычислимых чисел с вычислимыми функциями и так далее. При этом будут проведены исследования в области теории функций действительной переменной, выраженной в терминах вычислимых чисел. По моему определению, действительное число является вычислимым, если его представление в виде десятичной дроби может быть записано машиной.

В параграфах 9 и 10 я привожу некоторые доводы, чтобы показать, что вычислимые числа включают в себя все числа, которые естественно считать вычислимыми. В частности, я показываю, что некоторые большие классы чисел вычислимы. Они включают, например, действительные части всех алгебраических чисел, действительные части нулей функций Бесселя, числа π, e и прочие. Однако вычислимые числа включают в себя не все определимые числа, в подтверждение чего приведен пример определимого числа, которое не является вычислимым.

Хотя класс вычислимых чисел очень велик и во многих отношениях похож на класс действительных чисел, он все же поддается перечислению, то есть является перечислимым (enumerable). В §8 я рассматриваю определенные доводы, которые, казалось бы, доказывают обратное предположение. При корректном применении одного из этих доводов делаются выводы, на первый взгляд, аналогичные выводам Геделя*. Данные результаты имеют чрезвычайно важные способы применения. В частности, как показано ниже (§11), не может иметь решения проблема разрешения.

В своей недавней статье Алонзо Черч** представил идею «способности поддаваться эффективному исчислению» (effective calculability), которая эквивалентна моей идее «вычислимости» (computability), но имеет совершенно иное определение. Черч также приходит к аналогичным выводам относительно проблемы разрешения. Доказательство эквивалентности «вычислимости» и «способности поддаваться эффективному исчислению» изложено в приложении к настоящей статье.

1. Вычислительные машины

Мы уже говорили, что вычислимые числа — это такие числа, десятичные разряды которых исчислимы конечными средствами. Тут требуется более четкое определение. В настоящей статье не будет предпринято никаких реальных попыток обосновать приведенные здесь определения до тех пор, пока мы не дойдем до §9. Пока лишь замечу, что (логическое) обоснование (этого) заключается в том, что человеческая память в силу необходимости ограничена.

Сопоставим человека в процессе вычисления действительного числа с машиной, которая способна выполнять только конечное число условий q1, q2, …, qR; назовем эти условия «m-конфигурациями». Данная (то есть так определенная) машина снабжена «лентой» (аналогом бумаги). Такая лента, проходящая через машину, разделена на секции. Назовем их «квадратами». Каждый такой квадрат может содержать какой-то «символ». В любой момент существует и при том только один такой квадрат, скажем, r-й, содержащий символ который находится «в данной машине». Назовем такой квадрат «отсканированным символом». «Отсканированный символ» — это единственный такой символ, о котором машина, образно выражаясь, «непосредственно осведомлена». Однако при изменении своей m-конфигурации машина может эффективно запоминать некоторые символы, которые она «увидела» (отсканировала) ранее. Возможное поведение машины в любой момент определяется m-конфигурацией qn и отсканированным символом***. Назовем данную пару символов qn, «конфигурацией». Обозначенная таким образом конфигурация определяет возможное поведение данной машины. В некоторых из таких конфигураций, в которых отсканированный квадрат является пустым (т. е. не содержит символа), данная машина записывает новый символ на отсканированном квадрате, а в других из таких конфигураций она стирает отсканированный символ. Данная машина также способна перейти к сканированию другого квадрата, но так она может переместиться лишь на соседний квадрат вправо или влево. В дополнение к любой из этих операций можно изменить m-конфигурацию машины. При этом некоторые из записанных символов сформируют последовательность цифр, являющуюся десятичной частью вычисляемого действительного числа. Остальные из них представят собой не более чем неточные отметки с тем, чтобы «помочь памяти». При этом стиранию могут подвергаться лишь вышеупомянутые неточные отметки.

Я утверждаю, что рассматриваемые здесь операции включают в себя все те операции, которые используются при вычислении. Обоснование данного утверждения легче понять читателю, имеющему представление о теории машин. Поэтому в следующем разделе я продолжу развивать рассматриваемую теорию, опираясь на понимание значения терминов «машина», «лента», «отсканированный» и т. д.

*Гедель «О формально неразрешимых предложениях «Принципов математики» (опубликованных Уайтехдом и Расселом в 1910, 1912 и 1913 гг.) и родственных систем, часть I», журнал по мат. физике, ежемесячный бюллетень на немецком языке № 38 (за 1931 год , стр. 173-198.
** Алонзо Черч, «Неразрешимая проблема элементарной теории чисел», American J. of Math., («Американский журнал математики»), № 58 (за 1936 год), стр. 345-363.
*** Алонсо Черч, «Замечание о проблеме разрешения», J. of Symbolic Logic («Журнал математической логики»), №1 (за 1936 год), стр. 40-41