Тезис Чёрча – Тьюринга

«Диссертация Черча» перенаправляется сюда. Об аксиоме CT в конструктивной математике см. диссертацию Чёрча (конструктивная математика) .

В теории вычислимости тезис Чёрча -Тьюринга (также известный как тезис вычислимости ) тезис Тьюринга -Черча , гипотеза Чёрча-Тьюринга , тезис Чёрча , гипотеза Чёрча и тезис Тьюринга ) — тезис о природе вычислимых функций . Он утверждает, что функция натуральных чисел может быть вычислена эффективным методом тогда и только тогда, когда она вычислима машиной Тьюринга . Диссертация названа в честь американского математика Алонзо Чёрча и британского математика Алана Тьюринга . До точного определения вычислимой функции математики часто использовали неформальный термин «эффективно вычислимые» для описания функций, которые можно вычислить методами бумаги и карандаша. В 1930-е годы было предпринято несколько независимых попыток формализовать понятие вычислимости :

• В 1933 году Курт Гёдель вместе с Жаком Эрбраном формализовал определение класса общерекурсивных функций : наименьшего класса функций (с произвольным числом аргументов), который замкнут при композиции , рекурсии и минимизации и включает нуль , преемника и все прогнозы .
• В 1936 году Алонсо Чёрч создал метод определения функций, названный λ-исчислением . В рамках λ-исчисления он определил кодировку натуральных чисел, названную числами Чёрча . Функция натуральных чисел называется λ-вычислимой, если соответствующая функция чисел Чёрча может быть представлена ​​членом λ-исчисления.
• Также в 1936 году, еще до того, как узнал о работе Чёрча, Алан Тьюринг создал теоретическую модель машин, которые теперь называются машинами Тьюринга, которые могли выполнять вычисления на основе входных данных, манипулируя символами на ленте. При подходящем кодировании натуральных чисел в виде последовательностей символов функция натуральных чисел называется вычислимой по Тьюрингу, если некоторая машина Тьюринга вычисляет соответствующую функцию над закодированными натуральными числами.

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

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

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

Заявление словами Чёрча и Тьюринга

См. также: Эффективный метод.

Дж. Б. Россер ( 1939 ) обращается к понятию «эффективной вычислимости» следующим образом: «Очевидно, что существование CC и RC (доказательства Черча и Россера) предполагает точное определение понятия «эффективный». «Эффективный метод» здесь используется в довольно специальном смысле. смысл метода, каждый шаг которого точно предопределен и который наверняка даст ответ за конечное число шагов». Таким образом, наречие-прилагательное «эффективный» используется в значении «1а: произвести решающий, решающий или желаемый эффект» и «способно произвести результат».

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

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

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

Было заявлено..., что «функция эффективно вычислима, если ее значения могут быть найдены с помощью какого-либо чисто механического процесса». Мы можем понимать это буквально, понимая под этим чисто механический процесс, который может быть осуществлен машиной. Развитие... приводит к... выявлению вычислимости ^† с эффективной расчетностью. [ ^† – это сноска, цитированная выше.]

История

Основная статья: История церкви – диссертация Тьюринга

Одной из важных проблем для логиков 1930-х годов была проблема Entscheidungs, предложенная Давидом Гильбертом и Вильгельмом Аккерманом . в котором задавался вопрос, существует ли механическая процедура отделения математической истины от математической лжи. Этот квест требовал, чтобы понятие «алгоритм» или «эффективная вычислимость» было закреплено, по крайней мере, достаточно хорошо, чтобы квест начался. Но с самого начала попытки Алонсо Чёрча начались с дебатов, которые продолжаются и по сей день. Был понятие «эффективной вычислимости» должно быть (i) «аксиомой или аксиомами» в аксиоматической системе, (ii) просто определением , которое «идентифицирует» два или более суждения, (iii) эмпирической гипотезой , подлежащей проверке путем наблюдения за естественными событиями или (iv) просто предложение ради аргументации (т.е. «тезис»)?

Около 1930–1952 гг.

