Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
«Тезис Чёрча» перенаправляется сюда. Об аксиоме CT в конструктивной математике см . Тезис Черча (конструктивная математика) .

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

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

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

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

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

Утверждение словами Черча и Тьюринга [ править ]

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

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

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

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

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

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

История [ править ]

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

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

Приблизительно 1930–1952 гг. [ Править ]

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

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

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

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

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

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

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

Скорее, он рассматривал понятие «эффективной вычислимости» как просто «рабочую гипотезу», которая могла бы с помощью индуктивных рассуждений привести к « естественному закону », а не «определению или аксиоме». [26] Эта идея подверглась «резкой» критике со стороны Церкви. [27]

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

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

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

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

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

Клини предлагает Тезис I. Это оставило Клини явное выражение «тезиса». В своей статье 1943 года « Рекурсивные предикаты и квантификаторы» Клини предложил свой «ТЕЗИС I»:

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

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

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

ссылки Church 1936; [ недостаточно конкретен, чтобы проверить ] ( 23 ) ссылается на Тьюринг 1936-7. Клини отмечает, что:

этот тезис носит характер гипотезы - на это подчеркивали Пост и Черч ( 24 ). Если мы рассматриваем тезис и его обратное как определение, то гипотеза - это гипотеза о применении математической теории, разработанной на основе определения. Для принятия гипотезы есть, как мы и предполагали, довольно веские основания. [33]

(24) ссылки Post 1936 of Post и Church's Formal definitions в теории порядковых чисел , Fund. Математика . том 28 (1936), стр. 11–21 (см. исх. № 2, Davis 1965 : 286).

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

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

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

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

Клини, наконец, впервые использует термин «тезис Черча-Тьюринга» в разделе, в котором он помогает прояснить концепции в статье Алана Тьюринга «Проблема слова в полугруппах с отменой», как того требует критика Уильяма Буна. [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) добавляет к списку функции, « считаемые в системе S 1 » Курта Гёделя, 1936 г., и Эмиля Поста (1943, 1946), « канонические [также называемые нормальными ] системами ». [46] В 1950-х годах Хао Ван и Мартин Дэвис значительно упростили модель однопленочной машины Тьюринга (см. Машину Пост-Тьюринга ). Марвин Минскирасширили модель до двух или более лент и значительно упростили ленты до «счетчиков вверх-вниз», которые Мелзак и Ламбек в дальнейшем развили в то, что теперь известно как модель счетчиков . В конце 1960-х - начале 1970-х годов исследователи расширили модель счетной машины до счетной машины , близкого родственника современной концепции компьютера . Другие модели включают комбинаторную логику и алгоритмы Маркова . Гуревич добавляет модель указательной машины Колмогорова и Успенского (1953, 1958): «... они просто хотели ... убедить себя, что нет никакого способа расширить понятие вычислимой функции». [47]

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

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

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

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

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

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

Варианты [ править ]

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

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

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

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

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

Философские последствия [ править ]

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

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

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

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

Невычислимые функции [ править ]

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

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

См. Также [ править ]

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

