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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Тезис был высказан Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов[2][3][4][5]. Существенен для многих областей науки и философии науки, в том числе для математической логики, теории доказательств, информатики, кибернетики.

Формулировки[править | править вики-текст]

В терминах теории рекурсии, тезис формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча[6].

Более общая формулировка была дана Стивеном Клини, согласно которой все частичные (то есть не обязательно определенные для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными[7].

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

Позднее были сформулированы другие практические варианты утверждения:

  • физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;
  • сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]