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

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

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

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

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

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

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

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

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

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

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

  1. Математическая логика, 1973, с. 280
  2. Church, Alonzo (1936). «An Unsolvable Problem of Elementary Number Theory». American Journal of Mathematics 58 (58): 345–363. DOI:10.2307/2371045.
  3. Church, Alonzo (1936). «A Note on the Entscheidungsproblem». Journal of Symbolic Logic (1): 40–41.
  4. Turing, Alan (1936). «On computable numbers, with an application to the Entscheidungsproblem». Proc. London Math. Soc. (42): 230–265.
  5. Жар холодных числ и пафос бесстрастной логики, 1977, с. 143
  6. Алгоритмы и рекурсивные функции, 1986, с. 12
  7. Новый ум короля, 2003, с. 55

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

  • Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
  • Бирюков Б. В., Тростников В. Н. Жар холодных числ и пафос бесстрастной логики. — М.: Знание, 1977. — 192 с.
  • Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 368 с.
  • Пенроуз Р. Новый ум короля. — М.: Едиториал УРСС, 2003. — 384 с.