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

Диссертация о природе вычислимости

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

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

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

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

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

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

Дж. Б. Россер  (1939) обращается к понятию «эффективной вычислимости» следующим образом: «Очевидно, что существование CC и RC (доказательства Черча и Россера) предполагает точное определение понятия «эффективный». «Эффективный метод» здесь используется в довольно специальном смысле. смысл метода, каждый шаг которого точно предопределен и который наверняка даст ответ за конечное число шагов». ^[12] Таким образом, наречие-прилагательное «эффективный» используется в смысле «1а: производить решающий, решающий или желаемый эффект» и «способен произвести результат». ^{[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 года статья Алана Тьюринга (также доказывающая неразрешимость проблемы Entscheidungs ) была произнесена устно, но еще не появилась в печати. ^[27] С другой стороны, статья Эмиля Поста 1936 года появилась и была сертифицирована как независимая от работы Тьюринга. ^[28] Пост категорически не согласился с «отождествлением» Чёрча эффективной вычислимости с λ-исчислением и рекурсией, заявив:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: Каждый бесконечный набор 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, теоретик вычислимости принимает это как доказательство того, что множество действительно рекурсивно.

Вариации

Успех тезиса Чёрча-Тьюринга побудил предложить различные варианты этого тезиса. Например, физический тезис Чёрча-Тьюринга гласит: «Все физически вычислимые функции вычислимы по Тьюрингу». ^{[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 состояниями может напечатать перед остановкой при запуске без входных данных. Нахождение верхней границы функции занятого бобра эквивалентно решению проблемы остановки — проблемы, которая, как известно, неразрешима для машин Тьюринга. Поскольку функция занятого бобра не может быть вычислена с помощью машин Тьюринга, тезис Чёрча-Тьюринга утверждает, что эта функция не может быть эффективно вычислена каким-либо методом.

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

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

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

Сноски

1. Роберт Соаре , «Машины Oracle Тьюринга, онлайн-вычисления и три смещения в теории вычислимости»
2. Рабин, Майкл О. (июнь 2012 г.). Тьюринг, Чёрч, Гёдель, Вычислимость, сложность и рандомизация: личный взгляд. Событие происходит в 9:36 . Проверено 5 декабря 2021 г.
3. Переписка между Максом Ньюманом и Черчем в документах Алонзо Черча
4. Тьюринг, Алан (2004). Основные работы Тьюринга: плодотворные работы по вычислительной технике, логике, философии, искусственному интеллекту и искусственной жизни, а также секреты Энигмы (PDF) . Оксфорд: Кларендон Пресс. п. 44. ИСБН 9780198250791. Проверено 6 декабря 2021 г.
5. Соаре, Роберт И. (сентябрь 1996 г.). «Вычислимость и рекурсия». Бюллетень символической логики . 2 (3): 284–321. CiteSeerX 10.1.1.35.5803 . дои : 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. Церковь 1936а
8. Клини 1936 г.
9. Тьюринг 1937а
10. Клини 1936 г.
11. Тьюринг 1937б. Схема доказательства на стр. 153: ^[10] ${\displaystyle \lambda {\mbox{-definable}}}$ ${\displaystyle {\stackrel {triv}{\implies }}}$ ${\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}$ ${\displaystyle {\stackrel {160}{\implies }}}$ ${\displaystyle {\mbox{Turing computable}}}$ ${\displaystyle {\stackrel {161}{\implies }}}$ ${\displaystyle \mu {\mbox{-recursive}}}$ ${\displaystyle {\stackrel {Kleene}{\implies }}}$ ${\displaystyle \lambda {\mbox{-definable}}}$
12. Россер 1939 в Дэвисе 1965: 225.
13. «эффективный». Новый университетский словарь Мерриама Вебстера (9-е изд.).
14. См. также «эффективный». Интернет-словарь Мерриам-Вебстера (11-е изд.) . Проверено 26 июля 2014 г. ,который также дает эти определения слова «эффективный» - первое [«производящее решительный, решающий или желаемый эффект»] как определение смысла «1а» слова «эффективный», а второе [«способное производить результат». «] как часть «Обсуждения синонимов ЭФФЕКТИВНЫЙ» (во вводной части, где обобщаются сходства между значениями слов «эффективный», «эффективный», «эффективный» и «эффективный»).
15. Тьюринг, AM (1938). Системы логики на основе ординалов (PDF) (доктор философии). Университет Принстон. п. 8. Архивировано из оригинала (PDF) 23 октября 2012 г. Проверено 23 июня 2012 г.
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. В своем обзоре « Диссертации Чёрча через 70 лет» под редакцией Адама Ольшевского и др. В 2006 году критика Питером Смитом статьи Мурасвски и Воленски предлагает 4 «линии» относительно статуса тезиса Чёрча-Тьюринга: (1) эмпирическая гипотеза (2) аксиома или теорема, (3) определение, (4) объяснение. Но Смит полагает, что (4) неотличимо от (3), ср. Смит (11 июля 2007 г.) Диссертация Чёрча через 70 лет на http://www.logicmatters.net/resources/pdfs/CTT.pdf
20. см. сноска 3 в книге Черча, 1936а. Неразрешимая проблема элементарной теории чисел в Дэвисе, 1965:89.
21. Доусон 1997:99.
22. Зиг 1997: 160.
23. Sieg 1997:160, цитата из письма Черча Клини 1935 года, ср. Сноска 3 в Gödel 1934 и Davis 1965:44.
24. см. Церковь 1936 года в Дэвисе 1965: 105 и далее..
25. Комментарий Дэвиса перед Гёделем 1934 г. в Davis 1965:40.
26. Подробное обсуждение использования Гёделем машин Тьюринга в качестве моделей вычислений см. в «Шагрире». «Гедель о Тьюринге о вычислимости» (PDF) . Архивировано из оригинала (PDF) 17 декабря 2015 г. Проверено 8 февраля 2016 г.^{[ дата отсутствует ]}
27. Тьюринг 1937а.
28. см. Сноска редактора к «Конечному комбинаторному процессу после 1936 года». Формулировка I. at Davis 1965:289.
29. Сообщение 1936 года в Дэвисе 1965: 291, сноска 8.
30. Сообщение 1936 года в Дэвисе 1952: 291.
31. Зиг 1997: 171 и 176–177.
32. Тьюринг 1936–1937 в Дэвисе 1965: 263 и далее..
33. Церковь 1937.
34. Тьюринг 1939 в Дэвисе: 160.
35. см. Черч 1934 г. в Дэвисе 1965:100, а также Тьюринг 1939 г. в Дэвисе 1965:160.
36. курсив добавлен, Россер 1939 в Дэвисе 1965: 226.
37. Клини 1943, с. 60 в Дэвисе, 1965: 274. Сноски опущены.
38. Клини 1952:300.
39. Клини 1952:376.
40. Клини 1952: 382, ​​536.
41. Ганди 1980: 123 и далее.
42. Ганди 1980:135
43. Ганди 1980:126
44. Зиг 1998–1999 в Sieg, Sommer & Talcott 2002: 390ff.; также Зиг 1997:154ff.
45. В сноске Зиг разбивает Поста 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). Также обзор этого сборника: Смит, Питер (11 июля 2007 г.). «Диссертация Церкви через 70 лет» (PDF) .
47. См. также Ходжес, Эндрю (2005). «Были ли у Черча и Тьюринга диссертация о машинах?» (PDF) . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 27 июля 2014 г.
48. Гёдель, Курт (1995) [193?]. «Неразрешимые диофантовы предложения». В Фефермане, Соломоне (ред.). Собрание сочинений. Том. 3. Нью-Йорк: Издательство Оксфордского университета . п. 168. ИСБН 978-0-19-507255-6. ОСЛК  928791907.
49. Клини 1952:320
50. Гуревич 1988:2
51. Перевод Гёделя (1936) Дэвиса в «Неразрешимом», с. 83, отличаясь использованием слова «расчетный» в переводе у Клини (1952), с. 321
52. Хорстен в Ольшевском, Воленском и Януше 2006: 256.
53. Габбай 2001: 284
54. Пиччинини, Гуальтьеро (январь 2007 г.). «Вычислительность, тезис Чёрча-Тьюринга и ошибка Чёрча-Тьюринга» (PDF) . Синтезируйте . 154 (1): 97–120. CiteSeerX 10.1.1.360.9796 . doi : 10.1007/s11229-005-0194-z. S2CID  494161. Архивировано (PDF) из оригинала 24 апреля 2008 г. 
55. Арора, Санджив; Барак, Вооз (2009). Теория сложности: современный подход. Издательство Кембриджского университета . ISBN 978-0-521-42426-4.Разделы 1.4 «Машины как струны и универсальная машина Тьюринга» и 1.7 «Доказательство теоремы 1.9».
56. «Официальное описание проблемы» (PDF) . Архивировано из оригинала (PDF) 24 ноября 2005 г.
57. Кэй, Филипп; Лафламм, Раймонд; Моска, Мишель (2007). Введение в квантовые вычисления . Издательство Оксфордского университета. стр. 5–6. ISBN 978-0-19-857049-3.
58. ван Эмде Боас, Питер (1990). «Модели машин и моделирование». Справочник по теоретической информатике А. Эльзевир . п. 5.
59. Слот, К.; ван Эмде Боас, П. (декабрь 1984 г.). На ленте или на ядре: применение идеальных хэш-функций, эффективно использующих пространство, для обеспечения инвариантности пространства . СТОК .
60. Эбербах и Вегнер 2003, с. 287.
61. Абрамсон, Даррен (2011). «Философия разума — это (частично) философия информатики». Разум и машины . 21 (2): 203–219. дои : 10.1007/s11023-011-9236-0. S2CID  32116031.
62. Коупленд, Б. Джек (10 ноября 2017 г.). «Тезис Чёрча-Тьюринга». В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
63. Хорошее место для ознакомления с оригинальными статьями: Chalmers, David J. , ed. (2002). Философия разума: классические и современные чтения . Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-514581-6. ОСЛК  610918145.
64. Коупленд, Б. Джек (2004). «Расчет». Во Флориди, Лучано (ред.). Руководство Блэквелла по философии вычислений и информации . Уайли-Блэквелл. п. 15. ISBN 978-0-631-22919-3.
65. см. Пенроуз, Роджер (1990). «Алгоритмы и машины Тьюринга». Новый разум императора: о компьютерах, разуме и законах физики . Оксфорд: Издательство Оксфордского университета. стр. 47–49. ISBN 978-0-19-851973-7. ОКЛК  456785846.
66. Также описание «неалгоритмической природы математического понимания», Пенроуз, Роджер (1990). «Где находится физика разума?». Новый разум императора: о компьютерах, разуме и законах физики . Оксфорд: Издательство Оксфордского университета. стр. 416–418. ISBN 978-0-19-851973-7. ОКЛК  456785846.
67. Пьерджорджио Одифредди (1989). Классическая теория рекурсии . Исследования по логике и основам математики. Том. 125. Амстердам, Нидерланды: Северная Голландия.
68. Бургин, Марк (2005). Суперрекурсивные алгоритмы . Монографии по информатике. Нью-Йорк: Спрингер. ISBN 978-0-387-95569-8. ОКЛК  990755791.

Рекомендации

• Барвайз, Джон ; Кейслер, Х.Дж .; Кунен, Кеннет , ред. (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). «Über die Lāange von Beweisen» [О длине доказательств]. Ergenbnisse Eines Mathematishen Kolloquiums (на немецком языке). Вес (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). «Сюр-ла-непротиворечие арифметики». Journal für die Reine und Angewandte Mathematik (на французском языке). 166 : 1–8. дои : 10.1515/crll.1932.166.1. S2CID  116636410.
• Хофштадтер, Дуглас Р. «Глава XVII: Черч, Тьюринг, Тарский и другие». Гёдель, Эшер, Бах: вечная золотая коса .^{[ необходимы страницы ]}
• Клини, Стивен Коул (январь 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); позже он повторит этот тезис (Клин 1952:300) и назовет его «Тезис Чёрча» (Клин 1952:317) (т.е. тезис Чёрча ).
• Клини, Стивен Коул (1952). Введение в метаматематику . Северная Голландия. ОСЛК  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: location missing publisher (link)
• Марков А.А. (1960) [1954]. «Теория алгоритмов». Переводы Американского математического общества . 2 (15): 1–14.
• Ольшевский, Адам; Воленский, Ян; Януш, Роберт, ред. (2006). Тезис Чёрча спустя 70 лет . Франкфурт: Онтос. ISBN 978-3-938793-09-1. ОКЛК  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 был посвящен тезису Чёрча – Тьюринга.