Теорія обчислюваності

Теорія обчислюваності, також відома як теорія рекурсії, являє собою галузь математичної логіки, що заснована у 30-х роках XX ст. при вивченні обчислюваних функцій та степенів Тюрінга. Згодом галузь включила вивчення узагальненої обчислюваності та визначуваності. У цих областях, теорія рекурсій перетинається з теорією доведень та ефективно дескриптивною теорією множин.

Назва теорія рекурсії частіше використовується в західних роботах з цієї теми, і пов'язана з тим, що клас обчислюваних функцій збігається з класом рекурсивних функцій.

Основні питання теорії рекурсій є «Що значить для функції натуральних аргументів бути обчислюваною?» і «Чи можуть необчислювані функції бути класифіковані у ієрархію, виходячи з їх рівня необчислюваності?». Відповіді на ці питання привели до багатої теорії, що все ще активно досліджується.

Злічені і не злічені множини

Теорія рекурсії отримала свій початок розвитку в 1930-их, із робіт які започаткували Курт Гедель, Алонзо Черч, Роза Петер, Алан Тюрінг, Стівен Коул Кліні, і Еміль Пост.[1][2].

Фундаментальні результати які отримали дослідники встановили обчислюваність Тюрінга, що стало правильною формалізацією неформальної ідеї про ефективний розрахунок. Ці результати дали змогу Стівену Кліні (1952) закарбувати два імені у вигляді «Тез Черча» (Kleene 1952:300) і «Тез Тюрінга» (Kleene 1952:376). Сьогодні їх часто розглядають як єдину гіпотезу, Тезу Черча–Тюринга, яка стверджує, що будь-яка функція, яка є обчислювана за допомогою алгоритму є обчислюваною функцією.

Із появою визначення ефективності обчислення з'явилися перші докази того, що в математиці є задачі, які не можливо ефективно вирішити. Черч (1936a, 1936b) і Тюрінг (1936), натхнені методами, які застосував Гедель (1931) аби довести його теореми про неповноту, незалежно показали, що задача розв'язності не може бути ефективно вирішена. В цьому результаті було показано, що не існує алгоритмічної процедури яка б могла коректно розв'язати чи є довільні математичні припущення вірними чи ні.

Примітки
  1. Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
  2. Soare, Robert Irving (22 грудня 2011). Computability Theory and Applications: The Art of Classical Computability. Department of Mathematics. University of Chicago. Процитовано 23 серпня 2017.

Література

Підручники проміжного рівня
  • S. B. Cooper, 2004. Computability Theory, Chapman & Hall/CRC. ISBN 1-58488-237-9
  • N. Cutland, 1980. Computability, An introduction to recursive function theory, Cambridge University Press. ISBN 0-521-29465-7
  • Y. Matiyasevich, 1993. Hilbert's Tenth Problem, MIT Press. ISBN 0-262-13295-8

Просунуті тексти
  • S. Jain, D. Osherson, J. Royer and A. Sharma, 1999. Systems that learn, an introduction to learning theory, second edition, Bradford Book. ISBN 0-262-10077-0
  • S. Kleene, 1952. Introduction to Metamathematics, North-Holland (11th printing; 6th printing added comments). ISBN 0-7204-2103-9
  • M. Lerman, 1983. Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 3-540-12155-2.
  • Andre Nies, 2009. Computability and Randomness, Oxford University Press, 447 pages. ISBN 978-0-19-923076-1.
  • P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7
  • P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X
  • H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
  • G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
  • S. G. Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag. ISBN 3-540-64882-8
  • R. I. Soare, 1987. Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 0-387-15299-7.

Оглядові роботи та збірники
  • K. Ambos-Spies and P. Fejer, 2006. «Degrees of Unsolvability.» Unpublished preprint.
  • H. Enderton, 1977. «Elements of Recursion Theory.» Handbook of Mathematical Logic, edited by J. Barwise, North-Holland (1977), pp. 527—566. ISBN 0-7204-2285-X
  • Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, 1998. Handbook of Recursive Mathematics, North-Holland (1998). ISBN 0-7204-2285-X
  • M. Fairtlough and S. Wainer, 1998. «Hierarchies of Provably Recursive Functions». In Handbook of Proof Theory, edited by S. Buss, Elsevier (1998).
  • R. I. Soare, 1996. Computability and recursion, Bulletin of Symbolic Logic v. 2 pp. 284-321.

Дослідницькі роботи та збірники
  • Burgin, M. and Klinger, A. «Experience, Generations, and Limits in Machine Learning.» Theoretical Computer Science v. 317, No. 1/3, 2004, pp. 71-91
  • A. Church, 1936a. «An unsolvable problem of elementary number theory.» American Journal of Mathematics v. 58, pp. 345-363. Reprinted in «The Undecidable», M. Davis ed., 1965.
  • A. Church, 1936b. «A note on the Entscheidungsproblem.» Journal of Symbolic Logic v. 1, n. 1, and v. 3, n. 3. Reprinted in «The Undecidable», M. Davis ed., 1965.
  • M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9
  • R. M. Friedberg, 1958. «Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition.» The Journal of Symbolic Logic, v. 23, pp. 309-316.
  • E. M. Gold, 1967. «Language identification in the limit». Information and Control, volume 10, pages 447—474.
  • L. Harrington and R. I. Soare, 1991. «Post's Program and incomplete recursively enumerable sets», Proceedings of the National Academy of Sciences of the USA, volume 88, pages 10242—10246.
  • C. Jockusch jr, «Semirecursive sets and positive reducibility», Trans. Amer. Math. Soc. 137 (1968) 420—436
  • S. C. Kleene and E. L. Post, 1954. «The upper semi-lattice of degrees of recursive unsolvability.» Annals of Mathematics v. 2 n. 59, 379—407.
  • J. Myhill, 1956. «The lattice of recursively enumerable sets.» The Journal of Symbolic Logic, v. 21, pp. 215-220.
  • E. Post, 1944, «Recursively enumerable sets of positive integers and their decision problems», Bulletin of the American Mathematical Society, volume 50, pages 284—316.
  • E. Post, 1947. «Recursive unsolvability of a problem of Thue.» Journal of Symbolic Logic v. 12, pp. 1—11. Reprinted in «The Undecidable», M. Davis ed., 1965.
  • Shore, Richard A.; Slaman, Theodore A. (1999). Defining the Turing jump. Mathematical Research Letters 6: 711–722. ISSN 1073-2780. MR1739227.
  • T. Slaman and W. H. Woodin, 1986. «Definability in the Turing degrees.» Illinois J. Math. v. 30 n. 2, pp. 320—334.
  • R. I. Soare, 1974. «Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets.» Annals of Mathematics, v. 100, pp. 80-120.
  • A. Turing, 1937. «On computable numbers, with an application to the Entscheidungsproblem.» Proceedings of the London Mathematics Society, ser. 2 v. 42, pp. 230-265. Corrections ibid. v. 43 (1937) pp. 544-546. Reprinted in «The Undecidable», M. Davis ed., 1965. PDF from comlab.ox.ac.uk
  • A. Turing, 1939. «Systems of logic based on ordinals.» Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161-228. Reprinted in «The Undecidable», M. Davis ed., 1965.

Див. також

Посилання


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.