Teoría de la computabilidá

VEB Robotron Elektronik Dresden.

La Teoría de la computabilidad ye la parte de la computación qu'estudia los problemes de decisión que pueden ser resueltos con un algoritmu o equivalentemente cola llamada máquina de Turing. La teoría de la computabilidad interesar por cuatro preguntes:

• ¿Qué problemes puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a les máquines de Turing?
• ¿Qué problemes riquen máquines más poderoses?
• ¿Qué problemes riquen máquines menos poderoses?

La teoría de la complexidá computacional clasifica les funciones computables según l'usu que faen de diversos recursos en diversos tipos de máquina.

Conxuntos computables y non computables

• Esta obra remanez de la traducción de Computability theory de Wikipedia - inglés, concretamente d'de xineru de 2017 esta versión del parcial, espublizada polos sos editores baxo la Llicencia de documentación llibre de GNU y la Llicencia Creative Commons Atribución-CompartirIgual 3.0 Unported.

La teoría de la recursión aniciar na década de 1930, col trabayu de Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene y Emil Post.

Les resultancies fundamentales que llograron los investigadores estabilizaron el conceutu de función computable como la manera correuta de formalizar la idea sobre cálculos efectivos.

Estes resultancies llevaron a Stephen Kleene (1952) a acuñar dos nomes, "Tesis de Church" (Kleene 1952:300) y "Tesis de Turing" (Kleene 1952:376). Anguaño dambos considérense como una única hipótesis, la Tesis de Church-Turing, que establez que cualquier función que sía computable por un ciertu algoritmu ye una función computable. Anque nun principiu yera daqué un tanto escépticu, alredor del añu 1946, Gödel defendió esta tesis:

"Tarksi sorrayó na so llectura (y creo xustamente) la gran importancia del conceutu de recursividad xeneral (o computabilidad de Turing). Al mio pensar esta importancia deber en gran midida al fechu de que con esti conceutu, por fin consiguióse da-y una noción absoluta a una interesante noción epistemolóxica, esto ye, una que nun depende del formalismu escoyíu.*"(Gödel 1946 en Davis 1965:84).

Con una definición sobre cálculos efectivos apaecieron les primeres pruebes de qu'hai ciertos problemes nes matemátiques que nun pueden ser decidíos d'una manera eficaz. Church (1936p, 1936f) y Turing (1936), inspiraos poles téuniques usaes por Gödel (1931) pa probar les sos teoremas sobre la incompletitud, demostraron por separáu que nun ye posible decidir el Entscheidungsproblem d'una manera eficaz. Esta resultancia demostró que nun esiste un procedimientu algorítmico que pueda decidir de manera correuta si ciertes proposiciones matemátiques son verdaderes o non.

Munchos problemes nes matemátiques fueron demostraos ser indecidibles una vegada estableciéronse estos primeros exemplos. En 1947, Markov y Post publicaron por separáu los sos trabayos amosando que'l problema de les pallabres pa los semigrupos nun puede ser decidíu d'una manera eficaz. Ampliando esta resultancia, Pyotr Novikov y William Boone demostraron independientemente na década de 1950 que'l problema de les pallabres pa los semigrupos nun puede resolvese d'una manera efectiva: nun hai nengún procedimientu eficaz que, dada una pallabra nun grupu, decida si l'elementu representáu pola pallabra ye l'elementu identidá del grupu. En 1970, Yuri Matiyasevich demostró (usando los resultaos de Julia Robinson) el Teorema de Matiyasevich, que implica que'l décimu problema de Hilbert nun tien una solución eficaz; esti problema preguntaba si había o non un procedimientu por aciu el cual pudiera decidise si una ecuación diofántica sobre los númberos enteros tien una solución entera. La llista de problemes indecidibles contién exemplos adicionales sobre problemes ensin soluciones computables.

L'estudiu sobre qué construcciones matemátiques pueden ser llevaes a cabu d'una forma eficaz denominar dacuando matemática recursiva; El Handbook of Recursive Mathematics (Ershov et al. 1998) cubre munchos de los resultaos conocíes nesti campu.

Antecedentes