В ходе изучения проблемы Чёрч и его ученик Стивен Клини ввели понятие λ-определимых функций , и им удалось доказать, что несколько больших классов функций, часто встречающихся в теории чисел, являются λ-определимыми. Дебаты начались, когда Чёрч предложил Гёделю определить «эффективно вычислимые» функции как λ-определимые функции. Гёделя, однако, это не убедило, и он назвал это предложение «совершенно неудовлетворительным». Скорее, в переписке с Чёрчем (ок. 1934–1935) Гёдель предложил аксиоматизировать понятие «эффективной вычислимости»; действительно, в письме Клини в 1935 году Черч сообщил, что:

Его [Гёделя] единственная идея в то время заключалась в том, что можно было бы с точки зрения эффективной вычислимости как неопределенного понятия сформулировать набор аксиом, которые воплощали бы общепринятые свойства этого понятия, и что-то сделать на этой основе. .

Но Гёдель не дал никаких дальнейших указаний. В конце концов, он предложил свою рекурсию, модифицированную предложением Эрбрана, которую Гёдель подробно изложил в своих лекциях 1934 года в Принстоне, штат Нью-Джерси (Клин и Россер расшифровывали записи). Но он не думал, что эти две идеи можно удовлетворительно идентифицировать «кроме эвристического подхода».

Далее необходимо было выявить и доказать эквивалентность двух понятий эффективной вычислимости. Вооружившись λ-исчислением и «общей» рекурсией, Клини с помощью Чёрча и Дж. Баркли Россера представила доказательства (1933, 1935), показывающие, что эти два исчисления эквивалентны. Впоследствии Чёрч модифицировал свои методы, включив в них использование рекурсии Эрбранда-Гёделя, а затем доказал (1936), что проблема Entscheidungsproblem неразрешима: не существует алгоритма, который мог бы определить, ли правильно составленная формула имеет бета-нормальную форму .

Много лет спустя в письме Дэвису (около 1965 г.) Гёдель сказал, что «во время этих лекций [1934 г.] он совсем не был убежден, что его концепция рекурсии включает в себя все возможные рекурсии». К 1963–1964 годам Гёдель отрекся от рекурсии Эрбрана-Гёделя и λ-исчисления в пользу машины Тьюринга как определения «алгоритма», «механической процедуры» или «формальной системы».

Гипотеза, ведущая к естественному закону? : В конце 1936 года Алана Тьюринга статья (также доказывающая неразрешимость проблемы Entscheidungs ) была произнесена устно, но еще не появилась в печати. С другой стороны, статья Эмиля Поста 1936 года появилась и была сертифицирована как независимая от работы Тьюринга. Пост категорически не согласился с «отождествлением» Чёрчем эффективной вычислимости с λ-исчислением и рекурсией, заявив:

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

Скорее, он рассматривал понятие «эффективной вычислимости» просто как «рабочую гипотезу», которая могла бы привести путем индуктивного рассуждения к « естественному закону », а не к «определению или аксиоме». Эта идея подверглась «резкой» критике со стороны Чёрча.

Таким образом, Пост в своей статье 1936 года также не принял во внимание предложение Курта Гёделя Черчу в 1934–1935 годах о том, что этот тезис можно выразить как аксиому или набор аксиом.

Тьюринг добавляет еще одно определение, Россер приравнивает все три : за короткое время появилась статья Тьюринга 1936–1937 годов «О вычислимых числах с применением к проблеме Entscheidungs». появился. В нем он изложил еще одно понятие «эффективной вычислимости», представив свои а-машины (теперь известные как абстрактная вычислительная модель машины Тьюринга ). А в наброске доказательства, добавленном в качестве «Приложения» к его статье 1936–1937 годов, Тьюринг показал, что классы функций, определенные λ-исчислением и машинами Тьюринга, совпадают. Черч быстро осознал, насколько убедительным был анализ Тьюринга. В своем обзоре статьи Тьюринга он ясно дал понять, что концепция Тьюринга делает «отождествление с эффективностью в обычном (не явно определенном) смысле очевидным сразу».

Через несколько лет (1939 г.) Тьюринг, как до него Черч и Клини, предположил, что его формальное определение механического вычислительного агента было правильным. Таким образом, к 1939 году и Чёрч (1934), и Тьюринг (1939) индивидуально предложили, чтобы их «формальные системы» были определениями «эффективной вычислимости»; ни один из них не формулировал свои заявления как тезисы .

