Википедия

Тезис Чёрча

21 Июл, 2025 / 06:49

Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.

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

Формулировки

В терминах теории рекурсии, тезис формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча.

Более общая формулировка была дана Стивеном Клини, согласно которой все частичные (то есть не обязательно определённые для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными.

В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. Иногда в такой формулировке фигурирует как тезис Тьюринга. Ввиду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Позднее были сформулированы другие практические варианты утверждения:

  • физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;
  • сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

История

Одной из важных проблем для логиков в 1930-х годах была проблема разрешения: существует ли механическая процедура для отделения математических истин от математических ложностей. Эта задача требовала, чтобы понятие «алгоритм» или «эффективная вычислимость» было закреплено, по крайней мере, чтобы приступить к задаче С самого начала и по сей день (по состоянию на 2007 год) продолжаются дебаты:. было ли понятие «эффективной вычислимости» (i) «аксиомой или аксиомами» в аксиоматической системе или (ii) просто определением, которое «идентифицировало» два или более предложений или (iii) эмпирической гипотезой, которую следует проверить на естественных событиях или (iv) или просто предложением ради аргумента (то есть «тезиса»).

1930—1952

В ходе изучения проблемы Чёрч и его ученик Стивен Клини ввели понятие λ-определимых функций, и они смогли доказать, что несколько больших классов функций, часто встречающихся в теории чисел, были λ-определимыми. Дискуссия началась, когда Чёрч предложил Курту Гёделю определить «эффективно вычислимые» функции как λ-определимые функции. Однако Гёдель не был убеждён и назвал это предложение «полностью неудовлетворительным». Тем не менее Гёдель в переписке с Чёрчем предложил аксиоматизировать понятие «эффективной вычислимости»; В письме Клини и Чёрчу он сообщил, что

Его единственная идея в то время состоит в том, что может быть возможно задать термин эффективной вычислимости как неопределённого понятия в виде набора аксиом, которые бы воплощали общепринятые свойства этого понятия и затем что-то делать на этой основе.

—

Но Гёдель не дал никаких дальнейших указаний. Он предложил только рекурсию, модифицированную предложением Эрбрана, о чём Гёдель подробно написал на своих лекциях в 1934 году в Принстоне Нью-Джерси (Клини и расшифровали записи). Но он не думал, что две идеи могут быть удовлетворительно определены «кроме эвристически».

Затем необходимо было идентифицировать и доказать эквивалентность двух понятий эффективной вычислимости. Оснащённый λ-исчислением и «общей» рекурсией, Стивен Клини с помощью Чёрча и Россера подготовили доказательства (1933, 1935), чтобы показать, что эти два исчисления эквивалентны. Чёрч впоследствии изменил свои методы, включив использование рекурсии Эрбрана — Гёделя, а затем доказал (1936), что проблема разрешения неразрешима: нет обобщённого алгоритма, который может определить, имеет ли корректно сформулированная формула «нормальную форму».

Много лет спустя в письме к Дэвису (около 1965 года) Гёдель сказал, что «он был во время этих [1934] лекций, совсем не убеждён в том, что его концепция рекурсии включает все возможные рекурсии». К 1963 году Гёдель отказался от рекурсии Эрбрана — Гёделя и λ-исчисления в пользу машины Тьюринга как определения «алгоритма» или «механической процедуры» или «формальной системы».

В конце 1936 года статья Алана Тьюринга (также доказывающая, что проблема разрешения неразрешима) была озвучена в устной форме, но ещё не появилась в печати. С другой стороны, появилась статья Эмиля Поста 1936 года и была сертифицирована независимо от работы Тьюринга. Пост категорически не согласился с Чёрчевским «отождествлением» (identification) эффективной вычислимости c λ-исчислением и рекурсией, заявив:

На самом деле в работе Чёрча и других это отождествление излагается значительно сильнее рабочей гипотезы. Но маскировка этого отождествления под определение … ослепляет нас необходимостью постоянной проверки.

—

Скорее, он считал понятие «эффективной вычислимости» просто «рабочей гипотезой», которая могла бы привести индуктивным умозаключением к «естественному закону», а не «определению или аксиоме». Эта идея была «резко» подвергнута критике со стороны Чёрча.

Таким образом, Пост в своей статье 1936 года также отклонял предложение Курта Гёделя Чёрчу в 1934—1935 годах о том, что тезис может быть выражен как аксиома или множество аксиом.

Тьюринг добавляет ещё одно определение, Россер приравнивает все три : за короткое время появилась статья (1936-37) Тьюринга «О вычислимых числах и применение к проблеме разрешения». В ней он задал понятие «эффективной вычислимости» по-другому, с введением его а-машин (теперь они известны как абстрактная вычислительная модель машины Тьюринга). И в доказательном эскизе, добавленном как «Приложение» к его статье 1936-37, Тьюринг показал, что классы функций, определяемые λ-исчислением и машинами Тьюринга, совпадают. Чёрч быстро понял, насколько убедительным был анализ Тьюринга. В своем обзоре работы Тьюринга он ясно дал понять, что понятие Тьюринга сделало «отождествление с эффективностью в обычном (не явно определённом) смысле, очевидном сразу».

Через несколько лет (1939) Тьюринг предложил, как это сделали Чёрч и Клини перед ним, что его формальное определение механического вычислительного агента было правильным. Таким образом, к 1939 году и Чёрч (1934), и Тьюринг (1939) индивидуально предложили, чтобы их «формальные системы» были определениями «эффективной вычислимости»; а не сформулировали свои утверждения как тезисы.

Россер (1939) формально отождествил три понятия как определения:

«Все три определения эквивалентны, поэтому не имеет значения, какое из них используется».

Клини предлагает тезис Чёрча : здесь оставлено явное выражение «тезис», использованное Клини. В своей статье 1943 года «Рекурсивные предикаты и квантификаторы» Клин предложил свой «ТЕЗИС I»:

"Этот эвристический факт [общерекурсивные функции эффективно рассчитываются] … привел Чёрча к формулировке следующего тезиса (22). Тот же тезис неявен в описании Тьюринга вычислительных машин (23).
"ТЕЗИС I. Всякая эффективно вычисляемая функция (эффективно разрешимый предикат) является обще рекурсивной [курсив Клини]
«Поскольку точное математическое определение термина, эффективно вычисляемый (эффективно разрешимый), было бы желательным, мы можем принять этот тезис … как определение этого термина …»
(22) ссылка на Чёрча 1936
(23) ссылка Тьюринга 1936-7

Клини далее отмечает, что:

«… тезис имеет характер гипотезы — пункт, отмеченный Постом и Тьюрингом (24). Если мы рассмотрим тезис и его обратное как определение, то гипотеза является гипотезой о применении математической теории, полученной из этого определения. Для принятия этой гипотезы, как мы предложили, есть довольно убедительные основания»
(24) ссылка на Post 1936 of Post and Church’s Formal definitions in the theory of ordinal numbers, Fund. Math. vol 28 (1936) pp.11-21 (see ref. #2, Davis 1965:286).

Примечания

  1. Математическая логика, 1973, с. 280.
  2. Church, Alonzo. An Unsolvable Problem of Elementary Number Theory (англ.) // American Journal of Mathematics : journal. — 1936. — Vol. 58, no. 58. — P. 345—363. — doi:10.2307/2371045. — JSTOR 2371045.
  3. Church, Alonzo. A Note on the Entscheidungsproblem (неопр.) // [англ.]. — 1936. — № 1. — С. 40—41.
  4. Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem (англ.) // Proceedings of the London Mathematical Society — London Mathematical Society, 1937. — Vol. s2-42, Iss. 1. — P. 230—265. — ISSN 0024-6115; 1460-244X; 0024-6115 — doi:10.1112/PLMS/S2-42.1.230
  5. Turing A. M. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction (англ.) // Proceedings of the London Mathematical Society — London Mathematical Society, 1938. — Vol. s2-43, Iss. 6. — P. 544—546. — ISSN 0024-6115; 1460-244X; 0024-6115 — doi:10.1112/PLMS/S2-43.6.544
  6. Жар холодных чисел и пафос бесстрастной логики, 1977, с. 143.
  7. Алгоритмы и рекурсивные функции, 1986, с. 12.
  8. Новый ум короля, 2003, с. 55.
  9. Комментарий Девиса к «Черч 1936 An Unsolvable Problem of Elementary Number Theory» в Davis 1965:88. Чёрч использовал слова «эффективная вычисляемость»(«effective calculability») на странице 100ff.
  10. cf Smith (July 11, 2007) Church’s Thesis after 70 Years at http://www.logicmatters.net/resources/pdfs/CTT.pdf Архивная копия от 13 августа 2021 на Wayback Machine
  11. cf footnote 3 in Church, 1936a An Unsolvable Problem of Elementary Number Theory in Davis 1965:89
  12. Dawson 1997:99.[уточнить источник]
  13. Sieg 1997:160.
  14. Sieg 1997:160 цитирует письмо, написанное в 1935 Чёрчем для Клини, cf Footnote 3 in Gödel 1934 in Davis 1965:44.
  15. cf Church 1936 in Davis 1965:105ff
  16. Davis’s commentary before Gödel 1934 in Davis 1965:40
  17. Детальное обсуждение гёделевского использования тьюринговых машин как моделей вычисления см. Shagrir. Goedel on Turing on Computability (PDF) (2006). Дата обращения: 8 февраля 2016. Архивировано 17 декабря 2015 года.
  18. Turing, 1937
  19. cf. Editor’s footnote to Post 1936 Finite Combinatory Process. Formulation I. at Davis 1965:289
  20. Post 1936 in Davis 1965:291, footnote 8.
  21. Post 1936 in Davis 1952:291
  22. Sieg 1997:171 and 176-7
  23. Turing 1936-7 in Davis 1965:263ff
  24. Church, 1937
  25. Turing 1939 in Davis:160
  26. cf. Church 1934 in Davis 1965:100, also Turing 1939 in Davis 1965:160
  27. Устаревшее использование Клини и другими чтобы отличать Гёделевский (1931) «rekursiv» (несколькими годами позже названный примитивной рекурсией by (cf Gandy 1994:68)) от рекурсии Эрбрана — Гёделя (1934) то есть примитивной рекурсии с дополнительным μ-оператором, называемой сегодня μ-рекурсией, или проще, «рекурсией».
  28. Kleene, 1943 in Davis 1965:274

Литература

  • Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
  • Бирюков Б. В., Тростников В. Н. Жар холодных чисел и пафос бесстрастной логики. — М.: Знание, 1977. — 192 с.
  • Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 368 с.
  • Пенроуз Р. Новый ум короля. — М.: Едиториал УРСС, 2003. — 384 с.
  • Church, Alonzo. An Unsolvable Problem of Elementary Number Theory (англ.) // American Journal of Mathematics : journal. — 1936a. — April (vol. 58, no. 2). — P. 345—363. — doi:10.2307/2371045. — JSTOR 2371045.
  • The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. — New York : Raven Press, 1965. Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
  • Church's Thesis and the Principles for Mechanisms // The Kleene Symposium / H. J. Barwise ; H. J. Keisler ; K. Kunen. — North-Holland Publishing Company, 1980. — P. 123–148.
  • Gandy, Robin. The universal Turing Machine: A Half-Century Survey. — New York : Wien Springer–Verlag, 1994. — P. 51ff. — ISBN 978-3-211-82637-9.
  • Church, Alonzo. Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (англ.) // Journal of Symbolic Logic : journal. — 1937. — March (vol. 2, no. 1). — P. 42—43. — doi:10.2307/2268810.
  • Kleene, Stephen Cole. Recursive Predicates and Quantifiers (англ.) // American Mathematical Society Transactions. — 1943. — Vol. 54, no. 1. — P. 41—73. — doi:10.2307/1990131. — JSTOR 1990131.

Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Тезис Чёрча, Что такое Тезис Чёрча? Что означает Тезис Чёрча?

Te zis Chyorcha Tyu ringa logiko matematicheskij princip ustanavlivayushij ekvivalentnost mezhdu intuitivnym ponyatiem algoritmicheskoj vychislimosti i strogo formalizovannymi ponyatiyami chastichno rekursivnoj funkcii i funkcii vychislimoj na mashine Tyuringa V svyazi s intuitivnostyu ishodnogo ponyatiya algoritmicheskoj vychislimosti dannyj tezis nosit harakter suzhdeniya ob etom ponyatii i ego nevozmozhno strogo dokazat ili oprovergnut Pered tochnym opredeleniem vychislimoj funkcii matematiki chasto ispolzovali neoficialnyj termin effektivno vychislimyj dlya opisaniya funkcij kotorye mozhno vychislit s pomoshyu bumazhno karandashnyh metodov Tezis byl vyskazan Alonzo Chyorchem i Alanom Tyuringom v seredine 1930 h godov Sushestvenen dlya mnogih oblastej nauki i filosofii nauki v tom chisle dlya matematicheskoj logiki teorii dokazatelstv informatiki kibernetiki FormulirovkiV terminah teorii rekursii tezis formuliruetsya kak tochnoe opisanie intuitivnogo ponyatiya vychislimosti klassom obsherekursivnyh funkcij V etoj formulirovke chasto upominaetsya kak prosto tezis Chyorcha Bolee obshaya formulirovka byla dana Stivenom Klini soglasno kotoroj vse chastichnye to est ne obyazatelno opredelyonnye dlya vseh znachenij argumentov funkcii vychislimye posredstvom algoritmov yavlyayutsya chastichno rekursivnymi V terminah vychislimosti po Tyuringu tezis glasit chto dlya lyuboj algoritmicheski vychislimoj funkcii sushestvuet vychislyayushaya eyo znacheniya mashina Tyuringa Inogda v takoj formulirovke figuriruet kak tezis Tyuringa Vvidu togo chto klassy chastichno vychislimyh po Tyuringu i chastichno rekursivnyh funkcij sovpadayut utverzhdenie obedinyayut v edinyj tezis Chyorcha Tyuringa Pozdnee byli sformulirovany drugie prakticheskie varianty utverzhdeniya fizicheskij tezis Chyorcha Tyuringa lyubaya funkciya kotoraya mozhet byt vychislena fizicheskim ustrojstvom mozhet byt vychislena mashinoj Tyuringa silnyj tezis Chyorcha Tyuringa tezis Chyorcha Tyuringa Dojcha lyuboj konechnyj fizicheskij process ne ispolzuyushij apparat svyazannyj s nepreryvnostyu i beskonechnostyu mozhet byt vychislen fizicheskim ustrojstvom IstoriyaOdnoj iz vazhnyh problem dlya logikov v 1930 h godah byla problema razresheniya sushestvuet li mehanicheskaya procedura dlya otdeleniya matematicheskih istin ot matematicheskih lozhnostej Eta zadacha trebovala chtoby ponyatie algoritm ili effektivnaya vychislimost bylo zakrepleno po krajnej mere chtoby pristupit k zadache S samogo nachala i po sej den po sostoyaniyu na 2007 god prodolzhayutsya debaty bylo li ponyatie effektivnoj vychislimosti i aksiomoj ili aksiomami v aksiomaticheskoj sisteme ili ii prosto opredeleniem kotoroe identificirovalo dva ili bolee predlozhenij ili iii empiricheskoj gipotezoj kotoruyu sleduet proverit na estestvennyh sobytiyah ili iv ili prosto predlozheniem radi argumenta to est tezisa 1930 1952 V hode izucheniya problemy Chyorch i ego uchenik Stiven Klini vveli ponyatie l opredelimyh funkcij i oni smogli dokazat chto neskolko bolshih klassov funkcij chasto vstrechayushihsya v teorii chisel byli l opredelimymi Diskussiya nachalas kogda Chyorch predlozhil Kurtu Gyodelyu opredelit effektivno vychislimye funkcii kak l opredelimye funkcii Odnako Gyodel ne byl ubezhdyon i nazval eto predlozhenie polnostyu neudovletvoritelnym Tem ne menee Gyodel v perepiske s Chyorchem predlozhil aksiomatizirovat ponyatie effektivnoj vychislimosti V pisme Klini i Chyorchu on soobshil chto Ego edinstvennaya ideya v to vremya sostoit v tom chto mozhet byt vozmozhno zadat termin effektivnoj vychislimosti kak neopredelyonnogo ponyatiya v vide nabora aksiom kotorye by voploshali obsheprinyatye svojstva etogo ponyatiya i zatem chto to delat na etoj osnove No Gyodel ne dal nikakih dalnejshih ukazanij On predlozhil tolko rekursiyu modificirovannuyu predlozheniem Erbrana o chyom Gyodel podrobno napisal na svoih lekciyah v 1934 godu v Prinstone Nyu Dzhersi Klini i rasshifrovali zapisi No on ne dumal chto dve idei mogut byt udovletvoritelno opredeleny krome evristicheski Zatem neobhodimo bylo identificirovat i dokazat ekvivalentnost dvuh ponyatij effektivnoj vychislimosti Osnashyonnyj l ischisleniem i obshej rekursiej Stiven Klini s pomoshyu Chyorcha i Rossera podgotovili dokazatelstva 1933 1935 chtoby pokazat chto eti dva ischisleniya ekvivalentny Chyorch vposledstvii izmenil svoi metody vklyuchiv ispolzovanie rekursii Erbrana Gyodelya a zatem dokazal 1936 chto problema razresheniya nerazreshima net obobshyonnogo algoritma kotoryj mozhet opredelit imeet li korrektno sformulirovannaya formula normalnuyu formu Mnogo let spustya v pisme k Devisu okolo 1965 goda Gyodel skazal chto on byl vo vremya etih 1934 lekcij sovsem ne ubezhdyon v tom chto ego koncepciya rekursii vklyuchaet vse vozmozhnye rekursii K 1963 godu Gyodel otkazalsya ot rekursii Erbrana Gyodelya i l ischisleniya v polzu mashiny Tyuringa kak opredeleniya algoritma ili mehanicheskoj procedury ili formalnoj sistemy V konce 1936 goda statya Alana Tyuringa takzhe dokazyvayushaya chto problema razresheniya nerazreshima byla ozvuchena v ustnoj forme no eshyo ne poyavilas v pechati S drugoj storony poyavilas statya Emilya Posta 1936 goda i byla sertificirovana nezavisimo ot raboty Tyuringa Post kategoricheski ne soglasilsya s Chyorchevskim otozhdestvleniem identification effektivnoj vychislimosti c l ischisleniem i rekursiej zayaviv Na samom dele v rabote Chyorcha i drugih eto otozhdestvlenie izlagaetsya znachitelno silnee rabochej gipotezy No maskirovka etogo otozhdestvleniya pod opredelenie osleplyaet nas neobhodimostyu postoyannoj proverki Skoree on schital ponyatie effektivnoj vychislimosti prosto rabochej gipotezoj kotoraya mogla by privesti induktivnym umozaklyucheniem k estestvennomu zakonu a ne opredeleniyu ili aksiome Eta ideya byla rezko podvergnuta kritike so storony Chyorcha Takim obrazom Post v svoej state 1936 goda takzhe otklonyal predlozhenie Kurta Gyodelya Chyorchu v 1934 1935 godah o tom chto tezis mozhet byt vyrazhen kak aksioma ili mnozhestvo aksiom Tyuring dobavlyaet eshyo odno opredelenie Rosser priravnivaet vse tri za korotkoe vremya poyavilas statya 1936 37 Tyuringa O vychislimyh chislah i primenenie k probleme razresheniya V nej on zadal ponyatie effektivnoj vychislimosti po drugomu s vvedeniem ego a mashin teper oni izvestny kak abstraktnaya vychislitelnaya model mashiny Tyuringa I v dokazatelnom eskize dobavlennom kak Prilozhenie k ego state 1936 37 Tyuring pokazal chto klassy funkcij opredelyaemye l ischisleniem i mashinami Tyuringa sovpadayut Chyorch bystro ponyal naskolko ubeditelnym byl analiz Tyuringa V svoem obzore raboty Tyuringa on yasno dal ponyat chto ponyatie Tyuringa sdelalo otozhdestvlenie s effektivnostyu v obychnom ne yavno opredelyonnom smysle ochevidnom srazu Cherez neskolko let 1939 Tyuring predlozhil kak eto sdelali Chyorch i Klini pered nim chto ego formalnoe opredelenie mehanicheskogo vychislitelnogo agenta bylo pravilnym Takim obrazom k 1939 godu i Chyorch 1934 i Tyuring 1939 individualno predlozhili chtoby ih formalnye sistemy byli opredeleniyami effektivnoj vychislimosti a ne sformulirovali svoi utverzhdeniya kak tezisy Rosser 1939 formalno otozhdestvil tri ponyatiya kak opredeleniya Vse tri opredeleniya ekvivalentny poetomu ne imeet znacheniya kakoe iz nih ispolzuetsya Klini predlagaet tezis Chyorcha zdes ostavleno yavnoe vyrazhenie tezis ispolzovannoe Klini V svoej state 1943 goda Rekursivnye predikaty i kvantifikatory Klin predlozhil svoj TEZIS I Etot evristicheskij fakt obsherekursivnye funkcii effektivno rasschityvayutsya privel Chyorcha k formulirovke sleduyushego tezisa 22 Tot zhe tezis neyaven v opisanii Tyuringa vychislitelnyh mashin 23 TEZIS I Vsyakaya effektivno vychislyaemaya funkciya effektivno razreshimyj predikat yavlyaetsya obshe rekursivnoj kursiv Klini dd Poskolku tochnoe matematicheskoe opredelenie termina effektivno vychislyaemyj effektivno razreshimyj bylo by zhelatelnym my mozhem prinyat etot tezis kak opredelenie etogo termina 22 ssylka na Chyorcha 1936 23 ssylka Tyuringa 1936 7 dd Klini dalee otmechaet chto tezis imeet harakter gipotezy punkt otmechennyj Postom i Tyuringom 24 Esli my rassmotrim tezis i ego obratnoe kak opredelenie to gipoteza yavlyaetsya gipotezoj o primenenii matematicheskoj teorii poluchennoj iz etogo opredeleniya Dlya prinyatiya etoj gipotezy kak my predlozhili est dovolno ubeditelnye osnovaniya 24 ssylka na Post 1936 of Post and Church s Formal definitions in the theory of ordinal numbers Fund Math vol 28 1936 pp 11 21 see ref 2 Davis 1965 286 dd dd PrimechaniyaMatematicheskaya logika 1973 s 280 Church Alonzo An Unsolvable Problem of Elementary Number Theory angl American Journal of Mathematics journal 1936 Vol 58 no 58 P 345 363 doi 10 2307 2371045 JSTOR 2371045 Church Alonzo A Note on the Entscheidungsproblem neopr angl 1936 1 S 40 41 Turing A On Computable Numbers with an Application to the Entscheidungsproblem angl Proceedings of the London Mathematical Society London Mathematical Society 1937 Vol s2 42 Iss 1 P 230 265 ISSN 0024 6115 1460 244X 0024 6115 doi 10 1112 PLMS S2 42 1 230 Turing A M On Computable Numbers with an Application to the Entscheidungsproblem A Correction angl Proceedings of the London Mathematical Society London Mathematical Society 1938 Vol s2 43 Iss 6 P 544 546 ISSN 0024 6115 1460 244X 0024 6115 doi 10 1112 PLMS S2 43 6 544 Zhar holodnyh chisel i pafos besstrastnoj logiki 1977 s 143 Algoritmy i rekursivnye funkcii 1986 s 12 Novyj um korolya 2003 s 55 Kommentarij Devisa k Cherch 1936 An Unsolvable Problem of Elementary Number Theory v Davis 1965 88 Chyorch ispolzoval slova effektivnaya vychislyaemost effective calculability na stranice 100ff cf Smith July 11 2007 Church s Thesis after 70 Years at http www logicmatters net resources pdfs CTT pdf Arhivnaya kopiya ot 13 avgusta 2021 na Wayback Machine cf footnote 3 in Church 1936a An Unsolvable Problem of Elementary Number Theory in Davis 1965 89 Dawson 1997 99 utochnit istochnik Sieg 1997 160 Sieg 1997 160 citiruet pismo napisannoe v 1935 Chyorchem dlya Klini cf Footnote 3 in Godel 1934 in Davis 1965 44 cf Church 1936 in Davis 1965 105ff Davis s commentary before Godel 1934 in Davis 1965 40 Detalnoe obsuzhdenie gyodelevskogo ispolzovaniya tyuringovyh mashin kak modelej vychisleniya sm Shagrir Goedel on Turing on Computability neopr PDF 2006 Data obrasheniya 8 fevralya 2016 Arhivirovano 17 dekabrya 2015 goda Turing 1937 cf Editor s footnote to Post 1936 Finite Combinatory Process Formulation I at Davis 1965 289 Post 1936 in Davis 1965 291 footnote 8 Post 1936 in Davis 1952 291 Sieg 1997 171 and 176 7 Turing 1936 7 in Davis 1965 263ff Church 1937 Turing 1939 in Davis 160 cf Church 1934 in Davis 1965 100 also Turing 1939 in Davis 1965 160 Ustarevshee ispolzovanie Klini i drugimi chtoby otlichat Gyodelevskij 1931 rekursiv neskolkimi godami pozzhe nazvannyj primitivnoj rekursiej by cf Gandy 1994 68 ot rekursii Erbrana Gyodelya 1934 to est primitivnoj rekursii s dopolnitelnym m operatorom nazyvaemoj segodnya m rekursiej ili proshe rekursiej Kleene 1943 in Davis 1965 274LiteraturaKlini S K Matematicheskaya logika M Mir 1973 480 s Biryukov B V Trostnikov V N Zhar holodnyh chisel i pafos besstrastnoj logiki M Znanie 1977 192 s Malcev A I Algoritmy i rekursivnye funkcii M Nauka 1986 368 s Penrouz R Novyj um korolya M Editorial URSS 2003 384 s Church Alonzo An Unsolvable Problem of Elementary Number Theory angl American Journal of Mathematics journal 1936a April vol 58 no 2 P 345 363 doi 10 2307 2371045 JSTOR 2371045 The Undecidable Basic Papers on Undecidable Propositions Unsolvable Problems And Computable Functions New York Raven Press 1965 Includes original papers by Godel Church Turing Rosser Kleene and Post mentioned in this section Church s Thesis and the Principles for Mechanisms The Kleene Symposium H J Barwise H J Keisler K Kunen North Holland Publishing Company 1980 P 123 148 Gandy Robin The universal Turing Machine A Half Century Survey New York Wien Springer Verlag 1994 P 51ff ISBN 978 3 211 82637 9 Church Alonzo Review A M Turing On Computable Numbers with an Application to the Entscheidungsproblem angl Journal of Symbolic Logic journal 1937 March vol 2 no 1 P 42 43 doi 10 2307 2268810 Kleene Stephen Cole Recursive Predicates and Quantifiers angl American Mathematical Society Transactions 1943 Vol 54 no 1 P 41 73 doi 10 2307 1990131 JSTOR 1990131

21 Июл, 2025 / 06:49
NiNa.Az

NiNa.Az

NiNa.Az - Абсолютно бесплатная система, которая делится для вас информацией и контентом 24 часа в сутки.
Взгляните
Закрыто
© 2019 NiNa.Az - Все права защищены.
Авторские права: Dadash Mammadov