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

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

Те́зис Чёрча—Тью́ринга — фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В самой общей форме оно гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, эквивалентно, может быть вычислена с помощью некоторой машины Тьюринга.

Тезис Чёрча—Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».

Физический тезис Чёрча—Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга. Ограниченность физического тезиса Чёрча-Тьюринга была показана С.М.Крыловым в рамках работ по формальной технологии.

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