Тезис Чёрча — Тьюринга
Материал из Википедии — свободной encyclopedia
Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть[1]. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.
Тезис был высказан Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов[2][3][4][5]. Существенен для многих областей науки и философии науки, в том числе для математической логики, теории доказательств, информатики, кибернетики.