Машина Тьюринга: концентрированный реферат

В реферате рассматриваются ключевые концепции работ Курта Геделя, Алонзо Черча и Алана Тьюринга: вычислимая функция, рекурсия, λ-исчисление, алгоритм, машина Тьюринга. Автор рассматривает концепции в разрезе их логики: какую проблему они решали и с помощью каких подходов были разработаны. Выделение таких связок предназначено для исследователей, которые стремятся выделить логику зарождения компьютерных областей.

Автор статьи: Владимир Куценко, программист, исследователь зарождения и развития новых ИТ-областей.

Структура реферата

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

• Какую проблему рассматривали разработчики?
• Какие действия они выполнили, чтобы ее решить? 
• Из каких областей были перенесены механизмы?
• Благодаря чему стали возможны ходы, позволившие решить проблему?

Проблемы, которые решали концепции теории вычислений

В 1900 году немецкий математик Давид Гильберт занимался основаниями математики, поскольку в то время многие рабочие понятия (например, целое число) понимались лишь интуитивно и не были четко определены – то есть, не были формализованы. Из-за этого в самой математической теории возникали противоречия, которые не позволяли развивать ее далее.

[НАЧАЛО ЦИТАТЫ] 
Трудности, встречающиеся при обосновании арифметики, частично действительно отличаются от тех, которые надо было преодолеть при обосновании геометрии. При исследовании основ геометрии можно было обойти некоторые затруднения чисто арифметической природы; но при обосновании арифметики ссылка на другую основную дисциплину становится уже недопустимой. Подвергнув краткому критическому разбору взгляды отдельных исследователей я смогу с большей четкостью выявить те существенные трудности, которые встречаются при обосновании арифметики.

Л. Кронекер, как известно, усматривал в понятии целого числа коренной фундамент арифметики; он составил себе мнение, что целое число, и притом как общее понятие (значение параметра), существует прямо и непосредственно; это помешало ему осознать, что понятие целого числа нуждается в обосновании и может быть обосновано. Поскольку это так, я позволю себе назвать его догматиком: он воспринимает целое число с его существенными свойствами как догму, и затем уже не оглядывается назад.

Г. Гелъмгольц представляет точку зрения эмпирика; однако точка зрения чистого опыта опровергается, как мне кажется, указанием на то, что из опыта, т. е. посредством эксперимента, никогда нельзя прийти к заключению о возможности или существовании сколь угодно большого числа, ибо число предметов, являющихся объектом нашего опыта, даже если оно велико, все же не превосходит некоторого конечного предела.

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

Из ученых, которые глубже проникли в существо понятия «целое число», я упомяну следующих.

Г. Фреге ставит себе задачу обосновать законы арифметики средствами логики, понимая эту последнюю в обычном смысле. Его заслугой является правильное понимание существенных свойств понятия «целое число», а также значения выводов посредством полной индукции.

Но, проводя последовательно свою точку зрения, он среди прочего принимает и тот основной закон, согласно которому понятие (множество) определено и может быть непосредственно применено, если только относительно каждого объекта известно, попадает ли он под это понятие или нет; при этом он не налагает никаких ограничений на понятие «каждый» и, таким образом, оказывается под ударами тех теоретико-множественных парадоксов, которые заключаются, например, в понятии множества всех множеств и которые показывают, как мне кажется, что концепции и средства исследования логики, понятые в обычном смысле, не в состоянии удовлетворить тем строгим требованиям, которые ставит теория множеств. Напротив, устранение подобных противоречий и объяснение этих парадоксов следует с самого начала рассматривать как главную цель при исследованиях, касающихся понятия числа.

Р. Дедекинд ясно осознал те математические трудности, которые встречаются при обосновании понятия числа, и весьма проницательно начал с построения теории целого числа. Все же его метод я позволю себе назвать трансцендентальным, поскольку он доказывает существование бесконечного путем, основная идея которого используется таким же образом и философами; этот путь я, однако, не могу признать удобопроходимым и надежным, так как при этом приходится пользоваться понятием совокупности всех вещей, а в этом понятии кроется неизбежное противоречие.

Г. Кантор чувствовал упомянутое противоречие, и это его чувство нашло свое выражение в том, что он различал «консистентные» и «неконсистентные» множества. Но так как Кантор не установил, по моему мнению, никаких строгих критериев для этого различия, то я его точку зрения по этому пункту должен характеризовать как оставляющую еще широкое поле для субъективного мнения и не дающую поэтому никакой объективной уверенности. 
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том I. Теория инвариантов. Теория чисел. Алгебра. Геометрия. Основания математики. — М.: Факториал, 1998. — С. 399-400.]

Гильберт указал, что при таком состоянии оснований математики невозможно понять ее ограничения. До него господствовало убеждение, что каждая математическая проблема имеет решение и его нужно только найти. Получалось, что исследователь может потратить целую жизнь на поиски, хотя даже не ясно, есть ли у этой проблемы решение. Отдельно выделяется необходимость в том, чтобы понять следующее: решение математической проблемы может быть найдено за конечное количество шагов (одна из первых формулировок современных алгоритмов).

[НАЧАЛО ЦИТАТЫ] 
Вместе с тем бывает и так, что мы добиваемся ответа при недостаточных предпосылках, или идя в неправильном направлении, и вследствие этого не достигаем цели. Тогда возникает задача доказать неразрешимость данной проблемы при принятых предпосылках и выбранном направлении. Такие доказательства невозможности проводились еще старыми математиками, например, когда они обнаруживали, что отношение гипотенузы равнобедренного прямоугольного треугольника к его катету есть иррациональное число. В новейшей математике доказательства невозможности решений определенных проблем играют выдающуюся роль; там мы констатируем, что такие старые и трудные проблемы, как доказательство аксиомы о параллельных, как квадратура круга или решение уравнения пятой степени в радикалах, получили все же строгое, вполне удовлетворяющее нас решение, хотя и в другом направлении, чем то, которое сначала предполагалось.

Этот удивительный факт наряду с другими философскими основаниями создает у нас уверенность, которую разделяет, несомненно, каждый математик, но которую до сих пор никто не подтвердил доказательством, — уверенность в том, что каждая определенная математическая проблема непременно должна быть доступна строгому решению или в том смысле, что удается получить ответ на поставленный вопрос, или же в том смысле, что будет установлена невозможность ее решения и вместе с тем доказана неизбежность неудачи всех попыток ее решить. Представим себе какую- либо нерешенную проблему, скажем, вопрос об иррациональности константы Эйлера — Маскерони или вопрос о существовании бесконечного числа простых чисел вида 2^n + 1. Как ни недоступными представляются нам эти проблемы и как ни беспомощно мы стоим сейчас перед ними, мы имеем все же твердое убеждение, что их решение с помощью конечного числа логических заключений все же должно удаться.

Является ли эта аксиома разрешимости каждой данной проблемы характерной особенностью только математического мышления или, быть может, имеет место общий, относящийся к внутренней сущности нашего разума закон, по которому все вопросы, которые он ставит, способны быть им разрешимы? Встречаются ведь в других областях знания старые проблемы, которые были самым удовлетворительным образом и к величайшей пользе науки разрешены путем доказательства невозможности их решения. Я вспоминаю проблему о perpetuum mobile (вечный двигатель). После напрасных попыток конструирования вечного двигателя стали, наоборот, исследовать соотношения, которые должны существовать между силами природы, в предположении, что perpetuum mobile невозможно. И эта постановка обратной задачи привела к открытию закона сохранения энергии, из которого и вытекает невозможность perpetuum mobile в первоначальном понимании его смысла.