Сноски [ править ]

  1. ^ Роберт Соар , «Машины Тьюринга Oracle, онлайн-вычисления и три смещения в теории вычислимости»
  2. ↑ Рабин, Майкл О. (июнь 2012 г.). Тьюринг, Чёрч, Гёдель, вычислимость, сложность и рандомизация: личный взгляд . Архивировано из оригинала на 2019-06-05 . Проверено 14 июля 2012 .
  3. ^ Церковь 1936
  4. ^ Клини 1936
  5. ^ Тьюринг 1937a
  6. ^ Клини 1936
  7. ^ Тьюринг 1937b . Схема доказательства на стр.153: [6]
  8. ^ Россер 1939 в Дэвисе 1965 : 225.
  9. ^ "эффективный". Новый университетский словарь Мерриам Вебстер (9-е изд.).
  10. ^ См. Также «эффективный». Онлайн-словарь Мерриам-Вебстера (11-е изд.) . Проверено 26 июля 2014 г. , который также дает эти определения слова «эффективный» - первый [«производит решающий, решающий или желаемый эффект»] как определение смысла «1а» слова «эффективный», а второй [«способный произвести результат "] как часть" Обсуждения синонимов ЭФФЕКТИВНОСТИ "(во вводной части, где суммируются сходства между значениями слов" эффективный "," действенный "," действенный "и" действенный ").
  11. ^ а б Тьюринг, AM (1938). Системы логики на основе порядковых чисел (PDF) (PhD). Университет Принстона. п. 8. Архивировано из оригинального (PDF) 23.10.2012 . Проверено 23 июня 2012 .
  12. ^ Ганди (1980 : 123) утверждает это так: То, что эффективно вычислимо, является вычислимым. Он называет это «тезисом Чёрча».
  13. ^ Давид Гильберт и Вильгельм Акерманн: Grundzüge der Theoretischen Logik, Берлин, Германия, Springer, 1-е изд. 1928. (6-е изд. 1972, ISBN 3-540-05843-5 ) Английский перевод: Дэвид Гильберт и Вильгельм Аккерманн: принципы математической логики, AMS Chelsea Publishing, Провиденс, Род-Айленд, США, 1950 
  14. ^ Комментарий Дэвиса перед Черч 1936 Неразрешимая проблема элементарной теории чисел в Дэвисе 1965: 88. Черч использует слова «эффективная вычислимость» на странице 100 и далее.
  15. ^ В своем обзоре диссертации Черча через 70 лет под редакцией Адама Ольшевского и др. В 2006 году Питер Смит критика статьи Мурасвски и Воленски предлагает 4 «линии» относительно статуса тезиса Черча – Тьюринга: (1) эмпирическая гипотеза (2) аксиома или теорема, (3) определение, (4) объяснение. Но Смит считает, что (4) неотличимо от (3), см. Смит (11 июля 2007 г.) Тезис Черча через 70 лет на http://www.logicmatters.net/resources/pdfs/CTT.pdf.
  16. ^ см. сноску 3 в Church 1936a Неразрешимая проблема элементарной теории чисел в Дэвисе 1965 : 89.
  17. ↑ Доусон 1997 : 99.
  18. ^ а б Зиг 1997: 160.
  19. ↑ Sieg 1997: 160 цитируется из письма Черча Клини 1935 года, см. Сноску 3 в Gödel 1934 в Davis 1965 : 44.
  20. ^ ср. Церковь 1936 года в Дэвисе 1965 : 105 и далее.
  21. ↑ Комментарий Дэвиса до Гёделя 1934 в Davis 1965 : 40.
  22. ^ Для подробного обсуждения принятия Гёделем машин Тьюринга в качестве моделей вычислений см. Шагрир. «Гедель о Тьюринге о вычислимости» (PDF) . Архивировано из оригинального (PDF) 17 декабря 2015 года . Проверено 8 февраля 2016 . [ дата отсутствует ]
  23. ^ а б Тьюринг 1937 .
  24. ^ ср. Сноска редактора к « Конечному комбинаторному процессу после 1936 года» . Формулировка I. в Davis 1965 : 289.
  25. ↑ Post 1936 in Davis 1965 : 291, сноска 8.
  26. ^ Сообщение 1936 в Дэвисе 1952: 291.
  27. ↑ Sieg 1997: 171 и 176–177.
  28. ^ Тьюринг 1936-37 в Дэвисе 1965 : 263ff.
  29. ^ Церковь 1937 .
  30. ^ Тьюринг 1939 в Дэвисе: 160.
  31. ^ ср. Church 1934 в Davis 1965 : 100, также Turing 1939 в Davis 1965 : 160.
  32. ^ курсив добавлен, Россер 1939 в Дэвис 1965 : 226.
  33. ^ a b Клини 1943 в Дэвисе 1965 : 274.
  34. Перейти ↑ Kleene 1952 : 300.
  35. ^ a b {{harvcolnb | Kleene | 1952 | p = 376}.
  36. ^ Клини 1952 : 382 536
  37. ^ Gandy 1980 : 123ff.
  38. ^ Gandy 1980 : 135.
  39. ^ Gandy 1980 : 126
  40. ^ Зиг 1998-9 в Зиг, Somner & Talcott 2002 : 390ff; также Sieg 1997: 154ff.
  41. ^ В сноске Зиг разбивает статью Поста 1936 года (B) на (B.1) и (B.2) и (L) на (L.1) и (L.2) и описывает (D) по-разному. Что касается предложенной им машины Ганди, он позже добавляет LC.1, LC.2, GA.1 и GA.2. Это сложно; см. Sieg 1998–99 in Sieg, Somner & Talcott 2002 : 390ff.
  42. ^ Сборник статей можно найти в Olszewski, Woleński & Janusz (2006) . Также обзор этой коллекции: Питер Смит (11 июля 2007 г.). «Церковный тезис через 70 лет» (PDF) .
  43. ↑ См. Также Ходжес, Эндрю (2005). «Были ли у Черча и Тьюринга тезисы о машинах?» (PDF) . Архивировано из оригинального (PDF) 4 марта 2016 года . Проверено 27 июля 2014 года .
  44. Перейти ↑ Gödel, Kurt (1995) [193?]. «Неразрешимые диофантовы предложения» . У Фефермана, Соломона (ред.). Собрание сочинений . 3 . Нью-Йорк: Издательство Оксфордского университета. п. 168 . ISBN 978-0-19-507255-6. OCLC  928791907 - через Google Книги.
  45. ^ Соара, Роберт И. (сентябрь 1996). «Вычислимость и рекурсия». Вестник символической логики . 2 (3): 284–321. CiteSeerX 10.1.1.35.5803 . DOI : 10.2307 / 420992 . JSTOR 420992 .  
  46. ^ Клини 1952: 320
  47. ↑ Гуревич 1988: 2
  48. ^ перевод Гёделя (1936) Дэвисом в The Undecidable p. 83, отличаясь использованием слова «рассчитанный» в переводе в Kleene (1952) p. 321
  49. ^ Хорстен в Ольшевский 2006 : 256.
  50. ^ Gabbay 2001 : 284
  51. ^ Piccinini, Gualtiero (январь 2007). «Вычислительный подход, тезис Чёрча-Тьюринга и заблуждение Чёрча-Тьюринга» (PDF) . Synthese . 154 (1): 97–120. CiteSeerX 10.1.1.360.9796 . DOI : 10.1007 / s11229-005-0194-Z . S2CID 494161 .   
  52. ^ Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4. Разделы 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы 1.9».
  53. ^ "Официальное описание проблемы" (PDF) . Архивировано из оригинального (PDF) 24 ноября 2005 года.
  54. ^ a b Кэй, Филипп; Лафламм, Раймонд; Моска, Микеле (2007). Введение в квантовые вычисления . Издательство Оксфордского университета. С. 5–6. ISBN 978-0-19-857049-3.
  55. ^ Ван Emde Боаш, Питер (1990). «Модели машин и симуляторы». Справочник по теоретической информатике A . Эльзевир. п. 5.
  56. ^ Слот, C .; ван Эмде Боас, П. (декабрь 1984 г.). На ленте по сравнению с ядром: применение эффективных хэш-функций, эффективно использующих пространство, для неизменности пространства . STOC .
  57. ^ Eberbach & Вегнер 2003 .
  58. ^ Абрамсон, Даррен (2011). «Философия разума - это (отчасти) философия информатики» . Умы и машины . 21 (2): 203–219. DOI : 10.1007 / s11023-011-9236-0 . S2CID 32116031 . 
  59. ↑ Copeland, B. Jack (10 ноября 2017 г.). «Тезис Черча-Тьюринга» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
  60. ↑ Хорошее место, где можно найти оригинальные статьи, см. В Chalmers, David J. , ed. (2002). Философия разума: классические и современные чтения . Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-514581-6. OCLC  610918145 .
  61. Перейти ↑ Copeland, B. Jack (2004). «Вычисление». Во Флориди, Лучано (ред.). Руководство Blackwell по философии вычислений и информации . Вили-Блэквелл. п. 15. ISBN 978-0-631-22919-3.
  62. ^ ср Пенроуз, Роджер (1990). «Алгоритмы и машины Тьюринга». Новый разум императора: о компьютерах, разуме и законах физики . Оксфорд: Издательство Оксфордского университета. С. 47–49. ISBN 978-0-19-851973-7. OCLC  456785846 .
  63. ^ Также описание «неалгоритмической природы математического понимания», Пенроуз, Роджер (1990). «Где кроется физика разума?». Новый разум императора: о компьютерах, разуме и законах физики . Оксфорд: Издательство Оксфордского университета. С. 416–418. ISBN 978-0-19-851973-7. OCLC  456785846 .
  64. ^ Пирджиорджио Одифредди (1989). Классическая теория рекурсии . Исследования по логике и основам математики. 125 . Амстердам: Северная Голландия.
  65. ^ Бургин, Марк (2005). Суперрекурсивные алгоритмы . Монографии по информатике. Нью-Йорк: Спрингер. ISBN 978-0-387-95569-8. OCLC  990755791 .

Ссылки [ править ]

  • Барвайз, Джон ; Кейслер, HJ ; Кунен, Кеннет , ред. (1980). Клини симпозиум . Амстердам: Издательская компания Северной Голландии. ISBN 978-0-444-85345-5.
  • Бен-Амрам, AM (2005). «Тезис Черча-Тьюринга и его двойники» (PS) . Новости SIGACT . 36 (3): 113–116. CiteSeerX  10.1.1.74.7308 . DOI : 10.1145 / 1086649.1086651 . S2CID  13566703 .
  • Бернштейн, Э; Вазирани, У. (1997). «Квантовая теория сложности». SIAM Journal on Computing . 26 (5): 1411–1473. CiteSeerX  10.1.1.655.1186 . DOI : 10,1137 / S0097539796300921 .
  • Бласс, Андреас ; Гуревич, Юрий (октябрь 2003 г.). «Алгоритмы: поиски абсолютных определений» (PDF) . Бюллетень Европейской ассоциации теоретической информатики (81).[ требуется страница ]
  • Бургин, Марк (2005). «Суперрекурсивные алгоритмы». Монографии по информатике . Springer. ISBN 978-0-387-95569-8.
  • Церковь, Алонсо (1932). «Набор постулатов для основы логики». Анналы математики . 33 (2): 346–366. DOI : 10.2307 / 1968337 . JSTOR  1968337 .
  • Церковь, Алонсо (апрель 1936 г.). "Неразрешимая проблема элементарной теории чисел" (PDF) . Американский журнал математики . 58 (2): 345–363. DOI : 10.2307 / 2371045 . JSTOR  2371045 . Архивировано из оригинального (PDF) 27 февраля 2020 года.
  • Церковь, Алонсо (июнь 1936b). «Заметка о проблеме Entscheidungsproblem». Журнал символической логики . 1 (1): 40–41. DOI : 10.2307 / 2269326 . JSTOR  2269326 .
  • Церковь, Алонсо (март 1937 г.). "Обзор: AM Тьюринг, О вычислимых числах, в приложении к Entscheidungsproblem". Журнал символической логики . 2 (1): 42–43. DOI : 10.2307 / 2268810 . JSTOR  2268810 .
  • Церковь, Алонсо (1941). Исчисления лямбда-преобразования . Принстон: Издательство Принстонского университета.
  • Купер, С.Б.; Одифредди, П. (2003). «Неисчислимость в природе». В С. Б. Купере; С.С. Гончаров (ред.). Вычислимость и модели: перспективы Востока и Запада . Kluwer Academic / Plenum Publishers. С. 137–160.
  • Дэвис, Мартин , изд. (1965). Неразрешимые, основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях . Нью-Йорк: Raven Press. Включает оригинальные статьи Гёделя, Черча, Тьюринга, Россера, Клини и Поста, упомянутые в этом разделе.
  • Доусон, Джон В. Младший (1997). Логические дилеммы: жизнь и творчество Курта Гёделя . Уэллсли, Массачусетс: А.К. Петерс.
  • Eberbach, E .; Вегнер, П. (октябрь 2003 г.). «За пределами машин Тьюринга». Бюллетень Европейской ассоциации теоретической информатики (81): 279–304.
  • Габбай, DM (2001). Справочник по философской логике . 1 (2-е изд.).
  • Ганди, Робин (1980). «Тезис Черча и принципы механизмов». В HJ Barwise; Х. Дж. Кейслер; К. Кунен (ред.). Клини симпозиум . Издательская компания Северной Голландии. С. 123–148.
  • Ганди, Робин (1994). Херкен, Рольф (ред.). Универсальная машина Тьюринга: обзор за полвека . Нью-Йорк: Wien Springer – Verlag. стр. 51 и далее. ISBN 978-3-211-82637-9.
  • Гедель, Курт (1965) [1934]. «О неразрешимых предложениях формальных математических систем». В Дэвисе, Мартине (ред.). Неразрешимое . Клини и Россер (читатели лекций); Институт перспективных исследований (спонсор лекции). Нью-Йорк: Raven Press.
  • Гёдель, Курт (1936). "Über die Lāange von Beweisen" [О длине доказательств]. Ergenbnisse Eines Mathematishen Kolloquiums (на немецком языке). Heft (7): 23–24.Цитируется Клини (1952) .
  • Гуревич, Юрий (июнь 1988 г.). «О колмогоровских машинах и смежных вопросах». Бюллетень Европейской ассоциации теоретической информатики (35): 71–82.
  • Гуревич, Юрий (июль 2000 г.). "Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы" (PDF) . ACM-транзакции по вычислительной логике . 1 (1): 77–111. CiteSeerX  10.1.1.146.3017 . DOI : 10.1145 / 343369.343384 . S2CID  2031696 .
  • Эрбранд, Жак (1932). "Sur la non-противоречие де l'arithmétique". Journal für die Reine und Angewandte Mathematik (на французском языке). 166 : 1–8.
  • Хофштадтер, Дуглас Р. "Глава XVII: Церковь, Тьюринг, Тарский и другие". Гедель, Эшер, Бах: вечная золотая коса .[ необходимы страницы ]
  • Клини, Стивен Коул (январь 1935 г.). «Теория положительных целых чисел в формальной логике». Американский журнал математики . 57 (1): 153–173 и 219–244. DOI : 10.2307 / 2372027 . JSTOR  2372027 .
  • Клини, Стивен Коул (1936). «Лямбда-определимость и рекурсивность». Математический журнал герцога . 2 (2): 340–353. DOI : 10,1215 / s0012-7094-36-00227-2 .
  • Клини, Стивен Коул (1943). «Рекурсивные предикаты и квантификаторы» . Труды Американского математического общества . 54 (1): 41–73. DOI : 10.2307 / 1990131 . JSTOR  1990131 .Перепечатано в The Undecidable , p. 255ff. Клини уточнил свое определение «общей рекурсии» и продолжил в своей главе «12. Алгоритмические теории» постулировать «Тезис I» (стр. 274); Позже он повторил этот тезис (в Kleene 1952 : 300) и назвал его «Тезисом Чёрча» ( Kleene 1952 : 317) (то есть тезисом Чёрча ).
  • Клини, Стивен Коул (1952). Введение в метаматематику . Северная Голландия. OCLC  523942 .
  • Кнут, Дональд (1973). Искусство программирования . 1 / Фундаментальные алгоритмы (2-е изд.). Аддисон-Уэсли.
  • Кугель, Питер (ноябрь 2005 г.). «Пора мыслить нестандартно». Коммуникации ACM . 48 (11): 32–37. CiteSeerX  10.1.1.137.6939 . DOI : 10.1145 / 1096000.1096001 . S2CID  29843806 .
  • Льюис, HR ; Пападимитриу, СН (1998). Элементы теории вычислений . Река Аппер Сэдл, Нью-Джерси, США: Прентис-Холл.
  • Манна, Зохар (2003) [1974]. Математическая теория вычислений . Дувр. ISBN 978-0-486-43238-0.
  • Марков А.А. (1960) [1954]. «Теория алгоритмов». Переводы Американского математического общества . 2 (15): 1–14.
  • Ольшевский, Адам; Воленски, Ян; Януш, Роберт, ред. (2006). Тезис Чёрча через 70 лет . Франкфурт: Онтос. ISBN 978-3-938793-09-1. OCLC  909679288 .
  • Залив-Эл, МБ ; Ричардс, Дж. И. (1989). Вычислимость в анализе и физике . Springer Verlag .
  • Россер, JB (1939). "Неформальное изложение доказательств теоремы Гёделя и теоремы Чёрча". Журнал символической логики . 4 (2): 53–60. DOI : 10.2307 / 2269059 . JSTOR  2269059 .
  • Зиг, Вильфрид; Соммер, Ричард; Талкотт, Кэролайн, ред. (2002). Размышления об основах математики: Очерки в честь Соломона Фефермана . Конспект лекций по логике. 15 . АК Петерс, ООО ISBN 978-1-56881-169-7.
  • Сиропулос, Апостолос (2008). Гипервычисления: вычисления за пределами барьера Чёрча – Тьюринга . Springer. ISBN 978-0-387-30886-9.
  • Тьюринг, AM (1937) [доставлено Обществу в ноябре 1936 г.], «О вычислимых числах в приложении к Entscheidungsproblem» (PDF) , Труды Лондонского математического общества , 2, 42 , стр. 230–65, doi : 10.1112 / плмс / с2-42.1.230и Тьюринг AM (1938). «О вычислимых числах в приложении к Entscheidungsproblem: исправление». Труды Лондонского математического общества . 2. 43 (опубликовано в 1937 г.). С. 544–6. DOI : 10.1112 / ПНИЛИ / s2-43.6.544 .(См. Также: Davis 1965 : 115ff)
  • Алан Мэтисон Тьюринг (декабрь 1937 г.). «Вычислимость и λ-определимость» (PDF) . Журнал символической логики . 2 (4): 153–163. DOI : 10.2307 / 2268280 . JSTOR  2268280 . S2CID  2317046 . Архивировано из оригинального (PDF) на 2020-08-09.

Внешние ссылки [ править ]

  • Запись Б. Джека Коупленда "Тезис Черча-Тьюринга" в Стэнфордской энциклопедии философии .
  • «Вычисление в физических системах» запись по Гуалтьеро Piccinini в Stanford Encyclopedia философии -a всеобъемлющего философского рассмотрения соответствующих вопросов.
  • Казначеев, Артем (11 сентября 2014 г.). «Трансцендентальный идеализм и вариант Поста тезиса Черча-Тьюринга» . Журнал символической логики . 1 (3): 103–105.
  • Специальный выпуск (Vol.28, № 4, 1987) из Нотр - Дам Журнал формальной логики была посвящена тезиса Черча-Тьюринга.