Россер (1939) формально выделил три понятия-как-определения:

Все три определения эквивалентны, поэтому не имеет значения, какое из них используется.

Клини предлагает Тезис I : Это оставило Клини открытое выражение «тезиса». В 1943 году Клини предложил свой «Тезис I»:

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

Тезис I. Всякая эффективно вычислимая функция (эффективно разрешимый предикат) является общерекурсивной [курсив Клини]

Поскольку точное математическое определение термина «эффективно вычислимый» (эффективно разрешимый) отсутствует, мы можем принять этот тезис... как его определение...

... тезис имеет характер гипотезы - это подчеркивают Пост и Чёрч. Если рассматривать тезис и его обратное как определение, то гипотеза — это гипотеза о применении математической теории, разработанной на основе определения. Для принятия этой гипотезы, как мы предположили, имеются весьма веские основания.

Тезис Чёрча-Тьюринга : Стивен Клини во «Введении в метаматематику » наконец официально называет «Тезис Чёрча» и «Тезис Тьюринга», используя свою теорию рекурсивной реализуемости. Клини перешел от представления своей работы в терминологии лямбда-определимости Черча-Клин к терминологии рекурсивности Гёделя-Клини (частично рекурсивных функций). В ходе этого перехода Клини модифицировала общерекурсивные функции Гёделя, чтобы обеспечить доказательства неразрешимости проблем интуиционизма Э. Дж. Брауэра. В его аспирантском учебнике по логике излагается «тезис Чёрча» и доказывается нереализуемость основных математических результатов. Затем Клини приступает к представлению «тезиса Тьюринга», в котором показано, что результаты невычислимы, используя свой упрощенный вывод машины Тьюринга, основанный на работе Эмиля Поста. Оба тезиса эквивалентны с помощью «Теоремы XXX».

Тезис I. Всякая эффективно вычислимая функция (эффективно разрешимый предикат) общерекурсивна .

Теорема XXX: Следующие классы частичных функций коэкстенсивны, т. е. имеют одни и те же члены: (а) частично рекурсивные функции, (б) вычислимые функции...

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

Клини, наконец, впервые использует термин «тезис Чёрча-Тьюринга» в разделе, в котором он помогает дать разъяснения концепциям в статье Алана Тьюринга «Проблема слов в полугруппах с сокращением», как того требует критика Уильяма Буна.

Более поздние события

Попытка лучше понять понятие «эффективной вычислимости» привела Робина Ганди (ученика и друга Тьюринга) в 1980 году к анализу машинных вычислений (в отличие от человеческих вычислений, выполняемых машиной Тьюринга). Любопытство Ганди и анализ клеточных автоматов (включая игру жизни Конвея ), параллелизма и кристаллических автоматов привели его к предложению четырех «принципов (или ограничений) ... которым, как утверждается, должна удовлетворять любая машина». Его самый важный четвёртый «принцип причинности» основан на «конечной скорости распространения эффектов и сигналов; современная физика отвергает возможность мгновенного действия на расстоянии». Из этих принципов и некоторых дополнительных ограничений — (1a) нижняя граница линейных размеров любой из частей, (1b) верхняя граница скорости распространения (скорости света), (2) дискретное продвижение машины, и (3) детерминированное поведение - он выдвигает теорему: «То, что может быть вычислено с помощью устройства, удовлетворяющего принципам I–IV, вычислимо».

В конце 1990-х годов Вильфрид Зиг проанализировал понятия Тьюринга и Ганди об «эффективной вычислимости» с намерением «уточнить неформальное понятие, аксиоматически сформулировать его общие черты и исследовать аксиоматическую структуру». В своих работах 1997 и 2002 годов Зиг представляет ряд ограничений на поведение компьютера — «человека-вычислителя, действующего механически». Эти ограничения сводятся к:

• «(B.1) (Ограниченность) Существует фиксированное ограничение на количество символических конфигураций, которые компьютер может немедленно распознать.
• «(B.2) (Ограниченность) Существует фиксированное ограничение на количество внутренних состояний, в которых может находиться компьютер.
• «(L.1) (Локальность) Компьютер может изменять только элементы наблюдаемой символической конфигурации.
• «(L.2) (Локальность) Компьютер может переключить внимание с одной символической конфигурации на другую, но новые наблюдаемые конфигурации должны находиться на ограниченном расстоянии от непосредственно ранее наблюдаемой конфигурации.
• «(D) (Определенность) Сразу распознаваемая (под)конфигурация однозначно определяет следующий шаг вычислений (и идентификатор [мгновенное описание])»; иначе говоря: «Внутреннее состояние компьютера вместе с наблюдаемой конфигурацией однозначно определяет следующий шаг вычислений и следующее внутреннее состояние».

Этот вопрос продолжает активно обсуждаться в академическом сообществе.

Тезис как определение

Этот тезис можно рассматривать как не что иное, как обычное математическое определение. Комментарии Гёделя по этому поводу предполагают эту точку зрения, например, «правильное определение механической вычислимости было вне всякого сомнения установлено Тьюрингом». Аргументы в пользу рассмотрения диссертации как не более чем определения четко высказаны Робертом И. Соаре : где также утверждается, что определение вычислимости Тьюринга не менее вероятно правильное, чем эпсилон-дельта-определение непрерывной функции .

Успех диссертации

Другие формализмы (помимо рекурсии, λ-исчисление и машина Тьюринга ) были предложены для описания эффективной вычислимости/вычислимости. Клини (1952) добавляет к списку функции, « считающиеся в системе S ₁ » Курта Гёделя (1936), и Эмиля Поста (1943, 1946) в « канонических [также называемых нормальными ] системах ». В 1950-х годах Хао Ван и Мартин Дэвис значительно упростили модель одноленточной машины Тьюринга (см. Машина Пост-Тьюринга ). Марвин Мински расширил модель до двух или более лент и значительно упростил ленты до «счетчиков вверх-вниз», которые Мельзак и Ламбек в дальнейшем развили в то, что теперь известно как модель счетной машины . В конце 1960-х и начале 1970-х годов исследователи расширили модель счетчиковой машины до регистровой машины , близкой родственницы современного понятия компьютера . Другие модели включают комбинаторную логику и алгоритмы Маркова . Гуревич добавляет модель указательной машины Колмогорова и Успенского (1953, 1958): «… они просто хотели… убедить себя, что нет способа расширить понятие вычислимой функции».

Все эти вклады включают доказательства того, что модели вычислительно эквивалентны машине Тьюринга; такие модели называются полными по Тьюрингу . Поскольку все эти различные попытки формализовать концепцию «эффективной вычислимости/вычислимости» дали эквивалентные результаты, сейчас принято считать, что тезис Чёрча-Тьюринга верен. Фактически Гёдель (1936) предложил нечто более сильное, чем это; он заметил, что в понятии «рассчитываемого в S ₁ » есть что-то «абсолютное»:

Можно также показать, что функция, которая вычислима («считаема») в одной из систем Si _или даже в системе трансфинитного типа, уже вычислима («считаема») в _S1 . Таким образом, понятие «вычислимое» [«рассчитываемое»] является в определенном смысле «абсолютным», в то время как практически все другие известные метаматематические понятия (например, доказуемые, определимые и т. д.) весьма существенно зависят от системы, для которой они определены. .

Неофициальное использование в доказательствах

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

Дирк ван Дален приводит следующий пример, чтобы проиллюстрировать такое неформальное использование тезиса Чёрча-Тьюринга:

Пример: Каждый бесконечный набор RE содержит бесконечный рекурсивный набор .

Доказательство: Пусть A — бесконечное RE. Перечислим элементы A эффективно: n ₀ , n ₁ , n ₂ , n ₃ ,...

Из этого списка мы извлекаем возрастающий подсписок: положим m ₀ = n ₀ , после конечного числа шагов найдем nk _такой , что _nk > m ₀ , положим m ₁ = _nk . Мы повторяем эту процедуру, чтобы найти m ₂ > m ₁ и т. д. Это дает эффективный список подмножества B={m ₀ , m ₁ , m ₂ ,...} A со свойством m _i < m _{i+ 1} .

Требовать . B разрешима. Ибо, чтобы проверить k в B, мы должны проверить, является ли k = m _i для некоторого i. Поскольку последовательность m _i увеличивается, нам нужно создать не более k+1 элементов списка и сравнить их с k. Если ни один из них не равен k, то k не принадлежит B. Поскольку этот критерий эффективен, B разрешима и, по тезису Чёрча , рекурсивна.

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