Это убеждение в разрешимости каждой математической проблемы является для нас большим подспорьем в работе; мы слышим внутри себя постоянный призыв: вот проблема, ищи решение. Ты можешь найти его с помощью чистого мышления; ибо в математике не существует Ignorabimus! 
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том II. Анализ. Физика. Проблемы. Personalia. — М.: Факториал, 1998. — С. 406-407.]

[НАЧАЛО ЦИТАТЫ] 
Но поскольку доказательство непротиворечивости — вещь совершенно обязательная, представляется необходимым аксиоматизировать саму логику и показать, что теория чисел, равно как и теория множеств, составляют лишь части логики.

Этот путь, подготавливавшийся уже давно (не в последнюю очередь глубокими исследованиями Фреге), наконец, был проложен с величайшим успехом тонким математиком и логиком Расселом. Завершение намеченной Расселом грандиозной программы по аксиоматизации логики можно было бы рассматривать как венец всех усилий по аксиоматизации науки.

Но пока завершение этой программы все еще требует новых и разносторонних усилий. По зрелом размышлении нетрудно понять, что вопрос о непротиворечивости теории целых чисел и теории множеств существует не сам по себе, а принадлежит к обширной области труднейших теоретико-познавательных вопросов со специфической математической окраской; чтобы кратко охарактеризовать эту область вопросов, назову проблему принципиальной разрешимости любой математической задачи, проблему контролируемости результатов математического исследования, вопрос о критерии простоты математического доказательства, проблему отношения содержательности и формализма в математике и логике и, наконец, проблему разрешимости математической задачи за конечное число операций.

Аксиоматизацию логики нельзя считать удовлетворительной до тех пор, пока все вопросы такого рода не будут поняты и выяснены.

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

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

Как известно, в теории алгебраических инвариантов имеется фундаментальная теорема о том, что всегда существует конечное число целых рациональных инвариантов, через которые могут быть рационально выражены все остальные алгебраические инварианты. Данное мною первое общее доказательство этой теоремы полностью удовлетворяет, как я полагаю, нашим пожеланиям в том, что касается простоты и прозрачности; однако это доказательство невозможно видоизменить так, чтобы можно было с его помощью указать верхнюю границу числа элементов в полной системе инвариантов и уж тем более фактически найти само это число. Потребовались соображения совершенно иного рода и совершенно новые принципы, чтобы убедиться, что построение полной системы инвариантов осуществимо с помощью операций, число которых конечно и не превосходит границы, поддающейся вычислению.

Аналогичную ситуацию наблюдаем мы и в одном примере из теории поверхностей. В геометрии поверхностей четвертого порядка имеется фундаментальный вопрос: из скольких, самое большее, отдельных кусков может состоять такая поверхность?

При ответе на этот вопрос в первую очередь надо доказать, что число связных кусков поверхности должно быть конечно; это легко установить из теоретико-функциональных соображений следующим образом. Предположим, что кусков поверхности бесконечно много, и выберем в каждой части пространства, ограниченной таким куском, по точке. Точка накопления бесконечного множества выбранных точек была бы особой точкой такого типа, который исключен для алгебраических поверхностей.

Такой функционально-теоретический подход никоим образом не позволяет получить верхнюю границу числа кусков поверхности; для этого необходимы гораздо более конкретные рассуждения относительно числа точек пересечения, приводящие к заключению о том, что число кусков поверхности не может быть больше 12.

Этот второй метод, в корне отличный от первого, неприменим и не может быть видоизменен так, чтобы он стал применимым к решению вопроса о том, действительно ли существует поверхность четвертого порядка, состоящая ровно из 12 кусков.

Так как у кватернарной формы четвертого порядка 35 однородных коэффициентов, мы можем наглядно представить ее в виде точки в 34-мерном пространстве. Дискриминант кватернарной формы четвертого порядка имеет степень 108 по коэффициентам формы; если его положить равным нулю, то в 34-мерном пространстве он будет представлять поверхность 108-го порядка. Так как коэффициенты дискриминанта сами являются некоторыми целыми числами, топологический характер дискриминантной поверхности может быть точно установлен по правилам, знакомым нам по дву- и трехмерному пространству, что позволяет получить точное представление о природе и значении отдельных подобластей, на которые дискриминантная поверхность делит 34-мерное пространство. Все поверхности, представляемые точками одной подобласти, состоят из одного и того же числа кусков, что позволяет с помощью весьма трудоемких и нудных вычислений установить, существуют или не существуют поверхности четвертого порядка, состоящие из n ≤ 12 кусков.

Намеченные выше в общих чертах геометрические соображения доставляют третий подход к решению поднятого нами вопроса о наибольшем числе кусков, из которых может состоять поверхность четвертого порядка. Они показывают, что этот вопрос разрешим за конечное число операций. Тем самым принципиально наше требование выполнено: исходная проблема сведена к проблеме типа задачи о вычислении 10^(10^10 )-й цифры десятичного разложения числа π — задачи, разрешимость которой очевидна, хотя решение остается неизвестным.

Наконец, потребовалось (проведенное Рооном) глубокое и трудное алгебро-геометрическое исследование, чтобы доказать, что поверхность четвертого порядка не может состоять из 11 кусков, но может состоять из 10. Таким образом, лишь этот четвертый метод дает полное решение проблемы.

Приведенные специальные примеры показывают, сколь различными могут быть методы доказательства, применимые к одной и той же задаче, и заставляют задуматься над тем, сколь необходимо изучать самую сущность математического доказательства, если мы хотим успешно решать такие вопросы, как разрешимость за конечное число операций. 
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том I. Теория инвариантов. Теория чисел. Алгебра. Геометрия. Основания математики. — М.: Факториал, 1998. — С. 414-416.]

В качестве пути формализации и для определения ограничений Гильберт предложил метод глубокой аксиоматизации математики, после которого она должна стать полностью непротиворечива. Идея заключалась в том, что после подбора подходящего количества непротиворечивой системы аксиом все последующие математические и логические теоремы будут выводиться из них почти механически. Эта идея стала рассматриваться как возможная, когда другой немецкий математик, Эрнст Цермело, подобрал такие аксиомы для теории множеств и разрешил существующие в ней на то время противоречия.

[НАЧАЛО ЦИТАТЫ] 
С иной ситуацией мы сталкиваемся, когда противоречия встречаются в чисто теоретических областях знания. Классическим примером такого рода может служить теория множеств, в частности восходящий еще к Кантору парадокс множества всех множеств. Этот парадокс настолько существен, что побудил некоторых весьма уважаемых математиков, например Кронекера и Пуанкаре, вообще отказать всей теории множеств — одной из самых плодотворных и жизнеспособных областей математики — в праве на существование.

Но и из столь затруднительной ситуации удалось найти выход с помощью аксиоматического метода. Это сделал Цермело, который, введя подходящую аксиому, с одной стороны ограничил произвол в определениях множеств, а с другой стороны, в строго определенном смысле сузил круг допустимых утверждений об элементах множеств и развил теорию множеств таким образом, что отпали противоречия, о которых я упоминал, но значимость и применимость теории, несмотря на наложенные ограничения, сохранились.