L'orixe de los modelos astractos de computación encuadrar nos años '30 ( primero qu'esistieren los ordenadores modernos), pal trabayu de los lóxicos Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabayos iniciales tuvieron una fonda influencia, tantu nel desenvolvimientu teóricu como n'abondosos aspeutos de la práutica de la computación; previendo inclusive la esistencia d'ordenadores de propósitu xeneral, la posibilidá d'interpretar programes, la dualidá ente software y hardware, y la representación de llinguaxes por estructures formales basaos en regles de producción.

El puntu inicial d'estos primeros trabayos fueron les cuestiones fundamentales que David Hilbert formuló en 1900, mientres l'intre d'un congresu internacional.

Lo que Hilbert pretendía yera crear un sistema matemáticu formal completu y consistente nel cual toles aseveraciones fueren plantegaes con precisión. La so intención yera atopar un algoritmu que determinara la verdá o falsedá de cualquier proposición nel sistema formal. Al problema en cuestión denominóse-y Entscheidungsproblem. En casu de que Hilbert cumpliera'l so oxetivu, cualquier problema bien definíu resolveríase a cencielles al executar dichu algoritmu.

Pero fueron otros los que por aciu una serie d'investigaciones amosaron qu'esto nun yera posible. En contra d'esta idea K. Gödel sacó a la lluz el so conocíu Primer Teorema de Incompletitud. Este vien espresar que tou sistema de primer orde consistente que contenga los teoremas de l'aritmética y que'l so conxuntu d'axomes sía recursivo nun ye completu. Gödel construyó una fórmula que ye satisfactoria pero que nun puede ser probada nel sistema. De resultes, nun ye posible atopar el sistema formal deseyáu por Hilbert nel marcu de la lóxica de primer orde, sacantes que se tome un conxuntu non recursivo d'axomes.

Una posterior versión, que resulta más xeneral, del teorema de incompletitud de Gödel, indica que nengún sistema deductivu que contenga los teoremas de l'aritmética, y colos axomes recursivamente enumerables puede ser consistente y completu al empar. Esto fai pensar, a nivel intuitivu, que nun va a ser posible definir un sistema formal.

¿Qué problemes puede resolver una máquina de Turing?

Non tolos problemes pueden ser resueltos. Un problema indecidible ye unu que nun puede ser resueltu con un algoritmu entá si disponer d'espaciu y tiempu ilimitáu. Anguaño conócense munchos problemes indecidibles, como por casu:

• El Entscheidungsproblem (problema de decisión n'alemán) que se define como: Dada una frase del cálculu de predicaos de primer orde, decidir si ella ye un teorema. Church y Turing demostraron independientemente qu'esti problema ye indecidible (ver Tesis de Church-Turing).
• El Problema de la parada, que se define asina: Dau un programa y la so entrada, decidir si esi programa va terminar pa esa entrada o si va correr indefinidamente. Turing demostró que se trata d'un problema indecidible.
• Un númberu computable ye un númberu real que puede ser averáu por un algoritmu con un nivel d'exactitú arbitrariu. Turing demostró que casi tolos númberos nun son computables. Por casu, la Constante de Chaitin nun ye computable anque sí que ta bien definida.

¿Qué otros formalismos equivalen a les máquines de Turing?

Los llinguaxes formales que son aceptaos por una máquina de Turing son esautamente aquellos que pueden ser xeneraos por una gramática formal. El cálculo Lambda ye una forma de definir funciones. Les funciones que pueden ser computaes col cálculu Lambda son esautamente aquelles que pueden ser computaes con una máquina de Turing. Estos trés formalismos, les máquines de Turing, los llinguaxes formales y el cálculu Lambda son formalismos bien disímiles y fueron desenvueltos por distintes persones. Sicasí, toos ellos son equivalentes y tienen el mesmu poder d'espresión. Xeneralmente tómase esta notable coincidencia como evidencia de que la tesis de Church-Turing ye cierta, que l'afirmación de que la noción intuitiva d'algoritmu o procedimientu efectivu de cómputu correspuende a la noción de cómputu nuna máquina de Turing.

Los ordenadores electrónicos, basaos na arquiteutura de von Neumann según les máquines cuántiques tendríen esautamente'l mesmu poder d'espresión que'l d'una máquina de Turing si dispunxeren de recursos ilimitaos de tiempu y espaciu. De resultes, los llinguaxes de programación tienen a lo sumo el mesmu poder d'espresión que'l de los programes pa una máquina de Turing y na práutica non toos lo algamen. Los llinguaxes con poder d'espresión equivalente al d'una máquina de Turing denominar Turing completus.

Ente los formalismos equivalentes a una máquina de Turing tán:

• Máquines de Turing con delles cintes
• Máquines de Turing con cintes bidimensionales, Turmite (o una infinidá de cintes lliniales)
• Máquines de Turing con númberu llindáu d'estaos y símbolos pa la cinta *

Máquines de Turing con solu dos estaos

• Autómates finitos con dos piles
• Autómates finitos con dos contadores
• Gramátiques formales
• Máquina de Post
• Cálculo Lambda
• Funciones recursivas parciales
• Casi tolos llinguaxes de programación modernos si dispunxeren de memoria ilimitada
• Autómates celulares
• El Xuegu de la vida de John Conway
• Máquines de Turing non determinísticas
• Máquines de Turing probabilísticas
• Ordenador cuánticu

Los últimos trés exemplos utilicen una definición llixeramente distinta d'aceptación d'un llinguaxe. Elles acepten una pallabra si cualesquier, cómputu acepta (nel casu de non determinismu), o la mayoría de los cómputos acepten (pa les versiones probabilística y cuántica). Con estes definiciones, estes máquines tienen el mesmu poder d'espresión qu'una máquina de Turing.

¿Qué problemes riquen máquines más poderoses?

Considérase que delles máquines tienen mayor poder que les máquines de Turing. Por casu, una máquina oráculo qu'utiliza una caxa negra que puede calcular una función particular que nun ye calculable con una máquina de Turing. La fuercia de cómputu d'una máquina oráculu vien descrita pol so grau de Turing. La teoría de cómputos reales estudia máquines con precisión absoluta nos númberos reales. Dientro d'esta teoría, ye posible demostrar afirmaciones interesantes, tales como «el complementu d'un conxuntu de Mandelbrot ye solo parcialmente decidible».

Exemplos de funciones recursivas primitives

EXEMPLU 1. Sía k ∈, Y sía k la función constante. Definíu por k (x) = k pa tou x ∈. Demuestre que k ta en prim.

SOLUCIÓN Amosar por inducción sobre k. Yá que 0 ye una función inicial, tenemos 0 ∈ prim. Dígase k ∈ prim, daqué dau k. Entós (k + 1) (x) = (k (x)) 0, pa cada x ∈ ℕ. Asi que K + 1 ∈ prim (por sustitución de k en 0).

EXEMPLU 2. Demuestre que la diferencia absoluta, definida por

$|m-n|=\left\{{\begin{array}{rcl}m-n,&{\mbox{si }}&m\geq n\\n-m,&{\mbox{si }}&m<n\end{array}}\right.$

SOLUCIÓN. Nesti casu, llogramos la función por aciu la sustitución usando yá Funciones recursivas primitives probaes: |m − n| = (m−· n) + (n−· m). ¡Non tolos exemplos precisen un esquema recursivo primitivu!

Podemos esperar qu'esti procesu de construcción cada vez sía más complicáu. Tenemos De usar funciones anteriores hasta que tengamos toles funciones computables, na midida na que a partir de 1928 Wilhelm Ackermann definió una función computable que nun ye primitivu recursivo. Pa definir la función de Ackermann A, utilizó un añeráu recursivo. Equí ta una versión simplificada debíu al matemáticu húngaru R'osza P'eter, un cofundador en gran midida escaecíu de la teoría de la computabilidad:

A(m, 0) = m + 1 A(0, n + 1) = A(1, n) A(m + 1, n + 1) = A(A(m, n + 1), n).

El anidamiento na última llinia conduz a qu'A (m, m) sía muncho más rápido que la crecedera de cualquier función recursiva primitiva f (m) podría ser. Unu puede llograr una impresión de la rapidez cola computación namái unos pocos valores. Pa ello, utilice'l fechu de que la recursión añerada desusdicha da les ecuaciones equivalentes:

A(m, 0) = m + 1 A(m, 1) = 2 + (m + 3) − 3 A(m, 2) = 2 × (m + 3) − 3 A(m, 3) = 2(m+3) − 3 A(4, n) = 22 ... 2− 3 (m + 3 terms)

D'onde vamos llograr los valores: A(0,0)=1, A(1,1)=3, A(2,2)=7, A(3,3)=61, A(4,4)= 65536. Podemos remediar esta insuficiencia de prim añadiendo namái una regla más pa llograr nueves funciones.

Bibliografía

• 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. Dambos-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, Non. 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.
• Y. 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 Y. 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.
• Y. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
• Y. 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., «Defining the Turing jump», Mathematical Research Letters 6: 711–722, ISSN 1073-2780, http://www.math.cornell.edu/~shore/papers/pdf/jumpmrl.pdf 
• 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.

Referencies

• Datos: Q818930
• Multimedia: Computer science