Вариации

Успех тезиса Чёрча-Тьюринга побудил предложить различные варианты этого тезиса. Например, физический тезис Чёрча-Тьюринга гласит: «Все физически вычислимые функции вычислимы по Тьюрингу».

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

Вариант тезиса Чёрча-Тьюринга касается возможности эффективного моделирования произвольной, но «разумной» модели вычислений. Это называется технико-экономическим обоснованием . также известный как ( классический ) тезис Чёрча-Тьюринга по теории сложности или расширенный тезис Чёрча-Тьюринга , который не связан с Чёрчем или Тьюрингом, а скорее был реализован постепенно в развитии теории сложности . В нем говорится: « Вероятностная машина Тьюринга может эффективно моделировать любую реалистичную модель вычислений». Слово «эффективно» здесь означает сокращение до полиномиального времени . Эта диссертация первоначально была названа (1997) тезисом Чёрча-Тьюринга по теории вычислительной сложности Итаном Бернштейном и Умешом Вазирани . Таким образом, тезис Чёрча-Тьюринга из теории сложности утверждает, что все «разумные» модели вычислений дают один и тот же класс задач, которые можно вычислить за полиномиальное время. Принимая гипотезу о том, что вероятностное полиномиальное время ( BPP ) равно детерминированному полиномиальному времени ( P ), слово «вероятностный» не является обязательным в теоретико-сложном тезисе Чёрча-Тьюринга. Похожий тезис, названный тезисом инвариантности , был выдвинут Сис Ф. Слот и Питером ван Эмде Боасом. В нем говорится: « 'Разумные' машины могут моделировать друг друга с полиномиально ограниченными издержками во времени и постоянными коэффициентами в пространстве». Диссертация первоначально появилась в статье на STOC '84, которая была первой статьей, в которой было показано, что накладные расходы в полиномиальном времени и накладные расходы в постоянном пространстве могут быть одновременно достигнуты для моделирования машины произвольного доступа на машине Тьюринга.

Если будет показано, что BQP является строгим расширенным набором BPP , это сделает недействительным тезис Чёрча-Тьюринга из теории сложности. Другими словами, появятся эффективные квантовые алгоритмы , выполняющие задачи, для которых нет эффективных вероятностных алгоритмов . Однако это не лишило бы законной силы первоначальный тезис Чёрча-Тьюринга, поскольку квантовый компьютер всегда можно смоделировать с помощью машины Тьюринга, но это лишило бы законной силы классический тезис Чёрча-Тьюринга из теории сложности по соображениям эффективности. Следовательно, тезис Чёрча – Тьюринга из теории квантовой сложности гласит: « Квантовая машина Тьюринга может эффективно моделировать любую реалистичную модель вычислений».

Юджин Эбербах и Питер Вегнер утверждают, что тезис Чёрча-Тьюринга иногда интерпретируется слишком широко:заявив: «Хотя [...] машины Тьюринга выражают поведение алгоритмов, более широкое утверждение о том, что алгоритмы точно фиксируют то, что можно вычислить, неверно». Они утверждают, что формы вычислений, не отраженные в диссертации, актуальны и сегодня.термины, которые они называют вычислением супер-Тьюринга .

Философские последствия

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

1. Вселенная эквивалентна машине Тьюринга; таким образом, вычисление нерекурсивных функций физически невозможно. Это получило название сильного тезиса Чёрча-Тьюринга или принципа Чёрча-Тьюринга-Дойча и является основой цифровой физики .
2. Вселенная не эквивалентна машине Тьюринга (т. е. законы физики не являются вычислимыми по Тьюрингу), но неисчислимые физические события невозможно «использовать» для создания гиперкомпьютера . Например, вселенная, в которой физика использует случайные действительные числа , а не вычислимые . в эту категорию попадет
3. Вселенная — это гиперкомпьютер , и можно создавать физические устройства, использующие это свойство и вычисляющие нерекурсивные функции. Например, остается открытым вопрос, являются ли все квантово -механические события вычислимыми по Тьюрингу, хотя известно, что строгие модели, такие как квантовые машины Тьюринга, эквивалентны детерминированным машинам Тьюринга. (Они не обязательно эквивалентны с точки зрения эффективности; см. выше.) Джон Лукас и Роджер Пенроуз предположили, что человеческий разум может быть результатом неких квантовомеханически усовершенствованных «неалгоритмических» вычислений.

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

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