До сих пор речь во всех случаях шла о противоречиях, которые были обнаружены в ходе развития теории и для устранения которых возникала необходимость внести изменения в систему аксиом. Но чтобы восстановить репутацию математики как эталона строгой науки, недостаточно просто избавляться от имеющихся противоречий: принципиальное требование аксиоматической теории должно простираться дальше, а именно надо знать, что внутри данной области знания, построенной на основе принятой системы аксиом, никакие противоречия вообще невозможны. Следуя этому требованию, я доказал в «Основаниях геометрии» непротиворечивость принятых там аксиом, продемонстрировав, что любое противоречие в следствиях из геометрических аксиом с необходимостью должно было бы означать некоторое противоречие в арифметике системы вещественных чисел. 
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том I. Теория инвариантов. Теория чисел. Алгебра. Геометрия. Основания математики. — М.: Факториал, 1998. — С. 413-414.]

Давид Гильберт выделил 23 проблемы из разнообразных областей математики, откуда могли прийти нужные аксиомы.

Вторая проблема Гильберта: доказательство непротиворечивости аксиоматических систем

Работе по выявлению ограничений аксиоматических систем Гильберт посвятил вторую проблему. Необходимо было получить доказательство того, что набор арифметических аксиом является непротиворечивым. Иначе говоря, что из этого набора аксиом чисто механическим путем с помощью конечного числа логических действий нельзя получить результаты, которые противоречат друг другу.

[НАЧАЛО ЦИТАТЫ] 
2. Непротиворечивость арифметических аксиом. Когда речь идет о том, чтобы исследовать основания какой-нибудь науки, то следует установить систему аксиом, содержащих точное и полное описание тех соотношений, которые существуют между элементарными понятиями этой науки. Эти аксиомы являются одновременно определениями этих элементарных понятий, и мы считаем правильными только такие высказывания в области науки, основания которой мы исследуем, какие получаются из установленных аксиом с помощью конечного числа логических умозаключений. При более близком рассмотрении возникает вопрос: не являются ли некоторые из этих аксиом зависящими друг от друга, не содержат ли некоторые из этих аксиом общие части, которые следовало бы изъять, если ставить задачу об установлении системы аксиом, полностью независимых друг от друга?

Из многочисленных вопросов, которые могут быть поставлены относительно системы аксиом, мне хотелось бы прежде всего указать на важнейшую проблему, именно на доказательство того, что система аксиом непротиворечива, т. е. что на основании этих аксиом никогда нельзя с помощью конечного числа логических умозаключений получить результаты, противоречащие друг другу. 
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том II. Анализ. Физика. Проблемы. Personalia. — М.: Факториал, 1998. — С. 409.]

Десятая проблема Гильберта: способ указания поиска решения за конечное количество шагов

Работе с проблемой поиска решения за конечное количество шагов посвящалась десятая проблема о разрешимости диофантовых уравнений.

[НАЧАЛО ЦИТАТЫ] 
10. Задача о разрешимости диофантова уравнения. Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах. 
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том II. Анализ. Физика. Проблемы. Personalia. — М.: Факториал, 1998. — С. 419.]

Рекурсия. Курт Гёдель и его работа «On Formally Undecidable Propositions of the Principia Mathematica and Related Systems»

Описание проблемы

Второй проблемой Гильберта занялся австрийский логик и математик Курт Гёдель. Перед ним стояла задача – получить доказательство того, что система арифметических аксиом непротиворечива (англ. «consistent»). Если бы это удалось, стало бы возможным механизировать математические доказательства при условии открытия или подбора множества непротиворечивых аксиом в арифметике. 

Как решали проблему

ХОД: Рекурсия как способ определения одних высказываний через другие.

Первый ход, который применил Гёдель для рассмотрения формальных систем – рекурсия: в его понимании это определение функций через другие функции с помощью подстановки одних в определение других. Функция может также определяться и через себя, но это необязательно. 

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

[НАЧАЛО ЦИТАТЫ] 
We now introduce a digression which, for the moment, has nothing to do with the system P, and, first, we present the following definition: A number-theoretic function ϕ(х₁, х₂, ... xₙ) is said to be recursively defined from the number-theoretic functions Ψ(x₁, x₂, ... , xₙ₋₁) and μ(x₁, x₂, ... , xₙ₊₁) if the following holds for all x₂, . . . , xₙ , k the following hold:

ϕ(0, x₂, ... , xₙ)= Ψ(x₂, ... , xₙ)

ϕ(k + 1, x₂ , ... , xₙ) = μ(k, ϕ(к, x₂, ... , xₙ), х₂, ... , xₙ).

A number-theoretic function ϕ is said to be recursive if there exists a finite sequence of number-theoretic functions ϕ₁,ϕ₂,. .. , ϕₙ which ends with ϕ and has the property that each function ϕₖ of the sequence either is defined recursively from two of the preceding functions, or results from one of the preceding functions by substitution, or, finally, is a constant or the successor function x + 1. The length of the shortest sequence of ϕᵢ's belonging to a recursive function ϕ is called its rank. A relation among natural numbers R(x₁, ... , xₙ) is called recursive if there exists a recursive function ϕ(x₁, ... , xₙ) such that, for all x₁, x₂ ... xₙ

R(x₁, ... xₙ) ~ [ϕ(х₁, ... , xₙ) = 0]

[КОНЕЦ ЦИТАТЫ. Источник: K. Gödel. On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. Reprinted in M. Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 14-15.]

Такие функции позволили определять отношения между понятиями о системе аксиом в терминах самой системы аксиом.

С помощью базовых операторов и символов примитивной аксиоматической системы (операторы отрицания, логического сложения и умножения, предикаты) можно было рекурсивно выразить понятия «формула», «следствие», «аксиома», «доказательство» и «доказуемая формула» – через отношения между элементами. После этого в терминах аксиоматической системы стали возможны следующие высказывания: «Существуют ПРЕДЛОЖЕНИЯ а –  такие что ни а, ни ОТРИЦАНИЕ а не являются ДОКАЗУЕМЫМИ ФОРМУЛАМИ» (это основное высказывание, которое хотел доказать Гёдель в своей работе). 

Благодаря множественным свойствам рекурсии, доказанным Гёделем по ходу работы, – например, что логическое сложение двух рекурсивных функций также является рекурсивной функцией, –  приведенные высказывания также могли быть разложены на рекурсивные представления вплоть до самых базовых аксиом системы.

[НАЧАЛО ЦИТАТЫ] 
The functions x + y, x * y, xʸ and the relations x < y, x = y are readily found to be recursive; starting from these concepts, we now define a series of functions (relations) 1- 45, of which each is defined from the preceding ones by the methods indicated in Theorems I-IV. In so doing, several of the definitional steps allowed by Theorems I-IV are often combined into one step. Each of the functions (relations) 1-45, among which occur, for example, the concepts «formula», «axiom», «direct consequence», is therefore recursive.

[КОНЕЦ ЦИТАТЫ. Источник: K. Gödel. On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. Reprinted in M. Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 17-22.]

ХОД: Связывание формальных систем с арифметикой (арифметизация)

Гёдель связал арифметику с формальной аксиоматической системой. Любое высказывание, будь то формула, утверждение или список формул, однозначным образом кодировалось в целое число. Рекурсивные функции, которые выражают отношения между элементами такой системы (переменными, формулами, доказательствами), становились таким образом рекурсивными функциями целых чисел. Все свойства и высказывания об элементах формальной системы получали однозначное представление в виде свойств и высказываний о целых числах.

