Тезис Чёрча — Тьюринга о вычислимости

Введение

Тезис о природе вычислимости

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

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

In 1933, Kurt Gödel, with Jacques Herbrand, formalized the definition of the class of general recursive functions: the smallest class of functions (with arbitrarily many arguments) that is closed under composition, recursion, and minimization, and includes zero, successor, and all projections. In 1936, Alonzo Church created a method for defining functions called the λ calculus. Within λ calculus, he defined an encoding of the natural numbers called the Church numerals. A function on the natural numbers is called λ computable if the corresponding function on the Church numerals can be represented by a term of the λ calculus. Also in 1936, before learning of Church's work, Alan Turing created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called Turing computable if some Turing machine computes the corresponding function on encoded natural numbers. Church, Kleene, and Turing proved that these three formally defined classes of computable functions coincide: a function is λ computable if and only if it is Turing computable, and if and only if it is general recursive. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Other formal attempts to characterize computability have subsequently strengthened this belief (see below). On the other hand, the Church–Turing thesis states that the above three formally defined classes of computable functions coincide with the informal notion of an effectively calculable function. Although the thesis has near universal acceptance, it cannot be formally proven, as the concept of effective calculability is only informally defined. Since its inception, variations on the original thesis have arisen, including statements about what can physically be realized by a computer in our universe (physical Church Turing thesis) and what can be efficiently computed (Church–Turing thesis (complexity theory)). These variations are not due to Church or Turing, but arise from later work in complexity theory and digital physics. The thesis also has implications for the philosophy of mind (see below).

Позднее развитие

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

An attempt to understand the notion of "effective computability" better led Robin Gandy (Turing's student and friend) in 1980 to analyze machine computation (as opposed to human computation acted out by a Turing machine). Gandy's curiosity about, and analysis of, cellular automata (including Conway's game of life), parallelism, and crystalline automata, led him to propose four "principles (or constraints) which it is argued, any machine must satisfy". His most important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instantaneous action at a distance". From these principles and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable." In the late 1990s Wilfried Sieg analyzed Turing's and Gandy's notions of "effective calculability" with the intent of "sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework". In his 1997 and 2002 work Sieg presents a series of constraints on the behavior of a computor—"a human computing agent who proceeds mechanically". These constraints reduce to:
"(B.1) (Boundedness) There is a fixed bound on the number of symbolic configurations a computor can immediately recognize. "(B.2) (Boundedness) There is a fixed bound on the number of internal states a computor can be in. "(L.1) (Locality) A computor can change only elements of an observed symbolic configuration. "(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a bounded distance of the immediately previously observed configuration. "(D) (Determinacy) The immediately recognizable (sub )configuration determines uniquely the next computation step (and id [instantaneous description])"; stated another way: "A computor's internal state together with the observed configuration fixes uniquely the next computation step and the next internal state." The matter remains in active discussion within the academic community.

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

Диссертация как определение

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

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

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

Вариации

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

The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the physical Church–Turing thesis states: "All physically computable functions are Turing computable." The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate another. It has been proved for instance that a (multi tape) universal Turing machine only suffers a logarithmic slowdown factor in simulating any Turing machine. A variation of the Church–Turing thesis addresses whether an arbitrary but "reasonable" model of computation can be efficiently simulated. This is called the feasibility thesis, also known as the (classical) complexity theoretic Church–Turing thesis or the extended Church–Turing thesis, which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory. It states: "A probabilistic Turing machine can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to polynomial time reductions. This thesis was originally called computational complexity theoretic Church–Turing thesis by Ethan Bernstein and Umesh Vazirani (1997). The complexity theoretic Church–Turing thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial time (BPP) equals deterministic polynomial time (P), the word 'probabilistic' is optional in the complexity theoretic Church–Turing thesis. A similar thesis, called the invariance thesis, was introduced by Cees F. Slot and Peter van Emde Boas. It states: Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant factor overhead in space." The thesis originally appeared in a paper at STOC'84, which was the first paper to show that polynomial time overhead and constant space overhead could be simultaneously achieved for a simulation of a Random Access Machine on a Turing machine. If BQP is shown to be a strict superset of BPP, it would invalidate the complexity theoretic Church–Turing thesis. In other words, there would be efficient quantum algorithms that perform tasks that do not have efficient probabilistic algorithms. This would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but it would invalidate the classical complexity theoretic Church–Turing thesis for efficiency reasons. Consequently, the quantum complexity theoretic Church–Turing thesis states: They claim that forms of computation not captured by the thesis are relevant today,
terms which they call super Turing computation.

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

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

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

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

Можно формально определить функции, которые не являются вычислимыми. Хорошо известный пример такой функции — функция «Занятый бобр». Эта функция принимает на вход число *n* и возвращает наибольшее количество символов, которое машина Тьюринга с *n* состояниями может вывести перед остановкой, при запуске без входных данных. Поиск верхней границы для функции «Занятый бобр» эквивалентен решению проблемы останова, проблемы, которая, как известно, неразрешима машинами Тьюринга. Поскольку функцию «Занятый бобр» нельзя вычислить с помощью машин Тьюринга, тезис Черча — Тьюринга утверждает, что эта функция не может быть эффективно вычислена каким-либо способом. Некоторые вычислительные модели позволяют вычислять (Черч — Тьюринг) невычислимые функции. Они известны как гиперкомпьютеры. Марк Бергин утверждает, что сверрекурсивные алгоритмы, такие как индуктивные машины Тьюринга, опровергают тезис Черча — Тьюринга. Его аргумент основан на определении алгоритма, более широком, чем обычно принимаемое, в результате чего невычислимые функции, полученные из некоторых индуктивных машин Тьюринга, считаются вычислимыми. Эта интерпретация тезиса Черча — Тьюринга отличается от интерпретации, общепринятой в теории вычислимости, рассмотренной выше. Аргумент о том, что сверрекурсивные алгоритмы действительно являются алгоритмами в смысле тезиса Черча — Тьюринга, не получил широкого признания в научном сообществе, занимающемся теорией вычислимости.