Невычислимые функции

Можно формально определить функции, которые не являются вычислимыми. Хорошо известным примером такой функции является функция Busy Beaver . Эта функция принимает входные данные n и возвращает наибольшее количество символов, которые машина Тьюринга с n состояниями может напечатать перед остановкой при запуске без входных данных. Нахождение верхней границы функции занятого бобра эквивалентно решению проблемы остановки — проблемы, которая, как известно, неразрешима для машин Тьюринга. Поскольку функция занятого бобра не может быть вычислена с помощью машин Тьюринга, тезис Чёрча-Тьюринга утверждает, что эта функция не может быть эффективно вычислена каким-либо методом.

Некоторые вычислительные модели позволяют вычислять невычислимые функции (Черча-Тьюринга). Они известны как гиперкомпьютеры .Марк Бургин утверждает, что суперрекурсивные алгоритмы, такие как индуктивные машины Тьюринга, опровергают тезис Чёрча-Тьюринга. Его аргумент основан на более широком определении алгоритма, чем обычное, так что невычислимые функции, полученные с помощью некоторых индуктивных машин Тьюринга, называются вычислимыми. Такая интерпретация тезиса Чёрча-Тьюринга отличается от интерпретации, общепринятой в теории вычислимости, обсуждавшейся выше. Аргумент о том, что суперрекурсивные алгоритмы действительно являются алгоритмами в смысле тезиса Чёрча-Тьюринга, не нашел широкого признания в сообществе исследователей вычислимости.

См. также

• Абстрактная машина
• Диссертация Чёрча по конструктивной математике
• Принцип Чёрча-Тьюринга-Дойча , согласно которому каждый физический процесс может быть смоделирован с помощью универсального вычислительного устройства.
• Вычислимая логика
• Теория вычислимости
• Разрешимость
• Гипервычисления
• Модель вычислений
• Oracle (информатика)
• Суперрекурсивный алгоритм
• Полнота по Тьюрингу

Ссылки