[НАЧАЛО ЦИТАТЫ] 
We now set up a one-to-one correspondence of natural numbers to the primitive symbols of the system Pin the following manner:

and furthermore, to the variables of n-th type we assign the numbers of the form pⁿ (where p is a prime number > 13). Thus, to every finite sequence of primitive symbols (hence also to every formula), there corresponds in a one-to-one fashion a finite sequence of positive integers. 

We map (again in a one-to-one fashion) the finite sequences of positive integers into the natural numbers by letting the number 2^n₁ * 3^n₂ * ... * p^nₖ correspond to the sequence n₁, n₂, ... , nₖ, where pk denotes the k-th prime number (according to magnitude). Hence, a natural number is correlated in one-to-one fashion not only to every primitive symbol but also to every finite sequence of such symbols. 

The number corresponding to the primitive symbol (or sequence of primitive symbols) a will be written Φ(a). Assume given now any class or relation R(α₁, a₂, ..., an) between primitive symbols or sequences of such symbols. We correlate to it that class (relation) R'(х₁, x₂, ..., xₙ) of natural numbers which holds for x₁, x₂, … , xₙ when and only when there exist a₁, a₂, . . . , aₙ such that хi = Ф(аi) (i = 1, 2, ..., n) and R(a₁, a₂, ..., aₙ) is true. 

Those classes and relations of natural numbers which correspond in this manner to the previously defined metamathematical concepts, e.g. «variable», «formula», «sentence», «axiom», «provable formula», etc., are denoted by the same words in small capital letters. [In the original italics were used.] For example, the proposition that there exist undecidable problems in the system Ρ becomes: There exist SENTENCES α such that neither α nor the NEGATION of α is a provable formula.
[КОНЕЦ ЦИТАТЫ. Источник: K. Gödel. On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. Reprinted in M. Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 13-14.]

В основе своей теоремы Гёдель показывает, что утверждения о свойствах доказательства являются утверждениями о целых числах. И далее: в формальной системе есть высказывание о том, что существует число со свойством P – и не существует числа со свойством P в то же время.

[НАЧАЛО ЦИТАТЫ] 
The fact which can be vaguely formulated as the assertion that every recursive relation is definable within the system Ρ (under its intuitive interpretation), is rigorously expressed by the following theorem, without reference to the intuitive meaning of the formulas of P: Theorem V: For every recursive relation R(x₁, ... , xₙ) there is n-ary PREDICATE r(with the free variables u₁, u₂, ... , uₙ) such that, for all n-tuples of numbers (x₁, ... , xₙ) we have:

[КОНЕЦ ЦИТАТЫ]

Отсюда следовал вывод о неполноте формальных аксиоматических систем: в них всегда будут иметь место утверждения, которые в терминах этих систем нельзя доказать или опровергнуть.

Гёдель развивает доказательство неполноты формальных систем в невозможность доказать непротиворечивость аксиом в рамках этих систем.

Из каких областей применены ходы

Описанные ходы принадлежат математике и математической логике.

Благодаря чему стали возможны используемые ходы

Рекурсия стала возможна благодаря математической индукции – методу доказательства для целого числа 1 и для всех последующих случаев. Метод индукции был известен математике еще в XVII веке.

Само определение рекурсии в математике обозначается как «определение по индукции». Для функции это означает, что ее значение от некоторого аргумента определяется ее же значениями от предыдущих аргументов и более простых функций. Таким образом, и в индукции, и в рекурсии есть отношение следования элементов множества (в самом простом случае функция следования: х + 1).

Арифметизация формальной системы (то есть, отображение отношений, выраженных в терминах формальной системы в виде арифметических и логических операций) стала возможна благодаря открытию счетных множеств немецким математиком Георгом Кантором (стало возможным назначить номер алфавиту из символов и цепочкам из этого алфавита) и похожим случаем арифметизации для геометрии. О последнем Гильберт прямо указывает в формулировке второй проблемы.

[НАЧАЛО ЦИТАТЫ] 
Доказательство непротиворечивости аксиом геометрии достигается тем, что строится соответствующая числовая область так, что геометрическим аксиомам соответствуют аналогичные соотношения между числами этой области; тем самым каждое противоречие, полученное в следствиях из аксиом геометрии, должно быть обнаружено также в арифметике этой числовой области. Таким образом, желательное доказательство непротиворечивости аксиом геометрии сводится к предложению о непротиворечивости аксиом арифметики.

Напротив, непротиворечивость аксиом арифметики требует прямого доказательства.
[КОНЕЦ ЦИТАТЫ. Источник: Д. Гильберт. Избранные труды. Том II. Анализ. Физика. Проблемы. Personalia. — М.: Факториал, 1998. — С. 409.]

λ-исчисление. Алонзо Черч и его работа «An Unsolvable Problem of Elementary Number Theory»

Описание проблемы

Десятой проблемой Гильберта занялся американский математик и логик Алонзо Черч, и первым его шагом в эту сторону стало изучение ее ограничений. Для этого нужно было определить вычислимость – иначе говоря, потребовалось определить рабочий способ символических преобразований для механических вычислений.

[НАЧАЛО ЦИТАТЫ] 
The purpose of the present paper is to propose a definition of effective calculability 3 which is thought to correspond satisfactorily to the somewhat vague intuitive notion in terms of which problems of this class are often stated, and to show, by means of an example, that not every problem of this class is solvable.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 90.]

Как решали проблему

ХОД: Устранение необходимости информации для вычислений извне.

Модель вычислений Алонзо Черча представлялась в форме некоторого набора преобразований над формулами, записанными по определенному формату. Основная проблема, которая препятствует механическому вычислению, с точки зрения Черча, заключалась в свободных переменных математической формулы. 

Свободные переменные некоторой формулы (то есть, математического высказывания в виде наборов символов) всегда требуют дополнительной информации извне. Например, в формуле

a(b + c) = ab + ac   (1)

a, b и c нуждаются в пояснении и поэтому являются свободными переменными. Такие переменные приводят к парадоксам в математических высказываниях в символизме формальной логики, а также не подлежат подстановке в другие формулы в таком виде. Поэтому сначала их надо устранить.

[НАЧАЛО ЦИТАТЫ] 
1. Introduction. 
In this paper we present a set of postulates for the foundation of formal logic, in which we avoid use of the free, or real, variable, and in which we introduce a certain restriction on the law of excluded middle as a means of avoiding the paradoxes connected with the mathematics of the transfinite.

Our reason for avoiding use of the free variable is that we require that every combination of symbols belonging to our system, if it represents a proposition at all, shall represent a particular proposition, unambigouously, and without the addition of verbal explanations. That the use of the free variable involves violation of this requirement, we believe is readily seen. For example, the identity

(1) a(b + c) = ab + ac

in which a, b, and c are used as free variables, does note state a definite proposition unless it is known what values-may be taken on by these variables, and this information, if not implied in the context, must be given by a verbal addition. The range allowed to the variables a, b, and c might consist of all real numbers, or of all complex numbers, or of some other set, or the ranges allowed to the variables might differ, and for each possibility equation (1) has a different meaning. Clearly, when this equation is written alone, the proposition intended has not been completely translated into symbolic language, and, in order to make the translation complete, the necessary verbal addition must be expressed by means of the symbols of formal logic and included, with the equation, in the formula used to represent the proposition. When this is done we obtain, say,

