Тезис Чёрча — Тьюринга
Те́зис Чёрча — Тью́ринга — фундаментальное эвристическое утверждение, постулирующее эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть[1].
Тезис был высказан Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов[2] [3][4]. Существенен для многих областей науки и философии науки, в том числе для математической логики, теории доказательств, информатики, кибернетики.
Формулировки
В терминах теории рекурсии, тезис формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча[5].
Более общая формулировка была дана Стивеном Клини, согласно которой все частичные (то есть не обязательно определенные для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными[6].
В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга[7]. Иногда в такой формулировке фигурирует как тезис Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.
Позднее были сформулированы другие практические варианты утверждения:
- физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;
- сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.
Напишите отзыв о статье "Тезис Чёрча — Тьюринга"
Примечания
- ↑ Математическая логика, 1973, с. 280.
- ↑ Church, Alonzo (1936). «An Unsolvable Problem of Elementary Number Theory». American Journal of Mathematics 58 (58): 345–363. DOI:10.2307/2371045.
- ↑ Church, Alonzo (1936). «A Note on the Entscheidungsproblem». Journal of Symbolic Logic (1): 40–41.
- ↑ Turing, Alan (1936). «On computable numbers, with an application to the Entscheidungsproblem». Proc. London Math. Soc. (42): 230–265.
- ↑ Жар холодных числ и пафос бесстрастной логики, 1977, с. 143.
- ↑ Алгоритмы и рекурсивные функции, 1986, с. 12.
- ↑ Новый ум короля, 2003, с. 55.
Литература
- Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
- Бирюков Б. В., Тростников В. Н. Жар холодных числ и пафос бесстрастной логики. — М.: Знание, 1977. — 192 с.
- Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 368 с.
- Пенроуз Р. Новый ум короля. — М.: Едиториал УРСС, 2003. — 384 с.
|
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Тезис Чёрча — Тьюринга
В середине третьего экосеза зашевелились стулья в гостиной, где играли граф и Марья Дмитриевна, и большая часть почетных гостей и старички, потягиваясь после долгого сиденья и укладывая в карманы бумажники и кошельки, выходили в двери залы. Впереди шла Марья Дмитриевна с графом – оба с веселыми лицами. Граф с шутливою вежливостью, как то по балетному, подал округленную руку Марье Дмитриевне. Он выпрямился, и лицо его озарилось особенною молодецки хитрою улыбкой, и как только дотанцовали последнюю фигуру экосеза, он ударил в ладоши музыкантам и закричал на хоры, обращаясь к первой скрипке:
– Семен! Данилу Купора знаешь?
Это был любимый танец графа, танцованный им еще в молодости. (Данило Купор была собственно одна фигура англеза .)
– Смотрите на папа, – закричала на всю залу Наташа (совершенно забыв, что она танцует с большим), пригибая к коленам свою кудрявую головку и заливаясь своим звонким смехом по всей зале.
Действительно, всё, что только было в зале, с улыбкою радости смотрело на веселого старичка, который рядом с своею сановитою дамой, Марьей Дмитриевной, бывшей выше его ростом, округлял руки, в такт потряхивая ими, расправлял плечи, вывертывал ноги, слегка притопывая, и всё более и более распускавшеюся улыбкой на своем круглом лице приготовлял зрителей к тому, что будет. Как только заслышались веселые, вызывающие звуки Данилы Купора, похожие на развеселого трепачка, все двери залы вдруг заставились с одной стороны мужскими, с другой – женскими улыбающимися лицами дворовых, вышедших посмотреть на веселящегося барина.
– Батюшка то наш! Орел! – проговорила громко няня из одной двери.
Граф танцовал хорошо и знал это, но его дама вовсе не умела и не хотела хорошо танцовать. Ее огромное тело стояло прямо с опущенными вниз мощными руками (она передала ридикюль графине); только одно строгое, но красивое лицо ее танцовало. Что выражалось во всей круглой фигуре графа, у Марьи Дмитриевны выражалось лишь в более и более улыбающемся лице и вздергивающемся носе. Но зато, ежели граф, всё более и более расходясь, пленял зрителей неожиданностью ловких выверток и легких прыжков своих мягких ног, Марья Дмитриевна малейшим усердием при движении плеч или округлении рук в поворотах и притопываньях, производила не меньшее впечатление по заслуге, которую ценил всякий при ее тучности и всегдашней суровости. Пляска оживлялась всё более и более. Визави не могли ни на минуту обратить на себя внимания и даже не старались о том. Всё было занято графом и Марьею Дмитриевной. Наташа дергала за рукава и платье всех присутствовавших, которые и без того не спускали глаз с танцующих, и требовала, чтоб смотрели на папеньку. Граф в промежутках танца тяжело переводил дух, махал и кричал музыкантам, чтоб они играли скорее. Скорее, скорее и скорее, лише, лише и лише развертывался граф, то на цыпочках, то на каблуках, носясь вокруг Марьи Дмитриевны и, наконец, повернув свою даму к ее месту, сделал последнее па, подняв сзади кверху свою мягкую ногу, склонив вспотевшую голову с улыбающимся лицом и округло размахнув правою рукой среди грохота рукоплесканий и хохота, особенно Наташи. Оба танцующие остановились, тяжело переводя дыхание и утираясь батистовыми платками.
– Вот как в наше время танцовывали, ma chere, – сказал граф.
– Ай да Данила Купор! – тяжело и продолжительно выпуская дух и засучивая рукава, сказала Марья Дмитриевна.
В то время как у Ростовых танцовали в зале шестой англез под звуки от усталости фальшививших музыкантов, и усталые официанты и повара готовили ужин, с графом Безухим сделался шестой удар. Доктора объявили, что надежды к выздоровлению нет; больному дана была глухая исповедь и причастие; делали приготовления для соборования, и в доме была суетня и тревога ожидания, обыкновенные в такие минуты. Вне дома, за воротами толпились, скрываясь от подъезжавших экипажей, гробовщики, ожидая богатого заказа на похороны графа. Главнокомандующий Москвы, который беспрестанно присылал адъютантов узнавать о положении графа, в этот вечер сам приезжал проститься с знаменитым Екатерининским вельможей, графом Безухим.
