Теорема Чёрча — Тьюринга
Поделись знанием:
Лицо ее стало печально.
– Ах, графинюшка!…
И граф засуетился, доставая бумажник.
– Мне много надо, граф, мне пятьсот рублей надо.
И она, достав батистовый платок, терла им жилет мужа.
– Сейчас, сейчас. Эй, кто там? – крикнул он таким голосом, каким кричат только люди, уверенные, что те, кого они кличут, стремглав бросятся на их зов. – Послать ко мне Митеньку!
Митенька, тот дворянский сын, воспитанный у графа, который теперь заведывал всеми его делами, тихими шагами вошел в комнату.
– Вот что, мой милый, – сказал граф вошедшему почтительному молодому человеку. – Принеси ты мне… – он задумался. – Да, 700 рублей, да. Да смотри, таких рваных и грязных, как тот раз, не приноси, а хороших, для графини.
– Да, Митенька, пожалуйста, чтоб чистенькие, – сказала графиня, грустно вздыхая.
– Ваше сиятельство, когда прикажете доставить? – сказал Митенька. – Изволите знать, что… Впрочем, не извольте беспокоиться, – прибавил он, заметив, как граф уже начал тяжело и часто дышать, что всегда было признаком начинавшегося гнева. – Я было и запамятовал… Сию минуту прикажете доставить?
– Да, да, то то, принеси. Вот графине отдай.
– Экое золото у меня этот Митенька, – прибавил граф улыбаясь, когда молодой человек вышел. – Нет того, чтобы нельзя. Я же этого терпеть не могу. Всё можно.
– Ах, деньги, граф, деньги, сколько от них горя на свете! – сказала графиня. – А эти деньги мне очень нужны.
– Вы, графинюшка, мотовка известная, – проговорил граф и, поцеловав у жены руку, ушел опять в кабинет.
Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии алгоритма, решающего проблему разрешения. Используется при доказательстве неразрешимости арифметики натуральных чисел[1]. Впервые была сформулирована и доказана в 1936 году Алонзо Чёрчем[2][3] (вместе с тезисом Чёрча); в том же году, но несколько позже этот результат независимо получил Алан Тьюринг[4][5].
Формулировка
Предикат <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, с. 297.
- ↑ Church, Alonzo (1936). «An Unsolvable Problem of Elementary Number Theory». American Journal of Mathematics 58: 345—363. DOI:10.2307/2371045.
- ↑ Church, Alonzo (1936). «A note on the Entscheidungsproblem». Journal of Symbolic Logic 1: 40—41.
- ↑ Turing, A. M. (1936). «[www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf On computable numbers with an application to the Entscheidungsproblem]». Proc. London Maths. Soc. (Series 2) 42: 230—265. DOI:10.1112/plms/s2-42.1.230.
- ↑ Turing, A. M. (1938). «[www.turingarchive.org/viewer/?id=466&title=02 On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction]». Proc. London Maths. Soc. (Series 2) 43: 544—546. DOI:10.1112/plms/s2-43.6.544.
Литература
- Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Теорема Чёрча — Тьюринга
– Вот что, мой друг, – что это у тебя запачкано здесь? – сказала она, указывая на жилет. – Это сотэ, верно, – прибавила она улыбаясь. – Вот что, граф: мне денег нужно.Лицо ее стало печально.
– Ах, графинюшка!…
И граф засуетился, доставая бумажник.
– Мне много надо, граф, мне пятьсот рублей надо.
И она, достав батистовый платок, терла им жилет мужа.
– Сейчас, сейчас. Эй, кто там? – крикнул он таким голосом, каким кричат только люди, уверенные, что те, кого они кличут, стремглав бросятся на их зов. – Послать ко мне Митеньку!
Митенька, тот дворянский сын, воспитанный у графа, который теперь заведывал всеми его делами, тихими шагами вошел в комнату.
– Вот что, мой милый, – сказал граф вошедшему почтительному молодому человеку. – Принеси ты мне… – он задумался. – Да, 700 рублей, да. Да смотри, таких рваных и грязных, как тот раз, не приноси, а хороших, для графини.
– Да, Митенька, пожалуйста, чтоб чистенькие, – сказала графиня, грустно вздыхая.
– Ваше сиятельство, когда прикажете доставить? – сказал Митенька. – Изволите знать, что… Впрочем, не извольте беспокоиться, – прибавил он, заметив, как граф уже начал тяжело и часто дышать, что всегда было признаком начинавшегося гнева. – Я было и запамятовал… Сию минуту прикажете доставить?
– Да, да, то то, принеси. Вот графине отдай.
– Экое золото у меня этот Митенька, – прибавил граф улыбаясь, когда молодой человек вышел. – Нет того, чтобы нельзя. Я же этого терпеть не могу. Всё можно.
– Ах, деньги, граф, деньги, сколько от них горя на свете! – сказала графиня. – А эти деньги мне очень нужны.
– Вы, графинюшка, мотовка известная, – проговорил граф и, поцеловав у жены руку, ушел опять в кабинет.
