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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

Література[ред.ред. код]

Підручники проміжного рівня[ред.ред. код]

Просунуті тексти[ред.ред. код]

  • 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, MR1739227, ISSN 1073-2780 
  • T. Slaman and W. H. Woodin, 1986. «Definability in the Turing degreesIllinois 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.

Посилання[ред.ред. код]