(2) R(a) R(b) R(c) Ↄabc * a(b + c) = ab + ac

where R(x) has the meaning, «x is a real number," and the symbol Ↄabc has the meaning described in §§ 5 and 6 below. And in this expression there are no free variables.

A further objection to the use of the free variable is contained in the duplication of symbolism which arises when the free, or real, variable and the bound, or apparent, variable are used side by side. Corresponding to the proposition, represented by equation (1) when a, b, and c stand for any three real numbers, there is also a proposition expressed without the use of free variables, namely(2), and between these two propositions we know of no convincing distinction. An attempt to identify the two propositions is, however, unsatisfactory, because substitution of(1) for (2), when the latter occurs as a part of a more complicated expression, cannot always be allowed without producing confusion. In fact, the only feasible solution seems to be the complete abandonment of the free variable as a part of the symbolism of formal logic.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. A Set of Postulates for The Foundation of Logic. Annals of Mathematics. Second Series. Vol. 33. No. 2 (Apr., 1932). PP. 346-347.]

Чтобы устранить свободные переменные в описании синтаксиса лямбда-вычислений, Черч ввел оператор связывания для формул символических вычислений.

Формулы представляются в виде набора символов { , }, ( , ), λ, [ , ] и букв, которыми можно обозначать переменные: a, b, c и т.д. λ является оператором связывания свободной переменной с формулой: например, в выражении λx.x^2 + 2 символ λ связывает переменную x с формулой (x^2 + 2). Связывание переменной с формулой является определением функции для вычисления: f(x) = x^2 + 2. Механическое вычисление становится возможным, когда все переменные в символической записи формул связаны.

[НАЧАЛО ЦИТАТЫ] 
2. Conversion and λ-definability. 
We select a particular list of symbols, consisting of the symbols { , }, ( , ), λ, [ , ], and an enumerably infinite set of symbols а, b, с, · · · to be called variables. And we define the word formula to mean any finite sequence of symbols out of this list. 

The terms well-formed formula, free variable, and bound variable are then defined by induction as follows. A variable x standing alone is a well-formed formula and the occurrence of x in it is an occurrence of λ as a free variable in it; if the formulas F and X are well-formed, {F}(X) is well-formed, and an occurrence of x as a free (bound) variable in F or X is an occurrence of x as a free (bound) variable in {F}(X); if the formula Μ is well-formed and contains an occurrence of x as a free variable in if F, then λx[M] is well-formed, an occurrence of x in λx[M] is an occurrence of x as a bound variable in λx[Μ], and an occurrence of a variable y, other than x, as a free (bound) variable in Μ is an occurrence of у as a free (bound) variable in λx[Μ].
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 90.]

ХОД: Определение модели вычислений для формул как подстановки одних формул в другие.

Для символических записей математических высказываний Черч определяет три вида преобразований в формулах.

1. Замена имени переменной в формуле.
2. Подстановка результата формулы вместо записи формулы (аналог применения значения аргумента к функции). Например, подстановка вместо λx.x^2 + 2 (4)  →  4^2 + 2 → 18.
3. Подстановка записи формулы вместо результата формулы (преобразование, обратное пункту 2).

Если формула A может быть преобразована в формулу B с помощью указанного набора операций, то говорят, что формула A преобразуема в формулу B. Функции от целых чисел вида F(x) = r называются λ-определимыми, если их запись {F}(m) преобразуема в r. Таким образом Черч фиксирует начало вычислений как функцию, которая λ-определена (то есть, как функцию, записанную в λ-термах). 

Если формула не содержит части вида {λx[Μ]}(Ν), то она находится в своей нормальной форме. Иначе говоря, если в формуле нет связанных переменных после ее преобразований.

Преобразование, которое содержит ровно одно применение операции II и ни одного применения операции III, называется редукцией.

Вычислением называется механический процесс редукции λ-определяемой функции в нормальную форму. (В самом деле, подстановка по правилам I и II является однозначной последовательностью действий, поэтому может быть произведена без участия какого-либо творческого и интуитивного элемента.) 

Черч фиксирует результат вычислений как приведение функции к нормальной форме, после которой невозможны никакие преобразования. По итогу у него получается модель символьных вычислений, состоящая из начального состояния, механических операций над символами и результата, после которого невозможны дальнейшие операции.

[НАЧАЛО ЦИТАТЫ] 
The expression SxN M | is used to stand for the result of substituting N for x throughout M.

We consider the three following operations on well-formed formulas:
I. To replace any part λx[Μ] of a formula by λy[SxyM | ], where у is a variable which does not occur in M.
II. To replace any part {λx[Μ]}(Ν) of a formula by SxN M |, provided that the bound variables in Μ are distinct both from x and from the free variables in N.
III. To replace any part SxN M | (not immediately following λ) of a formula by {λx[Μ]}(Ν), provided that the bound variables in Μ are distinct both from x and from the free variables in N.

Any finite sequence of these operations is called a conversion, and if В is obtainable from A by a conversion we say that A is convertible into B, or, «A conv B.» If В is identical with A or is obtainable from A by a single application of-one of the operations Ι, II, III, we say that A is immediately convertible into B.

A conversion which contains exactly one application of Operation II, and no application of Operation III, is called a reduction.

A formula is said to be in normal form if it is well-formed and contains no part of the form {λx[Μ]} (Ν). And В is said to be a normal form of A if В is in normal form and A conv B.

The originally given order а, b, с, ... of the variables is called their natural order. And a formula is said to be in principal normal form if it is in normal form, and no variable occurs in it both as a free variable and as a bound variable, and the variables which occur in it immediately following the symbol λ are, when taken in the order in which they occur in the formula, in natural order without repetitions, beginning with a and omitting only such variables as occur in the formula as free variables. The formula В is said to be the principal normal form of A if В is in principal normal form and A conv B.

Of the three following theorems, proof of the first is immediate, and the second and third have been proved by the present author and J. B. Rosser.

Theorem I. If a formula is in normal form, no reduction of it is possible.
Theorem II. If a formula has a normal form, this normal form is unique to within applications of Operation I, and any sequence of reductions of the formula must (if continued) terminate in the normal form.
Theorem III. If a formula has a normal form, every well-formed part of it has a normal form.

We shall call a function of positive integers if the range of each independent variable is the class of positive integers and the range of the dependent variable is contained in the class of positive integers. And when it is desired to indicate the number of independent variables we shall speak of a function of one positive integer, a function of two positive integers, and so on. Thus if F is a function of n positive integers, and a₁, a₂, ...  ,aₙ are positive integers, then F(a₁, a₂, ... , aₙ) must be a positive integer.

A function F of one positive integer is said to be λ-definable if it is possible to find a formula F such that, if F(m) = r and m and r are the formulas for which the positive integers m and r (written in Arabic notation) stand according to our abbreviations introduced above, then {F}(m) conv r. Similarly, a function F of two positive integers is said to be λ-definable if it is possible to find a formula F such that, whenever F(m,n) = r, the formula {F}(m,n) is convertible into r (m, n, r being positive integers and m, n, r the corresponding formulas). And so on for functions of three or more positive integers.

