Машина Тьюринга: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 160:
{{Рамка}}
 
== Те́зис Чёрта—Тью́ринга ==
'''Те́зис Чёрча—Тью́ринга''' — фундаментальное утверждение для многих областей науки, таких, как [[w:Теория вычислимости|теория вычислимости]], [[w:Информатика|информатика]], теоретическая кибернетика и др. Это утверждение было высказано [[w:Чёрч, Алонзо|Алонзо Чёрчем]] и [[w:Тьюринг, Алан|Аланом Тьюрингом]] в середине [[w:1930-е|1930-х]] годов.
 
В самой общей форме оно гласит, что любая интуитивно вычислимая функция является [[w:частично вычислимая функция|частично вычислимой]], или, эквивалентно, может быть вычислена с помощью некоторой [[w:Машина Тьюринга|машины Тьюринга]].
 
Тезис Чёрча—Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием [[w:частично вычислимая функция|частично вычислимой функции]] и неформальным понятием «интуитивно вычислимой функции».