Тезис Черча – Тьюринга - Википедия - Church–Turing thesis
В теория вычислимости, то Тезис Черча – Тьюринга (также известный как тезис о вычислимости,[1] то Тезис Тьюринга – Черча,[2] то Гипотеза Черча – Тьюринга, Тезис Чёрча, Гипотеза Черча, и Тезис Тьюринга) это гипотеза о природе вычислимые функции. В нем говорится, что функция на натуральные числа можно рассчитать эффективный метод тогда и только тогда, когда он вычислим Машина Тьюринга. Диссертация названа в честь американского математика. Церковь Алонсо и британский математик Алан Тьюринг. До точного определения вычислимой функции математики часто использовали неформальный термин эффективно вычисляемый для описания функций, вычислимых методами бумаги и карандаша. В 1930-х годах было предпринято несколько независимых попыток оформить понятие вычислимость:
- В 1933 г. Курт Гёдель, с Жак Эрбранд, создал формальное определение класса с именем общие рекурсивные функции. Класс общерекурсивных функций - это наименьший класс функций (возможно, с более чем одним аргументом), который включает все постоянные функции, прогнозы, функция преемника, и который закрыт функциональная композиция, рекурсия, и минимизация.
- В 1936 г. Церковь Алонсо создал метод определения функций, названный λ-исчисление. В рамках λ-исчисления он определил кодировку натуральных чисел, названную Церковные цифры. Функция на натуральных числах называется λ-вычислимый если соответствующая функция на числах Чёрча может быть представлена членом λ-исчисления.
- Также в 1936 году, до того как узнал о работе Церкви,[нужна цитата ] Алан Тьюринг создал теоретическую модель машин, которые теперь называются машинами Тьюринга, которые могут выполнять вычисления на основе входных данных, манипулируя символами на ленте. При подходящем кодировании натуральных чисел как последовательностей символов функция натуральных чисел называется Вычислимый по Тьюрингу если какая-то машина Тьюринга вычисляет соответствующую функцию на закодированных натуральных числах.
Церковь[3] и Тьюринг[4][6] доказал, что эти три формально определенных класса вычислимых функций совпадают: функция является λ-вычислимой тогда и только тогда, когда она вычислима по Тьюрингу, и тогда и только тогда, когда она вычислима по Тьюрингу. общерекурсивный. Это заставило математиков и компьютерных специалистов поверить, что концепция вычислимости точно описывается этими тремя эквивалентными процессами. Другие формальные попытки охарактеризовать вычислимость впоследствии укрепили это убеждение (см. ниже ).
С другой стороны, тезис Черча – Тьюринга утверждает, что указанные выше три формально определенных класса вычислимых функций совпадают с неофициальный понятие эффективно вычислимой функции. Поскольку как неформальное понятие концепция эффективной вычислимости не имеет формального определения, этот тезис, хотя и имеет почти всеобщее признание, не может быть формально доказан.
С момента его создания возникли вариации исходного тезиса, в том числе утверждения о том, что физически может реализовать компьютер в нашей Вселенной (физический тезис Черча-Тьюринга ) и что можно эффективно вычислить (Тезис Черча – Тьюринга (теория сложности) ). Эти вариации возникают не из-за Черча или Тьюринга, а в результате более поздних работ в теория сложности и цифровая физика. Этот тезис также имеет значение для философия разума (видеть ниже ).
Утверждение словами Черча и Тьюринга
Дж. Б. Россер (1939 ) обращается к понятию «эффективная вычислимость» следующим образом: «Очевидно, что существование CC и RC (доказательства Черча и Россера) предполагает точное определение« эффективного ».« Эффективный метод »здесь используется в довольно специальном смысле метода каждый шаг которого точно предопределен и который, несомненно, даст ответ за конечное число шагов ".[7] Таким образом, прилагательное-наречие «эффективный» используется в значении «1a: производит решительный, решающий или желаемый эффект» и «способный произвести результат».[8][9]
Далее слова «эффективно вычислимый» будут означать «произведенный любыми интуитивно« эффективными »средствами каким бы то ни было», а «эффективно вычислимый» будет означать «произведенный машиной Тьюринга или эквивалентным механическим устройством». «Определения» Тьюринга, данные в сноске в его докторской диссертации 1938 г. Тезис Системы логики на основе порядковых чисел, контролируемые церковью, практически одинаковы:
† Мы будем использовать выражение «вычислимая функция» для обозначения функции, вычисляемой машиной, и пусть «эффективно вычислимая» будет относиться к интуитивной идее без особой идентификации с каким-либо из этих определений.[10]
Тезис можно сформулировать так: Каждая эффективно вычислимая функция является вычислимой функцией.[11]Черч также заявил, что «никакая вычислительная процедура не будет рассматриваться как алгоритм, если она не может быть представлена как машина Тьюринга».[нужна цитата ]Тьюринг заявил об этом так:
Было заявлено ... что «функция эффективно вычислима, если ее значения могут быть найдены с помощью какого-либо чисто механического процесса». Мы можем понимать это буквально, понимая, что это чисто механический процесс, который может быть осуществлен машиной. Развитие ... приводит к ... идентификации вычислимости† с эффективной вычислимостью. [† цитируемая выше сноска.][10]
История
Одной из важных проблем логиков 30-х гг. Entscheidungsproblem из Дэвид Гильберт и Вильгельм Аккерманн,[12] который спрашивал, существует ли механическая процедура для отделения математических истин от математической лжи. Этот квест требовал, чтобы понятие «алгоритм» или «эффективная вычислимость» было определено, по крайней мере, достаточно хорошо, чтобы квест начался.[13] Но с самого начала Церковь Алонсо Попытки начались с дебатов, которые продолжаются по сей день.[14] Был[уточнить ] понятие «эффективная вычислимость» должно быть (i) «аксиомой или аксиомами» в аксиоматической системе, (ii) просто определение которые «идентифицировали» два или более предложений, (iii) эмпирическая гипотеза быть подтвержденным наблюдением за природными явлениями, или (iv) просто предложение ради аргументации (т.е. "тезиса").
Примерно 1930–1952 гг.
В ходе изучения проблемы Черч и его ученик Стивен Клини ввел понятие λ-определимые функции, и они смогли доказать, что несколько больших классов функций, часто встречающихся в теории чисел, были λ-определимы.[15] Споры начались, когда Чёрч предложил Гёделю определить «эффективно вычислимые» функции как λ-определяемые функции. Гёдель, однако, не был убежден и назвал это предложение «совершенно неудовлетворительным».[16] Скорее, в переписке с Черчем (ок. 1934–1935) Гёдель предложил аксиоматизация понятие «эффективная исчисляемость»; действительно, в письме 1935 года Клини Черч сообщил, что:
Единственная идея его [Гёделя] в то время заключалась в том, что с точки зрения эффективной вычислимости как неопределенного понятия можно было бы сформулировать набор аксиом, которые воплощали бы общепринятые свойства этого понятия, и что-то сделать на этой основе. .[17]
Но Гёдель не дал никаких дальнейших указаний. В конце концов, он предложил свою рекурсию, модифицированную предложением Гербранда, которую Гёдель подробно изложил в своих лекциях 1934 года в Принстоне, штат Нью-Джерси (Kleene and Россер расшифровал заметки). Но он не думал, что эти две идеи можно удовлетворительно идентифицировать «кроме как эвристически».[18]
Затем необходимо было выявить и доказать эквивалентность двух понятий эффективной вычислимости. Оснащен λ-исчислением и "общей" рекурсией, Стивен Клини с помощью церкви и Дж. Баркли Россер произвел доказательства (1933, 1935), чтобы показать, что эти два исчисления эквивалентны. Впоследствии Черч модифицировал свои методы, включив в них использование рекурсии Хербрана – Гёделя, а затем доказал (1936 г.), что Entscheidungsproblem неразрешима: не существует алгоритма, который мог бы определить, хорошо сформированная формула имеет «нормальную форму».[уточнить ][19]
Много лет спустя в письме к Дэвису (ок. 1965 г.) Гёдель сказал, что «во время этих [1934] лекций он вовсе не был убежден, что его концепция рекурсии включает в себя все возможные рекурсии».[20] К 1963–64 годам Гёдель отверг рекурсию Гербрана – Гёделя и λ-исчисление в пользу машины Тьюринга как определения «алгоритма», «механической процедуры» или «формальной системы».[21]
Гипотеза, ведущая к естественному закону?: В конце 1936 г. Алан Тьюринг документ (также доказывающий, что Entscheidungsproblem неразрешима) был доставлен устно, но еще не опубликован.[22] С другой стороны, Эмиль Пост вышла статья 1936 года, которая была сертифицирована независимо от работ Тьюринга.[23] Пост категорически не согласен с "отождествлением" Черча эффективной вычислимости с λ-исчислением и рекурсией, заявив:
На самом деле работа, уже проделанная Чёрчем и другими, выводит эту идентификацию за пределы стадии рабочей гипотезы. Но если скрыть эту идентификацию под определением… мы не видим необходимости ее постоянной проверки.[24]
Скорее, он рассматривал понятие «эффективной вычислимости» как просто «рабочую гипотезу», которая могла бы привести к индуктивное мышление к "естественный закон "а не" определением или аксиомой ".[25] Эта идея была подвергнута «резкой» критике со стороны Церкви.[26]
Таким образом, Пост в своей статье 1936 г. Курт Гёдель предложение Черчу в 1934–1935 годах о том, что этот тезис может быть выражен как аксиома или набор аксиом.[17]
Тьюринг добавляет еще одно определение, Россер приравнивает все три: За короткое время вышла статья Тьюринга 1936–37 годов «О вычислимых числах в приложении к проблеме Entscheidungsproblem».[22] появившийся. В нем он сформулировал другое понятие «эффективной вычислимости» с введением его a-машин (теперь известных как Машина Тьюринга абстрактная вычислительная модель). А в эскизе доказательства, добавленном в качестве «Приложения» к его статье 1936–37 годов, Тьюринг показал, что классы функций, определенные λ-исчислением и машинами Тьюринга, совпадают.[27] Черч быстро осознал, насколько убедительным был анализ Тьюринга. В своем обзоре статьи Тьюринга он ясно дал понять, что понятие Тьюринга делает «отождествление с эффективностью в обычном (явно не определенном) смысле очевидным сразу».[28]
Через несколько лет (1939 г.) Тьюринг предложит, как Черч и Клини до него, что его формальное определение механического вычислительного агента было правильным.[29] Таким образом, к 1939 году и Черч (1934), и Тьюринг (1939) индивидуально предложили, чтобы их «формальные системы» были определения «эффективной вычислимости»;[30] ни один из них не сформулировал свои заявления как тезисы.
Россер (1939) формально выделил три понятия как определения:
Все три определения эквивалентны, поэтому не имеет значения, какой из них используется.[31]
Клини предлагает Тезис Черча: Это оставило Клини явное выражение «тезиса». В своей статье 1943 г. Рекурсивные предикаты и квантификаторы Клини предложил свой "ТЕЗИС I":
Этот эвристический факт [общие рекурсивные функции эффективно вычислимы] ... побудил Черча сформулировать следующий тезис (22). Тот же тезис подразумевается в описании вычислительных машин Тьюринга (23).
ТЕЗИС I. Каждая эффективно вычислимая функция (эффективно разрешимый предикат) является общей[32] рекурсивный [Курсив Клини]
Поскольку точного математического определения термина эффективно вычислимый (эффективно разрешимый) не хватало, мы можем принять этот тезис ... как его определение ...[33]
(22() ссылки Церковь 1936 г .;[недостаточно конкретный, чтобы проверить ] (23) отсылает к Тьюрингу 1936-7. Клини отмечает, что:
этот тезис носит характер гипотезы - на это подчеркивали Пост и Черч (24). Если мы рассматриваем тезис и его обратное как определение, то гипотеза - это гипотеза о применении математической теории, разработанной на основе определения. Для принятия гипотезы, как мы и предполагали, есть довольно веские основания.[33]
(24) ссылки на публикацию Post 1936 г. Формальные определения в теории порядковых чисел, Фонд. Математика. vol 28 (1936) pp.11–21 (см. исх. № 2, Дэвис 1965:286).
Тезис Чёрча-Тьюринга Клини: Несколько лет спустя (1952) Клини, который переключился с представления своей работы по математической терминологии лямбда-исчисления своего научного руководителя Алонзо Чёрча на теорию общих рекурсивных функций своего другого учителя Курта Гёделя, открыто назвал Церковь - Тезис Тьюринга в его исправлении статьи Тьюринга "Проблема слова в полугруппах с сокращением",[34] защитить и выразить два «тезиса», а затем «идентифицировать» их (показать эквивалентность) с помощью его теоремы XXX:
Эвристические данные и другие соображения побудили Черча в 1936 г. выдвинуть следующий тезис.
Тезис I. Каждая эффективно вычислимая функция (эффективно разрешимый предикат) общерекурсивна.[35]
Теорема XXX: следующие классы частичных функций коэкстенсивны, т.е. имеют одни и те же члены: (а) частично рекурсивные функции, (б) вычислимые функции ...[36]
Тезис Тьюринга: тезис Тьюринга о том, что каждая функция, которая естественным образом считалась бы вычислимой, вычислима по его определению, то есть на одной из его машин, эквивалентен тезису Черча по теореме XXX.[36]
Более поздние разработки
Попытка лучше понять понятие «эффективной вычислимости» привела Робин Ганди (Ученик и друг Тьюринга) в 1980 г. для анализа машина вычисления (в отличие от человеческих вычислений, выполняемых машиной Тьюринга). Любопытство Ганди и его анализ клеточные автоматы (включая Игра жизни Конвея ), параллелизм и кристаллические автоматы, привели его к предложению четырех «принципов (или ограничений) ... которым, как утверждается, должна удовлетворять любая машина».[37] Его наиболее важный четвертый «принцип причинности» основан на «конечной скорости распространения эффектов и сигналов; современная физика отвергает возможность мгновенного действия на расстоянии».[38] Из этих принципов и некоторых дополнительных ограничений - (1a) нижняя граница линейных размеров любой из частей, (1b) верхняя граница скорости распространения (скорость света), (2) дискретный ход машины, и (3) детерминированное поведение - он приводит теорему о том, что «то, что может быть вычислено устройством, удовлетворяющим принципам I – IV, вычислимо».[39]
В конце 1990-х Вилфрид Зиг проанализировал концепции Тьюринга и Ганди об «эффективной вычислимости» с целью «уточнить неформальное понятие, аксиоматически сформулировать его общие черты и исследовать аксиоматическую основу».[40] В своих работах 1997 и 2002 годов Зиг представляет ряд ограничений на поведение вычислитель- «человек-вычислительный агент, который действует механически». Эти ограничения сводятся к:
- «(B.1) (Ограниченность) Существует фиксированная граница количества символьных конфигураций, которые компьютер может сразу распознать.
- «(B.2) (Ограниченность) Существует фиксированная граница количества внутренних состояний, в которых может находиться компьютер.
- «(L.1) (Местоположение) Компьютер может изменять только элементы наблюдаемой символьной конфигурации.
- «(L.2) (Локальность) Компьютер может переключать внимание с одной символической конфигурации на другую, но новые наблюдаемые конфигурации должны находиться на ограниченном расстоянии от непосредственно наблюдаемой конфигурации.
- «(D) (Детерминированность) Сразу распознаваемая (под) конфигурация однозначно определяет следующий шаг вычисления (и id [мгновенное описание])»; сформулировал иначе: «Внутреннее состояние компьютера вместе с наблюдаемой конфигурацией однозначно фиксирует следующий шаг вычисления и следующее внутреннее состояние».[41]
Этот вопрос продолжает активно обсуждаться в академическом сообществе.[42][43]
Тезис как определение
Этот тезис можно рассматривать как простое математическое определение. Комментарии Гёделя по этому поводу предполагают эту точку зрения, например «Правильное определение механической вычислимости было вне всяких сомнений установлено Тьюрингом».[44] Аргументы в пользу того, чтобы рассматривать тезис как не более чем определение, явно сформулированы Роберт И. Соаре,[45] где также утверждается, что определение вычислимости Тьюринга не менее вероятно, чем определение эпсилон-дельта непрерывная функция.
Успех диссертации
Другие формализмы (помимо рекурсии, λ-исчисление, а Машина Тьюринга ) были предложены для описания эффективной вычислимости / вычислимости. Стивен Клини (1952) добавляет к списку функции "почтенный в системе S1" из Курт Гёдель 1936 г. и Эмиль Пост (1943, 1946) "канонический [также называемый нормальный] системы".[46] В 1950-е годы Хао Ван и Мартин Дэвис значительно упростила однополосную модель машины Тьюринга (см. Машина Пост-Тьюринга ). Марвин Мински расширили модель до двух или более лент и значительно упростили ленты до «счетчиков вверх-вниз», которые Мелзак и Ламбек далее развился в то, что теперь известно как счетчик машина модель. В конце 1960-х - начале 1970-х исследователи расширили модель счетчика до зарегистрировать машину, близкий родственник современной концепции компьютер. Другие модели включают комбинаторная логика и Марковские алгоритмы. Гуревич добавляет указатель машины Модель Колмогорова и Успенского (1953, 1958): «... они просто хотели ... убедить себя, что нет никакого способа расширить понятие вычислимой функции».[47]
Все эти вклады включают доказательства того, что модели вычислительно эквивалентны машине Тьюринга; такие модели называются Тьюринг завершен. Поскольку все эти различные попытки формализовать концепцию «эффективной вычислимости / вычислимости» дали эквивалентные результаты, в настоящее время принято считать, что тезис Черча – Тьюринга верен. Фактически, Гёдель (1936) предложил нечто более сильное, чем это; он заметил, что есть что-то «абсолютное» в концепции «счетного» в S1":
Также может быть показано, что функция, которая вычислима [«счтена»] в одной из систем Sя, или даже в системе трансфинитного типа, уже вычислима [вычислима] в S1. Таким образом, понятие «вычислимый» [«рассчитываемый»] в определенном смысле «абсолютен», в то время как практически все другие известные метаматематические концепции (например, доказуемые, определяемые и т. Д.) Весьма существенно зависят от системы, для которой они определены. .[48]
Неформальное использование в доказательствах
Доказательства в теории вычислимости часто используют тезис Черча – Тьюринга неформальным образом, чтобы установить вычислимость функций, избегая при этом (часто очень длинных) деталей, которые были бы задействованы в строгом формальном доказательстве.[49] Чтобы установить, что функция вычислима с помощью машины Тьюринга, обычно считается достаточным дать неформальное описание на английском языке того, как функция может быть эффективно вычислена, а затем заключить «с помощью тезиса Чёрча-Тьюринга», что функция вычислима по Тьюрингу (что эквивалентно , частично рекурсивный).
Дирк ван Дален приводит следующий пример, чтобы проиллюстрировать это неформальное использование тезиса Черча-Тьюринга:[50]
ПРИМЕР: Каждый бесконечный RE набор содержит бесконечное рекурсивный набор.
Доказательство. Пусть A бесконечное RE. Перечислим элементы A эффективно, n0, п1, п2, п3, ...
Из этого списка извлекаем увеличивающийся подсписок: положим m0= п0, после конечного числа шагов находим nk такой что nk > м0положим m1= пk. Повторяем эту процедуру, чтобы найти m2 > м1и т. д. это дает эффективный листинг подмножества B = {m0, м1, м2, ...} из A со свойством mя <мя + 1.
Требовать. B разрешима. Ведь для того, чтобы проверить k в B, мы должны проверить, k = mя для некоторых я. Поскольку последовательность mя's увеличивается, мы должны создать не более k + 1 элементов списка и сравнить их с k. Если ни один из них не равен k, то k не входит в B. Поскольку этот тест эффективен, B разрешима и, по диссертации Черча, рекурсивный.
Чтобы сделать приведенный выше пример полностью строгим, нужно было бы тщательно сконструировать машину Тьюринга или λ-функцию, или осторожно использовать аксиомы рекурсии, или, в лучшем случае, умно использовать различные теоремы теории вычислимости. Но поскольку теоретик вычислимости полагает, что вычислимость по Тьюрингу правильно фиксирует то, что может быть эффективно вычислено, и поскольку эффективная процедура для определения множества B изложена на английском языке, теоретик вычислимости принимает это как доказательство того, что множество действительно рекурсивно.
Вариации
Успех тезиса Чёрча-Тьюринга побудил к предложению различных вариантов тезиса. Например, физический тезис Черча – Тьюринга утверждает: «Все физически вычислимые функции вычислимы по Тьюрингу».[51]:101
В тезисе Черча – Тьюринга ничего не говорится об эффективности, с которой одна модель вычислений может моделировать другую. Например, было доказано, что (многолента) универсальная машина Тьюринга только страдает логарифмическим фактором замедления при моделировании любой машины Тьюринга.[52]
Вариант тезиса Черча – Тьюринга касается того, можно ли эффективно смоделировать произвольную, но «разумную» модель вычислений. Это называется тезис о осуществимости,[53] также известный как (классический) Теоретико-сложный тезис Чёрча – Тьюринга или расширенная диссертация Черча – Тьюринга, что не связано с Черчем или Тьюрингом, а, скорее, было реализовано постепенно в процессе развития теория сложности. Говорится:[54] "А вероятностная машина Тьюринга может эффективно моделировать любую реалистичную модель вычислений ». Слово« эффективно »здесь означает до редукции за полиномиальное время. Первоначально этот тезис назывался Теоретико-вычислительная теория сложности Чёрча – Тьюринга Итаном Бернстайном и Умеш Вазирани (1997). Теоретико-сложный тезис Черча – Тьюринга, таким образом, утверждает, что все «разумные» модели вычислений порождают один и тот же класс задач, которые могут быть вычислены за полиномиальное время. Если предположить, что вероятностное полиномиальное время (BPP ) равно детерминированному полиномиальному времени (п ), слово «вероятностный» является необязательным в теоретико-сложном тезисе Черча – Тьюринга. Похожий тезис, названный тезис об инвариантности, был представлен Сиз Ф. Слот и Питер ван Эмде Боас. Говорится: "«Разумные» машины могут моделировать друг друга в пределах полиномиально ограниченных накладных расходов во времени и накладных расходов постоянного фактора в пространстве ».[55] Первоначально диссертация была опубликована в STOC '84, который был первой статьей, показывающей, что накладные расходы за полиномиальное время и накладные расходы в постоянном пространстве могут быть одновременно достигнуто для моделирования Машина произвольного доступа на машине Тьюринга.[56]
Если BQP показано как строгий надмножество BPP, это сделало бы недействительным теоретико-сложный тезис Черча – Тьюринга. Другими словами, были бы эффективные квантовые алгоритмы которые выполняют задачи, не имеющие эффективного вероятностные алгоритмы. Это, однако, не аннулирует исходный тезис Черча – Тьюринга, поскольку квантовый компьютер всегда можно смоделировать с помощью машины Тьюринга, но по соображениям эффективности это сделает недействительным классический теоретико-сложный тезис Черча – Тьюринга. Следовательно, квантовая теория сложности Чёрча – Тьюринга состояния:[54] "А квантовая машина Тьюринга может эффективно моделировать любую реалистичную модель вычислений ».
Юджин Эбербах и Питер Вегнер утверждают, что тезис Черча-Тьюринга иногда интерпретируется слишком широко, заявляя, что «более широкое утверждение, что алгоритмы точно фиксируют то, что можно вычислить, неверно».[57][страница нужна ] Они утверждают, что формы вычислений, не охваченные тезисом, актуальны сегодня, и эти термины вычисление супер-Тьюринга.
Философские последствия
Философы интерпретировали тезис Черча-Тьюринга как имеющий значение для философия разума.[58][59][60] Б. Джек Коупленд заявляет, что это открытый эмпирический вопрос, существуют ли реальные детерминированные физические процессы, которые в конечном итоге ускользают от моделирования машиной Тьюринга; более того, он заявляет, что это открытый эмпирический вопрос, участвуют ли какие-либо такие процессы в работе человеческого мозга.[61] Есть также несколько важных открытых вопросов, которые охватывают взаимосвязь между тезисом Черча – Тьюринга и физикой, а также возможность гипервычисления. Применительно к физике диссертация имеет несколько возможных значений:
- Вселенная эквивалентна машине Тьюринга; таким образом, вычисляя нерекурсивные функции физически невозможно. Это получило название сильного тезиса Черча-Тьюринга, или Принцип Черча – Тьюринга – Дойча, и является основой цифровая физика.
- Вселенная не эквивалентна машине Тьюринга (т. Е. Законы физики не вычислимы по Тьюрингу), но неисчислимые физические события не могут быть «использованы» для построения гиперкомпьютер. Например, вселенная, в которой физика включает случайные действительные числа, в отличие от вычислимые вещественные числа, попадет в эту категорию.
- Вселенная - это гиперкомпьютер, и можно создавать физические устройства, использующие это свойство и вычисляющие нерекурсивные функции. Например, открытый вопрос, все ли квантово-механический события вычислимы по Тьюрингу, хотя известно, что строгие модели, такие как квантовые машины Тьюринга эквивалентны детерминированным машинам Тьюринга. (Они не обязательно эквивалентны по эффективности; см. Выше.) Джон Лукас и Роджер Пенроуз предположили, что человеческий разум может быть результатом некоего квантово-механически усовершенствованного «неалгоритмического» вычисления.[62][63]
Есть много других технических возможностей, которые выходят за пределы этих трех категорий или находятся между ними, но они служат для иллюстрации диапазона концепции.
Философские аспекты диссертации, касающиеся как физических, так и биологических компьютеров, также обсуждаются в учебнике Одифредди по теории рекурсии 1989 года.[64]:101–123
Невычислимые функции
Можно формально определить функции, которые не вычислимы. Хорошо известным примером такой функции является Занятый Бобер функция. Эта функция принимает ввод п и возвращает наибольшее количество символов, которое Машина Тьюринга с п состояния могут печататься перед остановкой при запуске без ввода. Нахождение верхней границы функции занятого бобра эквивалентно решению проблема остановки, проблема, заведомо неразрешимая для машин Тьюринга. Поскольку функция занятого бобра не может быть вычислена машинами Тьюринга, тезис Черча – Тьюринга утверждает, что эта функция не может быть эффективно вычислена каким-либо методом.
Некоторые вычислительные модели позволяют вычислять невычислимые функции (Черча-Тьюринга). Они известны какгиперкомпьютеры.Марк Бургин утверждает, что суперрекурсивные алгоритмы такие как индуктивные машины Тьюринга опровергают тезис Черча-Тьюринга.[65][страница нужна ] Его аргумент основан на более широком, чем обычный, определении алгоритма, так что невычислимые функции, полученные из некоторых индуктивных машин Тьюринга, называются вычислимыми. Эта интерпретация тезиса Черча – Тьюринга отличается от интерпретации, обычно принятой в теории вычислимости, обсужденной выше. Аргумент, что суперрекурсивные алгоритмы действительно являются алгоритмами в смысле тезиса Чёрча – Тьюринга, не нашел широкого признания в сообществе исследователей вычислимости.[нужна цитата ]
Смотрите также
- Абстрактная машина
- Тезис Черча по конструктивной математике
- Принцип Черча – Тьюринга – Дойча, в котором говорится, что каждый физический процесс можно моделировать универсальным вычислительным устройством
- Логика вычислимости
- Теория вычислимости
- Разрешимость
- Гипервычисления
- Модель вычисления
- Oracle (информатика)
- Суперрекурсивный алгоритм
- Полнота по Тьюрингу
Сноски
- ^ Роберт Соаре, «Машины Тьюринга Oracle, онлайн-вычисления и три смещения в теории вычислимости»
- ^ Рабин, Майкл О. (Июнь 2012 г.). Тьюринг, Чёрч, Гёдель, вычислимость, сложность и рандомизация: личное мнение. Архивировано из оригинал на 2019-06-05. Получено 2012-07-14.
- ^ Церковь 1936 г.
- ^ Тьюринг 1937a
- ^ Клини 1936
- ^ Тьюринг 1937b . Схема доказательства на стр.153: [5]
- ^ Россер 1939 в Дэвис 1965:225.
- ^ «эффективный». Новый университетский словарь Мерриам Вебстер (9-е изд.).
- ^ Смотрите также «эффективный». Онлайн-словарь Мерриам-Вебстера (11-е изд.). Получено 26 июля, 2014, который также дает эти определения слова «эффективный» - первый [«производящий решающий, решающий или желаемый эффект»] как определение смысла «1а» слова «эффективный», а второй [«способный произвести результат "] как часть" Обсуждения синонимов ЭФФЕКТИВНОСТИ "(во вводной части, где суммируются сходства между значениями слов" эффективный "," действенный "," действенный "и" действенный ").
- ^ а б Тьюринг, А. (1938). Системы логики на основе порядковых чисел (PDF) (Кандидат наук). Университет Принстона. п. 8. Архивировано из оригинал (PDF) на 2012-10-23. Получено 2012-06-23.
- ^ Ганди (1980: 123) утверждает это так: То, что эффективно вычислимо, можно вычислить. Он называет это «тезисом Чёрча».
- ^ Давид Гильберт и Вильгельм Аккерманн: Grundzüge der Theoretischen Logik, Берлин, Германия, Springer, 1-е изд. 1928. (6-е изд. 1972 г., стр. ISBN 3-540-05843-5) Английский перевод: Дэвид Гильберт и Вильгельм Акерманн: принципы математической логики, AMS Chelsea Publishing, Провиденс, Род-Айленд, США, 1950
- ^ Комментарий Дэвиса перед Черч 1936 г. Неразрешимая проблема элементарной теории чисел в Дэвисе 1965: 88. Черч использует слова «эффективная вычислимость» на странице 100 и далее.
- ^ В своем обзоре Тезис Чёрча через 70 лет под редакцией Адама Ольшевского и др. В 2006 году Питер Смит критика статьи Мурасвски и Воленски предлагает 4 «линии» относительно статуса тезиса Черча – Тьюринга: (1) эмпирическая гипотеза (2) аксиома или теорема, (3) определение, (4) объяснение. Но Смит считает, что (4) неотличимо от (3), см. Смит (11 июля 2007 г.). Тезис Чёрча через 70 лет в http://www.logicmatters.net/resources/pdfs/CTT.pdf
- ^ cf сноска 3 в Церковь 1936a Неразрешимая проблема элементарной теории чисел в Дэвис 1965:89.
- ^ Доусон 1997:99.
- ^ а б Зиг 1997: 160.
- ^ Sieg 1997: 160 цитата из письма Черча Клини 1935 года, см. Сноску 3 в Gödel 1934 in Дэвис 1965:44.
- ^ ср. Церковь 1936 г. в Дэвис 1965: 105ff.
- ^ Комментарий Дэвиса перед Гёделем 1934 г. в Дэвис 1965:40.
- ^ Подробное обсуждение того, как Гёдель принял машины Тьюринга в качестве моделей вычислений, см. Шагрир. "Гедель о Тьюринге о вычислимости" (PDF). Архивировано из оригинал (PDF) на 2015-12-17. Получено 2016-02-08.[дата отсутствует ]
- ^ а б Тьюринг 1937.
- ^ ср. Сноска редактора к публикации 1936 г. Конечный комбинаторный процесс. Состав I. в Дэвис 1965:289.
- ^ Пост 1936 г. в Дэвис 1965: 291, сноска 8.
- ^ Пост 1936 года в Дэвисе 1952: 291.
- ^ Sieg 1997: 171 и 176–177.
- ^ Тьюринг 1936–37 в Дэвис 1965: 263ff.
- ^ Церковь 1937 г..
- ^ Тьюринг 1939 в Дэвисе: 160.
- ^ ср. Церковь 1934 г. в Дэвис 1965: 100, также Тьюринг 1939 г. в Дэвис 1965:160.
- ^ курсив добавлен, Россер 1939 в Дэвис 1965:226.
- ^ Архаичное использование Kleene et al. отличить «рекурсив» Гёделя (1931) (несколько лет спустя названный примитивная рекурсия к Рожа Петер (ср Ганди 1994: 68)) из рекурсии Хербрана – Гёделя 1934 г., т.е. примитивной рекурсии, снабженной дополнительным оператор mu; в настоящее время мю-рекурсия называется просто "рекурсия ".
- ^ а б Клини 1943 в Дэвис 1965:274.
- ^ Клини 1952:382,536.
- ^ Клини 1952:300.
- ^ а б Клини 1952:376.
- ^ Ганди 1980: 123ff.
- ^ Ганди 1980:135.
- ^ Ганди 1980:126
- ^ Зиг 1998–9 в Зиг, Сомнер и Талкотт, 2002 г.: 390ff ; также Sieg 1997: 154ff.
- ^ В сноске Зиг разбивает 1936 г. Поста (B) на (B.1) и (B.2) и (L) на (L.1) и (L.2) и описывает (D) по-разному. Что касается предложенного им Машина Ганди позже он добавляет LC.1, LC.2, GA.1 и GA.2. Это сложно; см. Sieg 1998–99 in Зиг, Сомнер и Талкотт, 2002 г.: 390ff .
- ^ Сборник статей можно найти в Ольшевский, Воленский и Януш (2006). Также обзор этой коллекции: Смит, Питер (11 июля 2007 г.). «Тезис Чёрча через 70 лет» (PDF).
- ^ Смотрите также Ходжес, Эндрю (2005). "У Черча и Тьюринга был тезис о машинах?" (PDF). Архивировано из оригинал (PDF) 4 марта 2016 г.. Получено 27 июля, 2014.
- ^ Гёдель, Курт (1995) [193?]. «Неразрешимые диофантовы предложения». В Феферман, Соломон (ред.). Собрание сочинений. 3. Нью-Йорк: Издательство Оксфордского университета. п.168. ISBN 978-0-19-507255-6. OCLC 928791907 - через Google Книги.
- ^ Соаре, Роберт И. (Сентябрь 1996 г.). «Вычислимость и рекурсия». Бюллетень символической логики. 2 (3): 284–321. CiteSeerX 10.1.1.35.5803. Дои:10.2307/420992. JSTOR 420992.
- ^ Клини 1952: 320
- ^ Гуревич 1988: 2
- ^ перевод Гёделя (1936) Дэвиса в Неразрешимый п. 83, отличаясь использованием слова «вменяемый» в переводе в Kleene (1952) p. 321
- ^ Хорстен в Ольшевский 2006:256 .
- ^ Габбай 2001:284
- ^ Пиччинини, Гуальтьеро (Январь 2007 г.). «Вычислительный подход, тезис Черча – Тьюринга и заблуждение Черча – Тьюринга» (PDF). Синтез. 154 (1): 97–120. CiteSeerX 10.1.1.360.9796. Дои:10.1007 / s11229-005-0194-z.
- ^ Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход. Издательство Кембриджского университета. ISBN 978-0-521-42426-4. Разделы 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы 1.9».
- ^ «Официальное описание проблемы» (PDF). Архивировано из оригинал (PDF) 24 ноября 2005 г.
- ^ а б Кэй, Филипп; Лафламм, Раймонд; Моска, Микеле (2007). Введение в квантовые вычисления. Издательство Оксфордского университета. С. 5–6. ISBN 978-0-19-857049-3.
- ^ ван Эмде Боас, Питер (1990). «Модели машин и симуляторы». Справочник по теоретической информатике A. Эльзевир. п. 5.
- ^ Слот, C .; ван Эмде Боас, П. (декабрь 1984 г.). На ленте против ядра: применение эффективных хэш-функций, эффективно использующих пространство, для неизменности пространства. STOC.
- ^ Эбербах и Вегнер, 2003 г..
- ^ Абрамсон, Даррен (2011). «Философия разума - это (отчасти) философия информатики». Умы и машины. 21 (2): 203-219.
- ^ Коупленд, Б. Джек (10 ноября 2017 г.). "Тезис Черча-Тьюринга". В Залта, Эдуард Н. (ред.). Стэнфордская энциклопедия философии.
- ^ Чтобы найти хорошее место, где можно найти оригинальные документы, см. Чалмерс, Дэвид Дж., изд. (2002). Философия разума: классические и современные чтения. Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-514581-6. OCLC 610918145.
- ^ Коупленд, Б. Джек (2004). «Вычисление». В Флориди, Лучано (ред.). Руководство Blackwell по философии вычислений и информации. Вили-Блэквелл. п. 15. ISBN 978-0-631-22919-3.
- ^ ср Пенроуз, Роджер (1990). «Алгоритмы и машины Тьюринга». Новый разум императора: о компьютерах, разуме и законах физики. Оксфорд: Издательство Оксфордского университета. С. 47–49. ISBN 978-0-19-851973-7. OCLC 456785846.
- ^ Также описание «неалгоритмической природы математического понимания», Пенроуз, Роджер (1990). «Где кроется физика разума?». Новый разум императора: о компьютерах, разуме и законах физики. Оксфорд: Издательство Оксфордского университета. С. 416–418. ISBN 978-0-19-851973-7. OCLC 456785846.
- ^ Пьерджиоргио Одифредди (1989). Классическая теория рекурсии. Исследования по логике и основам математики. 125. Амстердам: Северная Голландия.
- ^ Бургин, Марк (2005). Супер-рекурсивные алгоритмы. Монографии по информатике. Нью-Йорк: Спрингер. ISBN 978-0-387-95569-8. OCLC 990755791.
Рекомендации
- Барвайз, Джон; Кейслер, Х.Дж.; Кунен, Кеннет, ред. (1980). Клини симпозиум. Амстердам: Издательская компания Северной Голландии. ISBN 978-0-444-85345-5.CS1 maint: ref = harv (связь)
- Бен-Амрам, А. (2005). "Тезис Черча-Тьюринга и его двойники" (PS). Новости SIGACT. 36 (3): 113–116. CiteSeerX 10.1.1.74.7308. Дои:10.1145/1086649.1086651.
- Бернштейн, Э; Вазирани, У. (1997). «Квантовая теория сложности». SIAM Журнал по вычислениям. 26 (5): 1411–1473. CiteSeerX 10.1.1.655.1186. Дои:10.1137 / S0097539796300921.
- Бласс, Андреас; Гуревич Юрий (Октябрь 2003 г.). «Алгоритмы: поиски абсолютных определений» (PDF). Бюллетень Европейской ассоциации теоретической информатики (81).[страница нужна ]
- Бургин, Марк (2005). «Суперрекурсивные алгоритмы». Монографии по информатике. Springer. ISBN 978-0-387-95569-8.
- Церковь, Алонсо (1932). «Набор постулатов для основы логики». Анналы математики. 33 (2): 346–366. Дои:10.2307/1968337. JSTOR 1968337.
- Церковь, Алонсо (апрель 1936 г.). «Неразрешимая проблема элементарной теории чисел». Американский журнал математики. 58 (2): 345–363. Дои:10.2307/2371045. JSTOR 2371045.CS1 maint: ref = harv (связь)
- Церковь, Алонсо (июнь 1936b). «Заметка о проблеме Entscheidungsproblem». Журнал символической логики. 1 (1): 40–41. Дои:10.2307/2269326. JSTOR 2269326.CS1 maint: ref = harv (связь)
- Церковь, Алонсо (март 1937 г.). "Обзор: А. М. Тьюринг, О вычислимых числах, в приложении к Entscheidungsproblem". Журнал символической логики. 2 (1): 42–43. Дои:10.2307/2268810. JSTOR 2268810.CS1 maint: ref = harv (связь)
- Церковь, Алонсо (1941). The Calculi of Lambda-Conversion. Принстон: Издательство Принстонского университета.
- Купер, С.Б .; Одифредди, П. (2003). «Неисчислимость в природе». В С. Б. Купере; Гончаров С.С. (ред.). Вычислимость и модели: перспективы Востока и Запада. Kluwer Academic / Plenum Publishers. С. 137–160.
- Дэвис, Мартин, изд. (1965). Неразрешимые, основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях. Нью-Йорк: Raven Press.CS1 maint: ref = harv (связь) Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
- Dawson, John W., Jr. (1997). Логические дилеммы: жизнь и творчество Курта Гёделя. Wellesley, MA: A.K. Питерс.
- Eberbach, E.; Wegner, P. (October 2003). "Beyond Turing Machines". Бюллетень Европейской ассоциации теоретической информатики (81): 279–304.CS1 maint: ref = harv (связь)
- Gabbay, D.M. (2001). Справочник по философской логике. 1 (2-е изд.).CS1 maint: ref = harv (связь)
- Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". In H.J. Barwise; H.J. Keisler; K. Kunen (eds.). The Kleene Symposium. Издательская компания Северной Голландии. pp. 123–148.CS1 maint: ref = harv (связь)
- Gandy, Robin (1994). Herken, Rolf (ed.). The universal Turing Machine: A Half-Century Survey. New York: Wien Springer–Verlag. pp. 51ff. ISBN 978-3-211-82637-9.CS1 maint: ref = harv (связь)
- Gödel, Kurt (1965) [1934]. "On Undecidable Propositions of Formal Mathematical Systems". In Davis, Martin (ed.). Неразрешимый. Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor). Нью-Йорк: Raven Press.
- Gödel, Kurt (1936). "Über die Lāange von Beweisen" [On The Length of Proofs]. Ergenbnisse Eines Mathematishen Kolloquiums (на немецком). Heft (7): 23–24. Cited by Клини (1952).
- Gurevich, Yuri (Июнь 1988 г.). "On Kolmogorov Machines and Related Issues". Bulletin of European Association for Theoretical Computer Science (35): 71–82.
- Gurevich, Yuri (July 2000). "Sequential Abstract State Machines Capture Sequential Algorithms" (PDF). Транзакции ACM по вычислительной логике. 1 (1): 77–111. CiteSeerX 10.1.1.146.3017. Дои:10.1145/343369.343384.
- Herbrand, Jacques (1932). "Sur la non-contradiction de l'arithmétique". Journal für die Reine und Angewandte Mathematik (На французском). 166: 1–8.
- Хофштадтер, Дуглас Р. "Chapter XVII: Church, Turing, Tarski, and Others". Гедель, Эшер, Бах: вечная золотая коса.[страницы необходимы ]
- Клини, Стивен Коул (January 1935). "A Theory of Positive Integers in Formal Logic". Американский журнал математики. 57 (1): 153–173 & 219–244. Дои:10.2307/2372027. JSTOR 2372027.
- Kleene, Stephen Cole (1936). "Lambda-Definability and Recursiveness". Математический журнал герцога. 2 (2): 340–353. Дои:10.1215/s0012-7094-36-00227-2.
- Kleene, Stephen Cole (1943). "Recursive Predicates and Quantifiers". American Mathematical Society Transactions. 54 (1): 41–73. Дои:10.2307/1990131. JSTOR 1990131. Перепечатано в Неразрешимый, п. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Клини 1952:300) and name it "Church's Thesis" (Клини 1952:317) (i.e., the Church thesis ).
- Kleene, Stephen Cole (1952). Введение в метаматематику. Северная Голландия. OCLC 523942.CS1 maint: ref = harv (связь)
- Knuth, Donald (1973). Искусство программирования. 1/Fundamental Algorithms (2nd ed.). Аддисон-Уэсли.
- Kugel, Peter (November 2005). "It's time to think outside the computational box". Коммуникации ACM. 48 (11): 32–37. CiteSeerX 10.1.1.137.6939. Дои:10.1145/1096000.1096001.
- Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. Река Аппер Сэдл, Нью-Джерси, США: Прентис-Холл.
- Манна, Зоар (2003) [1974]. Mathematical Theory of Computation. Дувр. ISBN 978-0-486-43238-0.
- Марков, А.А. (1960) [1954]. "The Theory of Algorithms". Переводы Американского математического общества. 2 (15): 1–14.
- Olszewski, Adam; Woleński, Jan; Janusz, Robert, eds. (2006). Church's Thesis After 70 Years. Frankfurt: Ontos. ISBN 978-3-938793-09-1. OCLC 909679288.CS1 maint: ref = harv (связь)
- Pour-El, M.B.; Richards, J.I. (1989). Computability in Analysis and Physics. Springer Verlag.
- Rosser, J. B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". Журнал символической логики. 4 (2): 53–60. Дои:10.2307/2269059. JSTOR 2269059.CS1 maint: ref = harv (связь)
- Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, eds. (2002). Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman. Lecture Notes in Logic. 15. А. К. Петерс, ООО ISBN 978-1-56881-169-7.CS1 maint: ref = harv (связь)
- Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church–Turing Barrier. Springer. ISBN 978-0-387-30886-9.
- Тьюринг, А. (1937) [Delivered to the Society November 1936], "О вычислимых числах в приложении к Entscheidungsproblem" (PDF), Труды Лондонского математического общества, 2, 42, pp. 230–65, Дои:10.1112 / плмс / с2-42.1.230CS1 maint: ref = harv (связь) и Тьюринг, А. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". Труды Лондонского математического общества. 2. 43 (published 1937). pp. 544–6. Дои:10.1112 / плмс / с2-43.6.544. (Смотрите также: Davis 1965:115ff)
- Alan Mathison Turing (Dec 1937). "Computability and λ-Definability" (PDF). Журнал символической логики. 2 (4): 153–163. Дои:10.2307/2268280. JSTOR 2268280.CS1 maint: ref = harv (связь)
внешняя ссылка
- "The Church–Turing Thesis" запись Б. Джек Коупленд в Стэнфордская энциклопедия философии.
- "Computation in Physical Systems" запись Гуальтьеро Пиччинини в Стэнфордская энциклопедия философии —a comprehensive philosophical treatment of relevant issues.
- Kaznatcheev, Artem (September 11, 2014). "Transcendental idealism and Post's variant of the Church-Turing thesis". Журнал символической логики. 1 (3): 103–105.
- А специальный выпуск (Vol.28, No.4, 1987) of the Журнал формальной логики Нотр-Дам was devoted to the Church-Turing thesis.