It is clear that, in the case of any λ-definable function of positive integers, the process of reduction of formulas to normal form provides an algorithm for the effective calculation of particular values of the function.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 91-93.]

ХОД: Определение ограничений модели вычислений для формул.

С помощью набора теорем Черч определяет ограничения его модели вычислений.

1. Не существует алгоритма вычислений, который может показать, что формула имеет нормальную форму. То есть, нет способа за конечное количество шагов проверить, приводит ли редукция формулы к результату, после которого никакие другие операции невозможны.

2. Не существует алгоритма вычислений, который может показать, что формула A преобразуема в формулу B. То есть, нет способа за конечное количество шагов проверить, можно ли получить из одной формулы другую с помощью указанного набора символьных преобразований.

Это, в свою очередь, дает отрицательный ответ на десятую проблему Гильберта: не существует способа указать конечное количество шагов, чтобы проверить, что уравнение (формула №1) разрешимо в целых числах (формула №2). Напомним, что формулами могут быть как уравнения, так и высказывания об этих уравнениях.

[НАЧАЛО ЦИТАТЫ] 
Lemma. The problem, to find a recursive function of two formulas A and В whose value is 2 or 1 according as A conv В or not, is equivalent to the problem, to find a recursive function of one formula С whose value is 2 or 1 according as С has a normal form or not. [...]

Theorem XVIII. There is no recursive function of a formula C, whose value is 2 or 1 according as С has a normal form or not. [...]

Theorem XIX. There is no recursive function of two formulas A and B, whose value is 2 or 1 according as A conv В or not.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 103-107.]

Побочные ходы и результаты 

Во время работы над моделью вычислений Черч и его коллега, еще один американский математик Стивен Клини, приходят к выводу, что рекурсия и λ-вычисления однозначно связаны. Любая λ-определимая функция целых чисел является рекурсивной и наоборот.

[НАЧАЛО ЦИТАТЫ] 
Theorem XVI. Every recursive function of positive integers is λ-definable.

Theorem XVII. Every λ-definable function of positive integers is recursive.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 99.]

Из этого Черч заключает, что вся его работа по доказательству десятой проблемы Гильберта может быть сделана как в терминах λ-исчислений, так и в терминах рекурсии.

[НАЧАЛО ЦИТАТЫ] 
As will appear, this definition of effective calculability can be stated in either of two equivalent forms, (1) that a function of positive integers shall be called effectively calculable if it is λ-definable in the sense of § 2 below, (2) that a function of positive integers shall be called effectively calculable if it is recursive in the sense of § 4 below. 

The notion of λ-definability is due jointly to the present author and S. C. Kleene, successive steps towards it having been taken by the present author in the Annals of Mathematics, vol. 34 (1933), p. 863, and by Kleene in the American Journal of Mathematics, vol. 57 (1935), p. 219. The notion of recursiveness in the sense of § 4 below is due jointly to Jacques Herbrand and Kurt Godel, as is there explained. 

And the proof of equivalence of the two notions is due chiefly to Kleene, but also partly to the present author and to J. B. Rosser, as explained below. The proposal to identify these notions with the intuitive notion of effective calculability is first made in the present paper (but see the first footnote to § 7 below).
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 90.]

Далее Черч заключает, что рекурсия является альтернативной равноценной моделью вычислений.

[НАЧАЛО ЦИТАТЫ] 
With the aid of the methods of Kleene (American Journal of Mathematics, 1935), the considerations of the present paper could, with comparatively slight modification, be carried through entirely in terms of λ-definability, without making use of the notion of recursiveness. 

On the other hand, since the results of the present paper were obtained, it has been shown by Kleene (see his forthcoming paper, «General recursive functions of natural numbers») that analogous results can be obtained entirely in terms of recursiveness, without making use of λ-definability. 

The fact, however, that two such widely different and (in the opinion of the author) equally natural definitions of effective calculability turn out to be equivalent adds to the strength of the reasons adduced below for believing that they constitute as general a characterization of this notion as is consistent with the usual intuitive understanding of it.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 90.]

Из каких областей применены ходы

Все указанные ходы принадлежат математике и математической логике

Благодаря чему стали возможны ходы

Черч начал работу над λ-исчислением еще в 1930 году, то есть, до открытий Геделя, но смог закончить свою работу лишь в 1936 году. Тем не менее один из методов, который он применил для работы над теоремами, была арифметизация формул, открытая Геделем.

[НАЧАЛО ЦИТАТЫ] 
3. The Gödel representation of a formula. Adapting to the formal notation just described a device which is due to Gödel, we associate with every formula a positive integer to represent it, as follows. To each of the symbols {, (, [ we let correspond the number 11, to each of the symbols}, ), ] the number 13, to the symbol λ the number 1, and to the variables а, b, c, … the prime numbers 17, 19, 23, ... respectively. And with а formula which is composed of the n symbols τ₁,₂, ... , τₙ in order we associate the number 2^t₁ * 3^t₂ ...  p^tₙ, where tᵢ is the number corresponding to the symbol τᵢ, and where pₙ stands for the n-th prime number.

This number 2^t₁ * 3^t₂ ...  p^tₙ will be called the Godel representation of the formula τ₁ ... τₙ.

Two distinct formulas may sometimes have the same Gödel representation, because the numbers 11 and 13 each correspond to three different symbols, but it is readily proved that no two distinct well-formed formulas can have the same Gödel representation. It is clear, moreover, that there is an effective method by which, given any formula, its Gödel representation can be calculated; and likewise that there is an effective method by which, given any positive integer, it is possible to determine whether it is the Godel representation of a well-formed formula and, if it is, to obtain that formula.

In this connection the Gödel representation plays a role similar to that of the matrix of incidence in combinatorial topology (cf. §1 above). For there is, in the theory of well-formed formulas, an important class of problems, each of which is equivalent to a problem of elementary number theory obtainable by means of the Gödel representation.
[КОНЕЦ ЦИТАТЫ. Источник: A. Church. An Unsolvable Problem of Elementary Number Theory. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. P. 93-94.]

Связь с рекурсией и работами Клини по эквивалентности рекурсивных функций и λ-определимых функций помогли с доказательством необходимых теорем, хотя сам Черч утверждает, что все указанные им в работе теоремы можно было получить? исходя только из определения λ-исчислений, поэтому такая связь не была решающим фактором.

Машина Тьюринга. Алан Тьюринг и его работа «On Computable Numbers, with an Application to the Entscheidungsproblem»

Описание проблемы

 / ВикимедиаДля окончательной разработки десятой проблемы Гильберта, которая требует указать способ получения некоторого набора конечного числа операций (то есть, способ получения алгоритма), британскому математику Алану Тьюрингу нужно было точно установить суть понятия алгоритма, его ограничений, а также ограничений способов его указаний (то есть, алгоритма для указания алгоритмов). До этого термин понимался лишь интуитивно.

Как решали проблему

Алан Тьюринг берется за еще не формализованную (не описанную по строго однозначным логическим правилам без возможности их множественных трактовок) часть разрабатываемой теории вычислений: алгоритм. Он рассматривает вычисления не с точки зрения особенностей формальной логической системы, что делали его предшественники – Гёдель, Черч и Клини, – а как процесс работы человека над набором символов, не над формулами. Другими словами, он рассматривал более низкий уровень системы.

ХОД: Определение модели вычислений как минимально допустимых операций над символами.