• Барвайз, Джон ; Кейслер, Х.Дж .; Кунен, Кеннет , ред. (1980). Симпозиум Клини . Амстердам: Издательство Северной Голландии. ISBN  978-0-444-85345-5 .
• Бен-Амрам, AM (2005). «Тезис Чёрча-Тьюринга и его двойники» . Новости СИГАКТ . 36 (3): 113–116. CiteSeerX   10.1.1.74.7308 . дои : 10.1145/1086649.1086651 . S2CID   13566703 . Архивировано из оригинала (PS) 6 июля 2017 г. Проверено 24 октября 2017 г.
• Бернштейн, Э.; Вазирани, У. (1997). «Квантовая теория сложности». SIAM Journal по вычислительной технике . 26 (5): 1411–1473. CiteSeerX   10.1.1.655.1186 . дои : 10.1137/S0097539796300921 .
• Бласс, Андреас ; Гуревич, Юрий (октябрь 2003 г.). «Алгоритмы: поиск абсолютных определений» (PDF) . Бюллетень Европейской ассоциации теоретической информатики (81). Архивировано (PDF) из оригинала 27 июля 2004 г.
• Бургин, Марк (2005). «Суперрекурсивные алгоритмы». Монографии по информатике . Спрингер. ISBN  978-0-387-95569-8 .
• Черч, Алонсо (1932). «Набор постулатов для основания логики». Анналы математики . 33 (2): 346–366. дои : 10.2307/1968337 . JSTOR   1968337 .
• Черч, Алонсо (апрель 1936а). «Неразрешимая проблема элементарной теории чисел» (PDF) . Американский журнал математики . 58 (2): 345–363. дои : 10.2307/2371045 . JSTOR   2371045 . S2CID   14181275 . Архивировано из оригинала (PDF) 27 февраля 2020 г.
• Черч, Алонсо (июнь 1936b). «Заметка о проблеме Entscheidungs». Журнал символической логики . 1 (1): 40–41. дои : 10.2307/2269326 . JSTOR   2269326 . S2CID   42323521 .
• Черч, Алонсо (март 1937 г.). «Обзор: А. М. Тьюринг, О вычислимых числах с применением к проблеме Entscheidungs». Журнал символической логики . 2 (1): 42–43. дои : 10.2307/2268810 . JSTOR   2268810 .
• Черч, Алонсо (1941). Исчисления лямбда-конверсии . Принстон: Издательство Принстонского университета.
• Купер, С.Б.; Одифредди, П. (2003). «Неисчислимость в природе». В СБ Купер; С.С. Гончаров (ред.). Вычислимость и модели: перспективы Востока и Запада . Издательство Kluwer Academic/Plenum. стр. 137–160.
• Дэвис, Мартин , изд. (1965). Неразрешимые, основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Нью-Йорк: Рэйвен Пресс. Включает оригинальные статьи Гёделя, Чёрча, Тьюринга, Россера, Клини и Поста, упомянутые в этом разделе.
• Доусон, Джон В. младший (1997). Логические дилеммы: жизнь и творчество Курта Гёделя . Уэлсли, Массачусетс, США: AK Peters .
• Эбербах, Э.; Вегнер, П. (октябрь 2003 г.). «За пределами машин Тьюринга» (PDF) . Бюллетень Европейской ассоциации теоретической информатики (81): 279–304. CiteSeerX   10.1.1.61.9759 . Архивировано (PDF) из оригинала 15 марта 2016 г.
• Габбай, DM (2001). Справочник по философской логике . Том. 1 (2-е изд.).
• Ганди, Робин (1980). «Тезис Черча и принципы механизмов». В HJ Barwise; Х. Дж. Кейслер; К. Кунен (ред.). Симпозиум Клини . Издательство Северной Голландии. стр. 123–148.
• Ганди, Робин (1994). Херкен, Рольф (ред.). Универсальная машина Тьюринга: обзор полувека . Нью-Йорк: Вена Спрингер – Верлаг. стр. 51 и далее. ISBN  978-3-211-82637-9 .
• Гёдель, Курт (1965) [1934]. «О неразрешимых предложениях формальных математических систем». В Дэвисе, Мартин (ред.). Неразрешимое . Клини и Россер (конспекторы лекций); Институт перспективных исследований (спонсор лекции). Нью-Йорк: Рэйвен Пресс.
• Гёдель, Курт (1936). «О длине доказательств». Результаты математического коллоквиума (на немецком языке) (7). Выпуск: 23–24. Цитируется Клини (1952) .
• Гуревич, Юрий (июнь 1988 г.). «О машинах Колмогорова и связанных с ними вопросах». Бюллетень Европейской ассоциации теоретической информатики (35): 71–82.
• Гуревич, Юрий (июль 2000 г.). «Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы» (PDF) . Транзакции ACM в вычислительной логике . 1 (1): 77–111. CiteSeerX   10.1.1.146.3017 . дои : 10.1145/343369.343384 . S2CID   2031696 . Архивировано (PDF) из оригинала 16 октября 2003 г.
• Эрбран, Жак (1932). «Сюр-ла-непротиворечие арифметики». Журнал чистой и прикладной математики (на французском языке). 166 : 1–8. дои : 10.1515/crll.1932.166.1 . S2CID   116636410 .
• Хофштадтер, Дуглас Р. «Глава XVII: Черч, Тьюринг, Тарский и другие». Гёдель, Эшер, Бах: вечная золотая коса (изд. К двадцатилетнему юбилею). Основные книги . стр. 559–585. ISBN  0-465-02656-7 .
• Клини, Стивен Коул (январь 1935 г.). «Теория положительных целых чисел в формальной логике». Американский журнал математики . 57 (1): 153–173 и 219–244. дои : 10.2307/2372027 . JSTOR   2372027 .
• Клини, Стивен Коул (1936). «Лямбда-определимость и рекурсивность». Математический журнал Дьюка . 2 (2): 340–353. дои : 10.1215/s0012-7094-36-00227-2 .
• Клини, Стивен Коул (1943). «Рекурсивные предикаты и квантификаторы» . Труды Американского математического общества . 53 (1): 41–73. дои : 10.2307/1990131 . JSTOR   1990131 . Перепечатано в «Неразрешимом» , с. 255 и далее. Клини уточнил свое определение «общей рекурсии» и в главе «12. Алгоритмические теории» перешел к постулированию «Тезиса I» (стр. 274); позже он повторил этот тезис ( Kleene 1952 :300) и назвал его «Тезисом Чёрча» ( Kleene 1952 :317) (т.е. тезисом Чёрча ).
• Клини, Стивен Коул (1952). Введение в метаматематику . Северная Голландия. OCLC   523942 .
• Кнут, Дональд (1973). Искусство компьютерного программирования . Том. 1/Фундаментальные алгоритмы (2-е изд.). Аддисон-Уэсли.
• Кугель, Питер (ноябрь 2005 г.). «Пришло время мыслить за пределами вычислительных рамок». Коммуникации АКМ . 48 (11): 32–37. CiteSeerX   10.1.1.137.6939 . дои : 10.1145/1096000.1096001 . S2CID   29843806 .
• Льюис, HR ; Пападимитриу, CH (1998). Элементы теории вычислений . Река Аппер-Сэддл, Нью-Джерси, США: Прентис-Холл.
• Манна, Зоар (2003) [1974]. Математическая теория вычислений . Дувр. ISBN  978-0-486-43238-0 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Марков А.А. (1960) [1954]. «Теория алгоритмов». Переводы Американского математического общества . 2 (15): 1–14.
• Ольшевский, Адам; Воленский, Ян; Януш, Роберт, ред. (2006). Тезис Чёрча спустя 70 лет . Франкфурт: Онтос. ISBN  978-3-938793-09-1 . OCLC   909679288 .
• Пур-Эль, МБ ; Ричардс, Дж.И. (1989). Вычислимость в анализе и физике . Спрингер Верлаг .
• Россер, Дж. Б. (1939). «Неформальное изложение доказательств теоремы Гёделя и теоремы Чёрча». Журнал символической логики . 4 (2): 53–60. дои : 10.2307/2269059 . JSTOR   2269059 . S2CID   39499392 .
• Зиг, Уилфрид; Соммер, Ричард; Талкотт, Кэролайн, ред. (2002). Размышления об основаниях математики: Очерки в честь Соломона Фефермана . Конспект лекций по логике. Том. 15. АК Петерс, ООО ISBN  978-1-56881-169-7 .
• Сиропулос, Апостолос (2008). Гиперкомпьютерные вычисления: вычисления за пределами барьера Церкви – Тьюринга . Спрингер. ISBN  978-0-387-30886-9 .
• Тьюринг, AM (1937a) [Доставлено Обществу в ноябре 1936 г.], «О вычислимых числах с применением к проблеме Entscheidungs» (PDF) , Труды Лондонского математического общества , 2, том. 42, стр. 230–265, doi : 10.1112/plms/s2-42.1.230 , S2CID   73712 и Тьюринг, AM (1938). «О вычислимых числах с применением к проблеме Entscheidungs: исправление». Труды Лондонского математического общества . 2. Том. 43 (опубликовано в 1937 г.). стр. 544–546. дои : 10.1112/plms/s2-43.6.544 . (См. также: Дэвис 1965 : 115 и далее.)
• Тьюринг, Алан Мэтисон (декабрь 1937b). «Вычислимость и λ-определимость» (PDF) . Журнал символической логики . 2 (4): 153–163. дои : 10.2307/2268280 . JSTOR   2268280 . S2CID   2317046 . Архивировано из оригинала (PDF) 9 августа 2020 г.

Внешние ссылки

• «Тезис Чёрча-Тьюринга» Статья Б. Джека Коупленда в Стэнфордской энциклопедии философии .
• «Вычисления в физических системах» Запись Гуалтьеро Пиччинини в Стэнфордской энциклопедии философии — комплексное философское рассмотрение соответствующих вопросов.
• Казначеев, Артем (11 сентября 2014 г.). «Трансцендентальный идеализм и вариант Поста тезиса Чёрча-Тьюринга» . Журнал символической логики . 1 (3): 103–105.
• ( Специальный выпуск том 28, № 4, 1987 г.) журнала Notre Dame Journal of Formal Logic был посвящен тезису Чёрча – Тьюринга.