stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

История

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

Около 1930–1952 гг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дальнейшие события

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

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

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

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

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

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

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

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

Можно также показать, что функция, которая вычислима ['исчислима'] в одной из систем S i , или даже в системе трансфинитного типа, уже вычислима [исчислима] в S 1 . Таким образом, понятие 'вычислимое' ['исчислимое'] является в определенном смысле 'абсолютным', в то время как практически все другие знакомые метаматематические понятия (например, доказуемое, определимое и т. д.) зависят весьма существенно от системы, в которой они определены... [51]

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

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

Дирк ван Дален приводит следующий пример для иллюстрации этого неформального использования тезиса Чёрча-Тьюринга: [53]

Пример: Каждое бесконечное рекурсивно перечислимое (RE) множество содержит бесконечное рекурсивное множество .

Доказательство: Пусть A — бесконечное RE. Перечислим элементы A эффективно, n 0 , n 1 , n 2 , n 3 , ...

Из этого списка извлекаем возрастающий подсписок: положим m 0  = n 0 , после конечного числа шагов найдем n k такой, что n k > m 0 , положим m 1  = n k . Повторяем эту процедуру, чтобы найти m 2 > m 1 и т. д. это дает эффективный список подмножества B={m 0 , m 1 , m 2 ,...} A со свойством m i < m i+1 .

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

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

Вариации

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

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

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

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

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

Философские импликации

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

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

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

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

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

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

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

Смотрите также