Тьюринг увидел, что при вычислениях человек работает, прежде всего, с некоторыми символами на бумаге. В каких-то местах бумаги он считывает символы, в других – записывает их, исходя из ранее прочитанных символов и на основании некоторых правил.

Для машины Тьюринг выбрал набор наиболее простых операций с бумажной лентой, состоящей из квадратных ячеек: считывание символа из ячейки, запись символа в ячейку, а также сдвиг считывающей головки вправо или влево на одну от текущей. Правила действий после прочтения символа задавались прямым отображением между только что считанным символом и последовательностью элементарных действий, перечисленных выше (это называлось конфигурацией). Из элементарных операций можно было составить последовательности чтения и записи символов на бумаге любой требуемой сложности. Эти операции можно механизировать на автоматической машине.

[НАЧАЛО ЦИТАТЫ] 
1. Computing machines.
We have said that the computable numbers are those whose decimals are calculable by finite means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach §9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited.

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q₁, q₂, ..., qᵣ which will be called «m-configurations». The machine is supplied with a «tape» (the analogue of paper) running through it, and divided into sections (called «squares») each capable of bearing a «symbol». At any moment there is just one square, say the r-th, bearing the symbol 𝔖(r) which is «in the machine». We may call this square the «scanned square». The symbol on the scanned square may be called the «scanned symbol». The «scanned symbol» is the only one of which the machine is, so to speak, «directly aware». 

However, by altering its m-configuration the machine can effectively remember some of the symbols which it has «seen» (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration qₙ and the scanned symbol 𝔖(r). This pair qₙ,𝔖(r) will be called the «configuration» : thus the configuration determines the possible behaviour of the machine. 

In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to «assist the memory». It will only be these rough notes which will be liable to erasure.

It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by «machine», «tape», «scanned», etc. [...]

9. The extent of the computable numbers. [...]
I. [Type (a)]. This argument is only an elaboration of the ideas of § 1.

Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent f. The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral such as 17 or 999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an enumerable infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.

The behaviour of the computer at any moment is determined by the symbols which he is observing, and his «state of mind» at that moment. We may suppose that there is a bound В to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be «arbitrarily close» and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.

Let us imagine the operations performed by the computer to be split up into «simple operations» which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always «observed» squares.

Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square.

In connection with «immediate recognisability», it may be thought that there are other kinds of square which are immediately recognisable. In particular, squares marked by special symbols might be taken as immediately recognisable. Now if these squares are marked only by single symbols there can be only a finite number of them, and we should not upset our theory by adjoining these marked squares to the observed squares. If, on the other hand, they are marked by a sequence of symbols, we cannot regard the process of recognition as a simple process. This is a fundamental point and should be illustrated. In most mathematical papers the equations and theorems are numbered. Normally the numbers do not go beyond (say) 1000. It is, therefore, possible to recognise a theorem at a glance by its number. But if the paper was very long, we might reach Theorem 157767733443477 ; then, further on in the paper, we might find «...hence (applying Theorem 157767733443477) we have ...». In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure, possibly ticking the figures off in pencil to make sure of their not being counted twice. If in spite of this it is still thought that there are other «immediately recognisable» squares, it does not upset my contention so long as these squares can be found by some process of which my type of machine is capable. This idea is developed in III below.

The simple operations must therefore include:
(a) Changes of the symbol on one of the observed squares.
(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.

It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following:
(A) A possible change (a) of symbol together with a possible change of state of mind.
(B) A possible change (b) of observed squares, together with a possible change of state of mind.

The operation actually performed is determined, as has been suggested on p. 136, by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation is carried out.

We may now construct a machine to do the work of this computer. To each state of mind of the computer corresponds an «m-configuration» of the machine. The machine scans В squares corresponding to the В squares observed by the computer. In any move the machine can change a symbol on a scanned square or can change any one of the scanned squares to another square distant not more than L squares from one of the other scanned squares. The move which is done, and the succeeding configuration, are determined by the scanned symbol and the m-configuration. The machines just described do not differ very essentially from computing machines as defined in § 2, and corresponding to any machine of this type a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the computer.
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 117-118, 135-138.]

Таким образом, алгоритм был формализован в виде серии механический действий с символами на бумаге.

ХОД: Комбинирование процессов вычислений.

После этого Алан Тьюринг показывает: возможность универсальных вычислений существует, поскольку таблицу конфигураций машины можно записать (закодировать) в виде последовательности арабских цифр и передать на вход в ленту другой машине. Из указанной последовательности цифр машина может восстановить действия другой машины и выполнить ее.

Последовательность таких цифр Тьюринг называет описательным номером («description number»). Далее в нашей работе мы будем называть такой номер дескриптором.

[НАЧАЛО ЦИТАТЫ] 
Let us write down all expressions so formed from the table for the machine and separate them by semi-colons. In this way we obtain a complete description of the machine. In this description we shall replace qᵢ by the letter «D» followed by the letter «A» repeated i times, and Sᵢ by «D» followed by «C» repeated j times. This new description of the machine may be called the standard description (S.D). It is made up entirely from the letters «A», «C», «D», «L», «R», «N», and from «;».

If finally we replace «A» by «1», «C» by «2», «D» by «3», «L» by «4», «R» by «5», «N» by «6», and «;» by «7» we shall have a description of the machine in the form of an arabic numeral. The integer represented by this numeral may be called a description number (D.N) of the machine. The D.N determines the S.D and the structure of the machine uniquely. The machine whose D.N is n may be described as M(n).

To each computable sequence there corresponds at least one description number, while to no description number does there correspond more than one computable sequence. The computable sequences and numbers are therefore enumerable.

Let us find a description number for the machine I of § 3. [...]

The standard description is
DADDCRDAA ; DAADDRDAAA;
DAAADDCCRDAAAA ; DAAAADDRDA;

A description number is
31332531173113353111731113322531111731111335317
and so is
3133253117311335311173111332253111173111133531731323253117
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 126-127.]

[НАЧАЛО ЦИТАТЫ] 
6. The universal computing machine.
It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D of some computing machine M then U will compute the same sequence as M.
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 127-128.]

Указанное выше впоследствии приводит к открытию хранимых процедур в программировании, поскольку, по Тьюрингу, машины могут быть скомбинированы из других машин через указанные дескрипторы.

ХОД: Определение ограничений модели вычислений для символов.

Далее, с помощью понятий «машина с циклами» («circular» – машина, которая в какой-то момент не сможет вычислить свой следующий символ, так как зациклится и начнет проходить цепочку конфигураций без вывода символа бесконечно по кругу или наткнется на неразрешимую ситуацию) и «машина без циклов» («circle-free» – машина, которая всегда может вычислить свой следующий символ), Тьюринг утверждает, что нельзя построить машину, которая определит, является ли запись другой машины «машиной с циклами» или «машиной без циклов». Это показывает, что существуют алгоритмически неразрешимые вопросы.

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

[НАЧАЛО ЦИТАТЫ] 
The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes β. This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that «there must be something wrong». The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea «circle-free». It depends not on constructing β, but on constructing β', whose n-th figure is φₙ(n).

Let us suppose that there is such a process; that is to say, that we can invent a machine D which, when supplied with the S.D of any computing machine M it will test this S.D and if M is circular will mark the S.D with the symbol «u» and if it is circle-free will mark it with «s». By combining the machines D and U we could construct a machine MN to compute the sequence β'. The machine D may require a tape. We may suppose that it uses the E-squares beyond all symbols on F-squares, and that when it has reached its verdict all the rough work done by D is erased.

