Просмотр кода страницы Теорема Чёрча — Тьюринга

'''Теоре́ма Чёрча — Тью́ринга''' — утверждение об отсутствии [[алгоритм]]а, решающего [[Проблема разрешения|проблему разрешения]]. Используется при доказательстве [[Разрешимость теории|неразрешимости]] арифметики натуральных чисел{{sfn|Математическая логика|1973|с=297}}. Впервые была сформулирована и доказана в [[1936 год в науке|1936 году]] [[Чёрч, Алонзо|Алонзо Чёрчем]]<ref>{{статья |заглавие=An Unsolvable Problem of Elementary Number Theory |ссылка=https://archive.org/details/sim_american-journal-of-mathematics_1936-04_58_2/page/345 |издание=[[American Journal of Mathematics]] |страницы=345—363 |jstor=2371045 |том=58 |doi=10.2307/2371045 |язык=en |автор=Church, Alonzo |год=1936 |тип=journal}}</ref><ref>{{статья |заглавие=A note on the Entscheidungsproblem |издание={{Нп3|Journal of Symbolic Logic}} |страницы=40—41 |том=1 |язык=und |автор=Church, Alonzo |год=1936}}</ref> (вместе с [[Тезис Чёрча — Тьюринга|тезисом Чёрча]]); в том же году, но несколько позже этот результат независимо получил [[Алан Тьюринг]]<ref>{{source|Q25864184|ref=Turing|ref-year=1937}} <!-- On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society --></ref><ref>{{source|Q27638524|ref=Turing|ref-year=1938}} <!-- On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction // Proceedings of the London Mathematical Society --></ref>.

== Формулировка ==
Предикат <math>(Ex)T(a, a, x)</math>{{Уточнить}}<!-- что значат все эти обозначения — это должно быть в формулировке--> неразрешим, то есть функция:
: <math>\chi (a) = \begin{cases}
  0,  & \mbox{if} (Ex)T(a, a, x) \\
  1, & \mbox{else}
\end{cases}</math>
невычислима.

Данная формулировка использует понятие вычислимости по Тьюрингу.

== См. также ==
* [[Теорема Геделя о неполноте]]
* [[Теорема Тарского о невыразимости истины]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
 | автор           = [[Клини, Стивен Коул|Клини С. К.]]
 | заглавие      = Математическая логика
 | место          = М.
 | издательство  = Мир
 | год           = 1973
 | страниц    = 480
 | isbn = 
 | ref             = Математическая логика
 }}

{{дописать|дата=2014-07-14}}

[[Категория:Математическая логика]]
[[Категория:Теория алгоритмов]]
[[Категория:Теоремы математической логики|Чёрча — Тьюринга]]
[[Категория:Метаматематика]]
[[Категория:Метатеоремы|Чёрча — Тьюринга]]
[[Категория:Именные законы и правила|Чёрча — Тьюринга]]