Сноски

  1. ^ Роберт Соаре , «Тьюринговые Oracle-машины, онлайн-вычисления и три смещения в теории вычислимости»
  2. ^ Рабин, Майкл О. (июнь 2012 г.). Тьюринг, Чёрч, Гёдель, Вычислимость, сложность и рандомизация: личный взгляд. Событие происходит в 9:36 . Получено 2021-12-05 .
  3. ↑ Переписка между Максом Ньюманом и Чёрчем в бумагах Алонзо Чёрча
  4. ^ Тьюринг, Алан (2004). Суть Тьюринга: основополагающие труды по вычислительной технике, логике, философии, искусственному интеллекту и искусственной жизни, а также секреты Энигмы (PDF) . Оксфорд: Clarendon Press. стр. 44. ISBN 9780198250791. Получено 2021-12-06 .
  5. ^ ab Soare, Robert I. (сентябрь 1996 г.). «Вычислимость и рекурсия». Bulletin of Symbolic Logic . 2 (3): 284–321. CiteSeerX 10.1.1.35.5803 . doi :10.2307/420992. JSTOR  420992. S2CID  5894394. 
  6. ↑ Статья Чёрча была представлена ​​Американскому математическому обществу 19 апреля 1935 года и опубликована 15 апреля 1936 года. Тьюринг, который добился существенного прогресса в изложении своих собственных результатов, был разочарован, узнав о доказательстве Чёрча после его публикации. [3] [4] Тьюринг быстро закончил свою статью и поспешил с публикацией; она была получена Трудами Лондонского математического общества 28 мая 1936 года, прочитана 12 ноября 1936 года и опубликована в серии 2, том 42 (1936–1937); она появилась в двух разделах: в Части 3 (страницы 230–240), выпущенной 30 ноября 1936 года, и в Части 4 (страницы 241–265), выпущенной 23 декабря 1936 года; Тьюринг добавил исправления в томе 43 (1937), стр. 544–546. [5] : 45 
  7. ^ Церковь 1936a
  8. ^ Клини 1936
  9. ^ Тьюринг 1937a
  10. ^ Клини 1936
  11. ↑ Тьюринг 1937б. План доказательства на стр. 153: [10]
  12. ↑ Россер 1939 в Дэвис 1965:225.
  13. ^ "эффективный". Новый университетский словарь Merriam Webster (9-е изд.).
  14. ^ См. также "эффективный". Онлайн-словарь Merriam-Webster (11-е изд.) . Получено 26.07.2014 ,где также даны определения термину «эффективный» – первое [«производящий решительный, решающий или желаемый эффект»] как определение для значения «1a» слова «эффективный», а второе [«способный производить результат»] как часть «Обсуждения синонимов слова ЭФФЕКТИВНЫЙ» там же (во вступительной части, где суммируются сходства между значениями слов «эффективный», «действенный», «эффективный» и «действенный»).
  15. ^ ab Turing, AM (1938). Системы логики, основанные на ординалах (PDF) (PhD). Принстонский университет. стр. 8. Архивировано из оригинала (PDF) 2012-10-23 . Получено 2012-06-23 .
  16. ^ Ганди (1980:123) формулирует это так: То, что эффективно вычислимо, вычислимо. Он называет это «тезисом Чёрча».
  17. ^ Дэвид Гильберт и Вильгельм Аккерман: Grundzüge der theoretischen Logik, Берлин, Германия, Springer, 1-е изд. 1928. (6-е изд. 1972, ISBN 3-540-05843-5 ) Английский перевод: Дэвид Гильберт и Вильгельм Аккерман: Принципы математической логики, издательство AMS Chelsea Publishing, Провиденс, Род-Айленд, США, 1950. 
  18. ↑ Комментарий Дэвиса перед Чёрчем 1936 г. Неразрешимая проблема элементарной теории чисел в Дэвисе 1965:88. Чёрч использует слова «эффективная вычислимость» на стр. 100 и далее.
  19. ^ В своем обзоре Church's Thesis after 70 Years под редакцией Adam Olszewski et al. 2006 Питер Смит в своей критике статьи Мурасвски и Воленски предлагает 4 "линии" относительно статуса Church-Turing Thesis: (1) эмпирическая гипотеза (2) аксиома или теорема, (3) определение, (4) экспликация. Но Смит полагает, что (4) неотличимо от (3), см. Smith (2007-07-11) Church's Thesis after 70 Years на http://www.logicmatters.net/resources/pdfs/CTT.pdf
  20. ^ см. сноску 3 в Church 1936a An Unsolvable Problem of Elementary Number Theory в Davis 1965:89.
  21. ↑ Доусон 1997:99.
  22. ^ ab Sieg 1997:160.
  23. ↑ Sieg 1997:160 цитирует письмо 1935 года, написанное Чёрчем Клини, см. сноску 3 в Gödel 1934 в Davis 1965:44.
  24. ^ см. Church 1936 в Davis 1965:105ff..
  25. ↑ Комментарий Дэвиса к работе Гёделя 1934 г. в Davis 1965:40.
  26. ^ Подробное обсуждение принятия Гёделем машин Тьюринга в качестве моделей вычислений см. в Shagrir, Oron (2006-06-15). "Gödel on Turing on Computability" (PDF) . Church's Thesis After 70 Years . De Gruyter. pp. 393–419. doi :10.1515/9783110325461.393. ISBN 978-3-11-032494-5. Архивировано из оригинала (PDF) 2015-12-17 . Получено 2016-02-08 .
  27. ^ ab Тьюринг 1937a.
  28. ^ см. Сноску редактора к статье Post 1936 Finite Combinatory Process. Formulation I. в Davis 1965:289.
  29. ↑ Пост 1936 в Davis 1965:291, сноска 8.
  30. ↑ Пост 1936 в Davis 1952:291.
  31. ^ Зиг 1997: 171 и 176–177.
  32. ↑ Тьюринг 1936–1937 в Дэвисе 1965:263ff..
  33. ↑ Церковь 1937.
  34. ↑ Тьюринг 1939 в Дэвисе:160.
  35. ^ см. Church 1934 в Davis 1965:100, а также Turing 1939 в Davis 1965:160.
  36. ^ курсив добавлен, Россер 1939 в Дэвис 1965:226.
  37. ↑ Kleene 1943, стр. 60 в Davis 1965:274. Сноски опущены.
  38. ↑ Клини 1952:300.
  39. ^ ab Kleene 1952:376.
  40. ^ Клини 1952:382, 536
  41. ↑ Ганди 1980:123ff.
  42. ^ Ганди 1980:135
  43. ^ Ганди 1980:126
  44. ^ Зиг 1998–1999 в Sieg, Sommer & Talcott 2002: 390ff.; также Зиг 1997: 154 и далее.
  45. ^ В сноске Зиг разбивает Post's 1936 (B) на (B.1) и (B.2) и (L) на (L.1) и (L.2) и описывает (D) по-другому. В отношении его предложенной машины Ганди он позже добавляет LC.1, LC.2, GA.1 и GA.2. Они сложны; см. Sieg 1998–1999 в Sieg, Sommer & Talcott 2002:390ff..
  46. ^ Сборник статей можно найти в Olszewski, Woleński & Janusz (2006). Также обзор этого сборника: Smith, Peter (2007-07-11). "Тезис Церкви спустя 70 лет" (PDF) .
  47. ^ См. также Hodges, Andrew (2005). «Имел ли Чёрч и Тьюринг тезис о машинах?» (PDF) . Архивировано из оригинала (PDF) 2016-03-04 . Получено 2014-07-27 .
  48. ^ Гёдель, Курт (1995) [193?]. "Неразрешимые диофантовы предложения". В Feferman, Solomon (ред.). Собрание сочинений. Т. 3. Нью-Йорк: Oxford University Press . стр. 168. ISBN 978-0-19-507255-6. OCLC  928791907.
  49. ^ Клини 1952:320
  50. ^ Гуревич 1988:2
  51. ↑ Перевод Гёделя (1936) Дэвиса в «Неразрешимом» стр. 83, отличающийся использованием слова «исчислимый» в переводе у Клини (1952) стр. 321
  52. ^ Хорстен в Ольшевском, Воленском и Януше 2006: 256.
  53. ^ Габбай 2001:284
  54. ^ Piccinini, Gualtiero (январь 2007 г.). «Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy» (PDF) . Synthese . 154 (1): 97–120. CiteSeerX 10.1.1.360.9796 . doi :10.1007/s11229-005-0194-z. S2CID  494161. Архивировано (PDF) из оригинала 24.04.2008. 
  55. ^ Арора, Санджив; Барак, Боаз (2009). Теория сложности: современный подход. Cambridge University Press . ISBN 978-0-521-42426-4.Разделы 1.4 «Машины как струны и универсальная машина Тьюринга» и 1.7 «Доказательство теоремы 1.9».
  56. ^ "Официальное описание проблемы" (PDF) . Архивировано из оригинала (PDF) 2005-11-24.
  57. ^ ab Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2007). Введение в квантовые вычисления . Oxford University Press. С. 5–6. ISBN 978-0-19-857049-3.
  58. ^ Ван Эмде Боас, Питер (1990). «Модели машин и симуляции». Справочник по теоретической информатике A. Elsevier . стр. 5.
  59. ^ Слот, К.; ван Эмде Боас, П. (декабрь 1984 г.). На ленте против ядра: применение эффективных по пространству совершенных хеш-функций к инвариантности пространства . STOC .
  60. ^ Эбербах и Вегнер 2003, с. 287.
  61. ^ Абрамсон, Даррен (2011). «Философия разума — это (отчасти) философия компьютерной науки». Minds and Machines . 21 (2): 203–219. doi :10.1007/s11023-011-9236-0. S2CID  32116031.
  62. ^ Коупленд, Б. Джек (10.11.2017). «Тезис Чёрча-Тьюринга». В Zalta, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
  63. ^ Для хорошего места, чтобы познакомиться с оригинальными статьями, см. Chalmers, David J. , ed. (2002). Philosophy of Mind: Classical and Contemporary Readings . New York: Oxford University Press. ISBN 978-0-19-514581-6. OCLC  610918145.
  64. ^ Коупленд, Б. Джек (2004). "Вычисление". В Floridi, Лучано (ред.). Руководство Блэквелла по философии вычислений и информации . Wiley-Blackwell. стр. 15. ISBN 978-0-631-22919-3.
  65. ^ см. Пенроуз, Роджер (1990). «Алгоритмы и машины Тьюринга». Новый разум императора: о компьютерах, разуме и законах физики . Оксфорд: Oxford University Press. стр. 47–49. ISBN 978-0-19-851973-7. OCLC  456785846.
  66. ^ Также описание «неалгоритмической природы математического понимания», Пенроуз, Роджер (1990). «Где лежит физика разума?». Новый разум императора: о компьютерах, разуме и законах физики . Оксфорд: Oxford University Press. С. 416–418. ISBN 978-0-19-851973-7. OCLC  456785846.
  67. ^ Пьерджорджио Одифредди (1989). Классическая теория рекурсии . Исследования по логике и основаниям математики. Т. 125. Амстердам, Нидерланды: Северная Голландия.
  68. ^ Burgin, Mark (2005). Суперрекурсивные алгоритмы . Монографии по информатике. Нью-Йорк: Springer. ISBN 978-0-387-95569-8. OCLC  990755791.

Ссылки

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