The machine MN has its motion divided into sections. In the first N — l sections, among other things, the integers 1, 2, ..., N – 1 have been written down and tested by the machine D. A certain number, say R(N – 1), of them have been found to be the D.N's of circle-free machines. In the N-th section the machine D tests the number N. If N is satisfactory, i.e., if it is the D.N of a circle-free machine, then R(N) = 1 + R(N — 1) and the first R(N) figures of the sequence of which a D.N is N are calculated. The R(N)-th figure of this sequence is written down as one of the figures of the sequence β' computed by MN. If N is not satisfactory, then R(N) = R(N – 1) and the machine goes on to the (N + 1)-th section of its motion.

From the construction of MN we can see that MN is circle-free. Each section of the motion of MN comes to an end after a finite number of steps. For, by our assumption about D, the decision as to whether N is satisfactory is reached in a finite number of steps; If N is not satisfactory, then the N-th section is finished. If N is satisfactory, this means that the machine MN(N) whose D.N is N is circle-free, and therefore its R(N)-th figure can be calculated in a finite number of steps. When this figure has been calculated and written down as the R(N)-th figure of β', the N-th section is finished. Hence N is circle-free.

Now let К be the D.N of MN. What does MN do in the K-th section of its motion? It must test whether К is satisfactory, giving a verdict «s» or «w». Since К is the D.N of MN and since MN is circle-free, the verdict cannot be «u». On the other hand the verdict cannot be «sÏ. For if it were, then in the K-th section of its motion MN would be bound to compute the first R(K – 1) + 1 = R(K) figures of the sequence computed by the machine with К as its D.N and to write down the R(K)-th as a figure of the sequence computed by MN. The computation of the first R(K) – 1 figures would be carried out all right, but the instructions for calculating the R(K)-th would amount to «calculate the first R(K) figures computed by Η and write down the R(K)-th». This R(K)-th figure would never be found. I.e., MN is circular, contrary both to what we have found in the last paragraph and to the verdict «s». Thus both verdicts are impossible and we conclude that there can be no machine D.
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 132-133.]

С помощью доказательства выше Тьюринг показывает: невозможно определить, напечатает ли какая-либо машина М конкретный символ хотя бы один раз, потому что это равносильно тому, что машина является «машиной без циклов».

[НАЧАЛО ЦИТАТЫ] 
We can show further that there can be no machine & which, when supplied with the S.D of an arbitrary machine it, will determine whether it ever prints a given symbol (0 say). [...] 

By a combination of these processes we have a process for determining whether it prints an infinity of figures, i.e. we have a process for determining whether It is circle-free. There can therefore be no machine E.
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 134.]

Таким образом формально доказывается, что существуют задачи, которые алгоритмически неразрешимы.

С помощью второго доказательства Тьюринг обращает внимание на то, что проблема указания алгоритма для задания алгоритма решения диофантовых уравнений равносильна определению, напечатает ли машина конкретный символ во время своей работы. То есть, проблема неразрешима.

[НАЧАЛО ЦИТАТЫ] 
Lemma 1. If S₁ appears on the tape in some complete configuration of M, then Uₙ(M) is provable. [...]

Lemma 2. If Uₙ(M) is provable, then S₁ appears on the tape in some complete configuration of M. [...]

We are now in a position to show that the Entscheidungsproblem cannot be solved. Let us suppose the contrary. Then there is a general (mechanical) process for determining whether Uₙ(M) is provable. By Lemmas 1 and 2, this implies that there is a process for determining whether M, ever prints 0, and this is impossible, by §8. Hence the Entscheidungsproblem cannot be solved.
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 147-148.]

Из каких областей применены ходы

Создавая абстрактную машину, Алан Тьюринг фактически вычленил из рабочего процесса человека отдельные операции и механизировал их (теоретически). Также, кодирование алгоритма машины в виде серии целых чисел является применением арифметического кодирования. Способы доказательства предположений применяются из математической логики.

Благодаря чему стали возможны используемые ходы

По сути, открытие Тьюринга не зависело от открытия рекурсивных функций или лямбда-исчисления и могло быть сделано без результатов Гёделя и Черча. 

Тем не менее открытие Гёделя, которое формально показало, что в некоторой непротиворечивой системе аксиом всегда будут формулы, не доказуемые в ней, стало эталоном для системы Тьюринга. В своей работе он должен был прийти к тому же результату в терминах вычислимости чисел, функций и формул: в его случае должны были существовать алгоритмы, которые невозможно проверить алгоритмически, что по итогу и было сделано в двух теоремах Тьюринга.

Результаты лямбда-вычисления Черча Тьюринг использовал в качестве проверочного эталона для вычислимости, показывая, что можно создать машину, которая может реализовать эти вычисления.

[НАЧАЛО ЦИТАТЫ] 
To show that every λ-definable sequence γ is computable, we have to show how to construct a machine to compute γ. For use with machines it is convenient to make a trivial modification in the calculus of conversion. This alteration consists in using χ, χ', χ", ... as variables instead of a, b, c, — We now construct a machine X which, when supplied with the formula Mγ writes down the sequence γ. The construction of X is somewhat similar to that of the machine К which proves all provable formulae of the functional calculus.
[КОНЕЦ ЦИТАТЫ. Источник: A. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Reprinted in Martin Davis. THE UNDECIDABLE. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. RAVEN PRESS BOOKS, LTD. 1965. PP. 149.]

Идея Г. Кантора о счетных множествах в противовес множествам мощностью континуум существовала до того, как Гильберт сформулировал десятую проблему, поэтому логики и математики уже могли кодировать элементы счетных множеств (например, алфавит из символов) с помощью чисел и рассматривать закономерности таких множеств через арифметику.

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

Также в пользу утверждения о том, что не существовало значительных препятствий для открытия Алана Тьюринга, может говорить тот факт, что очень похожая машина была открыта независимо Эмилем Постом несколько месяцев позже, и она может рассматриваться как полноценный аналог машины Тьюринга. 

Сильные разработки создаются не в одиночку, а в коллективе. LIVREZON CLUB объединяет более 50-ти коллективов в разных отраслях научного знания. В ежедневном режиме они делятся опытом, собирают новые данные, пишут книги и статьи, тестируют технологии и получают друг от друга полезную обратную связь. 

Хотите присоединиться к коллективу разработчиков? Пишите на info@livrezon.com

ЧТО ТАКОЕ БАЗА ЗНАНИЙ?

Концентрированная книга издательства LIVREZON складывается из сотен и тысяч проанализированных источников литературы и масс-медиа. Авторы скрупулёзно изучают книги, статьи, видео, интервью и делятся полезными материалами, формируя коллективную Базу знаний. 

Пример – это фактурная единица информации: небанальное воспроизводимое преобразование, которое используется в исследовании. Увы, найти его непросто. С 2017 года наш Клуб авторов собрал более 80 тысяч примеров. Часть из них мы ежедневно публикуем здесь. 

Каждый фрагмент Базы знаний относится к одной или нескольким категориям и обладает точной ссылкой на первоисточник. Продолжите читать материалы по теме или найдите книгу, чтобы изучить её самостоятельно.  

📎 База знаний издательства LIVREZON – только полезные материалы.