Diferencia entre revisiones de «Teoría de la computabilidad»

Contenido eliminado Contenido añadido
agregada bibliografia
Línea 58:
una [[máquina oráculo]] que utiliza una [[caja negra (sistemas)|caja negra]] que puede calcular una función particular que no es calculable con una máquina de Turing. La fuerza de cómputo de una máquina oráculo viene descrita por su [[grado de Turing]]. La [[teoría de cómputos reales]] estudia máquinas con precisión absoluta en los números reales. Dentro de esta teoría, es posible demostrar afirmaciones interesantes, tales como «el complemento de un [[conjunto de Mandelbrot]] es solo parcialmente decidible».
 
== Bibliografía ==
[[Categoría:Computabilidad| ]]
:* [[S. Barry Cooper|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
:* [[Yuri Matiyasevich|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
:* [[Stephen Kleene|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.
:* [[Piergiorgio Odifreddi|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
:* [[Hartley Rogers, Jr.|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. "[http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf 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.
:* {{Citation | last1=Shore | first1=Richard A. | last2=Slaman | first2=Theodore A. | author2-link=Theodore Slaman |title=Defining the Turing jump |url=http://www.math.cornell.edu/~shore/papers/pdf/jumpmrl.pdf | mr=1739227 | year=1999 | journal=[[Mathematical Research Letters]] | issn=1073-2780 | volume=6 | pages=711–722}}
:* T. Slaman and W. H. Woodin, 1986. "[http://citeseer.ist.psu.edu/cache/papers/cs/11492/http:zSzzSzwww.math.berkeley.eduzSz~slamanzSzpaperszSzslaman-woodin.pdf/slaman86definability.pdf 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. [http://web.comlab.ox.ac.uk/oucl/research/areas/ieg/e-library/sources/tp2-ie.pdf 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.
 
 
[[Categoría:Computabilidad| ]]
 
{{Bueno|ja}}