Teoria de la computabilidad

La teoria de la computabilidad o teoria de la recursión és la part de la computació que estudia els problemes de decisió que es poden resoldre en un algoritme o equivalentemente en una màquina de Turing. Les preguntes fonamentals de la teoria de la computabilidad són:

• ¿Quins problemes pot resoldre una màquina de Turing?
• ¿Qué atres #formalisme equivalen a les màquines de Turing?
• ¿Quins problemes requerixen màquines més poderoses?
• ¿Quins problemes requerixen màquines menys poderoses?

La teoria de la complexitat computacional classifica les funcions computables segons l'us que fan de diversos recursos en diversos tipos de màquina.

Introducció

La Teoria de la Computabilidad és l'estudi matemàtic dels models de computació. Com a tal estudi teòric, es va originar en la década dels anys 30 en els treballs dels llògics Church, Gödel, Kleene, Post i Turing.

Tinga's en conte que en aquells anys l'alvanç tecnològic ni tan sols podia prevore la revolució que en la década dels 60 durien els ordenadors, i no obstant, conceptes habituals hui en dia (computadors universals, programes com a llistes d'instruccions d'un llenguage formal, intérprets, ...) ya varen ser definits des d'un punt de vista teòric per eixos matemàtics.

Descripció

La teoria de la computabilidad, també denominada teoria de la recursión, és una de les quatre parts que constituïxen la llògica matemàtica, sent les atres tres, la teoria de conjunts, la teoria de models i la teoria de la demostració, i s'ocupa de l'estudi i classificació de les relacions i aplicacions computables. Ademés, la teoria de la computabilidad, junt en la teoria d'autómates, de l'informació, dels llenguages i màquines, i és el fonament de l'informàtica teòrica i esta, a la seua volta, de l'indústria dels ordenadors.

Des de temps inmemorial se sap que certa classe de problemes, i.g., la determinació del màxim comú divisor de dos número entero, per mig del algoritme de Euclides, o la determinació dels número primo, per mig de la garbell de Eratóstenes, són algorítmicamente solubles, i.i., hi ha algoritmes o procediments mecànics que permeten obtindre la solució del problema en qüestió. De manera que fins a principis de el XX es donava per fet que existien algoritmes i que l'únic problema residia en determinar-los. Aixina que, si lo que es desija és determinar un algoritme, no hi ha cap necessitat de definir la classe de tots els algoritmes; això només és necessari si es pretén demostrar que algun problema no és algorítmicamente soluble, i.i., que para dit problema no hi ha cap algoritme que ho resolga.

És possible que el primer en afirmar la no existència d'un algoritme fora Tietze en 1908, quí va dir dels grups de presentació finita:

“. . . la qüestió sobre quàn dos grups són isomorfos no és soluble en general.”

Pero sembla ser que va ser, per una part, el problema de la decidibilidad de la llògica de predicats plantejat per Hilbert i Ackermann en el seu llibre sobre llògica, publicat en 1928, i, per una atra, l'assunt de la solubilidad de tot problema matemàtic, lo que va induir, en llaures a resoldre'ls, a diversos investigadors a partir de 1930, i entre els que cal mencionar a Gödel, Church i Turing, a propondre diverses #formalisació del concepte informal de funció mecánicamente computable. Degut a que de totes eixes #formalisació, i d'atres propostes per Kleene, Post i Markoff, es va demostrar que eren dos a dos equivalents, es va propondre la hipòtesis, coneguda com Hipòtesis de Church-Turing-Post-Kleene, que afirma la coincidència entre el concepte informal de funció parcial mecànica o algorítmicamente computable, i el concepte formal, matemàtic, d'aplicació parcial recursiva. Naturalment, eixa hipòtesis, de caràcter similar a atres hipòtesis propostes en les ciències empíriques, no és demostradora, i el seu fonament últim residix en les #equivalència abans mencionades.

Hi ha cursos dedicats, en primer lloc, a l'estudi de diferents classes d'aplicacions recursivas, des de les recursivas primitives, fins a les parcials recursivas, passant per les recursivas generals, aixina com al de diverses classes de relacions, entre les que cal citar a les recursivas primitives, les recursivamente enumerables i a les recursivas, demostrant ademés, certes teoremes fonamentals de la teoria de la recursión, deguts en gran mida a Kleene; i, en segon lloc, a l'aplicació de la teoria de la recursión a la demostració de l'indecidibilidad de la llògica de predicats de primer orde, i.i., a la demostració de que el conjunt dels números de Gödel de les teoremes de la llògica de predicats de primer orde no és recursivo, encara que sí siga recursivamente enumerable; i de les teoremes de incompletitud de Gödel, dels quals, el primer dona conte, essencialment, de la diferència, en l'aritmètica, entre les nocions de veres i demostrabilidad, mentres que el segon afirma que, baix certes condicions, no és possible demostrar des d'una teoria, la consistència de la mateixa, i.i., essencialment que l'infinit no és eliminable en les matemàtiques.

Conjunts computables i no computables

La teoria de la recursión es va originar en la década de 1930, en el treball de Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene i Emil Post.

Els resultats fonamentals que varen obtindre els investigadors varen estabilisar el concepte de funció computable com la manera correcta de formalisar l'idea sobre càlculs efectius.

Estos resultats varen dur a Stephen Kleene (1952) a falcar dos noms, "Tesis de Church" (Kleene 1952:300) i "Tesis de Turing" (Kleene 1952:376). Hui en dia abdós es consideren com una única hipòtesis, la Tesis de Church-Turing, la qual establix que qualsevol funció que siga computable per un cert algoritme és una funció computable. Encara que en un principi era alguna cosa un tant escèptic, al voltant de l'any 1946, Gödel va defendre esta tesis:

"Tarksi ha subrallat en la seua llectura (i cree justament) la gran importància del concepte de recursividad general (o computabilidad de Turing). En la meua opinió esta importància es deu en gran mida al fet de que en este concepte, per fi s'ha conseguit donar-li una noció absoluta a una interessant noció epistemològica, és dir, una que no depén del formalisme elegit.*"(Gödel 1946 en Davis 1965:84).

En una definició sobre càlculs efectius varen aparéixer les primeres proves de que hi ha certs problemes en les matemàtiques que no poden ser decidits d'una manera eficaç. Church (1936p, 1936f) i Turing (1936), inspirats per les tècniques usades per Gödel (1931) per a provar les seues teoremes sobre l'incompletitud, varen demostrar per separat que no és possible decidir l'Entscheidungsproblem d'una manera eficaç. Este resultat va demostrar que no existix un procediment algorítmic que puga decidir de manera correcta si certes proposicions matemàtiques són verdaderes o no.

Molts problemes en les matemàtiques han segut demostrats ser indecidibles una volta es varen establir estos primers eixemples. En 1947, Markov i Post varen publicar per separat els seus treballs mostrant que el problema de les paraules per als semigrupos no pot ser decidit d'una manera eficaç. Ampliant este resultat, Pyotr Novikov i William Boone varen demostrar independentment en la década de 1950 que el problema de les paraules per als semigrupos no es pot resoldre d'una manera efectiva: no hi ha cap procediment eficaç que, donada una paraula en un grup, decidixca si l'element representat per la paraula és l'element identitat del grup. En 1970, Yuri Matiyasevich va demostrar (usant els resultats de Julia Robinson) el Teorema de Matiyasevich, el qual implica que el dècim problema de Hilbert no té una solució eficaç; este problema preguntava si hi havia o no un procediment per mig del qual es poguera decidir si una equació diofántica sobre els número entero té una solució sancera. La llista de problemes indecidibles conté eixemples adicionals sobre problemes sense solucions computables.

L'estudi sobre quines construccions matemàtiques poden ser portades a terme d'una forma eficaç es denomina a voltes matemàtica recursiva; El Handbook of Recursive Mathematics (Ershov et al. 1998) cobrix molts dels resultats coneguts en este camp.

Antecedents

L'orige dels models abstractes de computació s'enquadra en els anys 1930 (ans que existiren els ordenadors moderns), per al treball dels llògics Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, i Alan Turing. Estos treballs inicials han tingut una profunda influència, tant en el desenroll teòric com en abundants aspectes de la pràctica de la computació; preveent inclús l'existència d'ordenadors de propòsit general, la possibilitat d'interpretar programes, la dualitat entre software i hardware, i la representació de llenguages per estructures formals basats en regles de producció.

El punt inicial d'estos primers treballs varen ser les qüestions fonamentals que David Hilbert va formular en 1900, durant el transcurs d'un congrés internacional.

Lo que Hilbert pretenia era crear un sistema matemàtic formal complet i consistent en el qual totes les asseveracions anaren plantejades en precisió. La seua intenció era trobar un algoritme que determinara la veritat o falsetat de qualsevol proposició en el sistema formal. Al problema en qüestió se li va denominar Entscheidungsproblem. En cas que Hilbert haguera complit el seu objectiu, qualsevol problema ben definit es resoldria simplement en eixecutar dit algoritme.

Pero varen ser uns atres els que per mig d'una série d'investigacions varen mostrar que açò no era possible. En contra d'esta idea K. Gödel va traure a la llum el seu conegut Primera Teorema de Incompletitud. Est ve a expressar que tot sistema de primer orde consistent que continga els teoremes de l'aritmètica i el conjunt de la qual d'axiomas siga recursivo no és complet. Gödel va construir una fòrmula que és satisfactòria pero que no pot ser provada en el sistema. Com a conseqüència, no és possible trobar el sistema formal desijat per Hilbert en el marc de la llògica de primer orde, a no ser que es prenga un conjunt no recursivo de #axioma.

Una posterior versió, que resulta més general, de la teorema de incompletitud de Gödel, indica que cap sistema deductivo que continga les teoremes de l'aritmètica, i en els #axioma recursivamente enumerables pot ser consistent i complet al mateix temps. Açò fa pensar, a nivell intuïtiu, que no va a ser possible definir un sistema formal.

¿Quins problemes pot resoldre una màquina de Turing?

No tots els problemes poden ser resolts. Un problema indecidible és un que no pot ser resolt en un algoritme encara si es dispon d'espai i temps illimitat. Actualment es coneixen molts problemes indecidibles, com per eixemple:

• l'Entscheidungsproblem (problema de decisió en alemà) que es definix com: Donada una frase del càlcul de predicats de primer orde, decidir si ella és una teorema. Church i Turing varen demostrar independentment que este problema és indecidible (vore Tesis de Church-Turing).
• El Problema de la parada, que es definix aixina: Donat un programa i la seua entrada, decidir si eixe programa terminarà per a eixa entrada o si correrà indefinidament. Turing va demostrar que es tracta d'un problema indecidible.
• Un número computable és un número real que pot ser aproximat per un algoritme en un nivell d'exactitut arbitrari. Turing va demostrar que casi tots els números no són computables. Per eixemple, la Constant de Chaitin no és computable encara que sí que està ben definida.

¿Qué atres #formalisme equivalen a les màquines de Turing?

Els llenguages formals que són acceptats per una màquina de Turing són exactament aquells que poden ser generats per una gramàtica formal. El càlcul Lambda és una forma de definir funcions. Les funcions que poden ser computades en el càlcul Lambda són exactament aquelles que poden ser computades en una màquina de Turing. Estos tres #formalisme, les màquines de Turing, els llenguages formals i el càlcul Lambda són #formalisme molt disímiles i varen ser desenrollats per diferents persones. No obstant, tots ells són equivalents i tenen el mateix poder d'expressió. Generalment es pren esta notable coincidència com a evidència de que la tesis de Church-Turing és certa, que l'afirmació de que la noció intuïtiva d'algoritme o procediment efectiu de còmput correspon a la noció de còmput en una màquina de Turing.

Els computadors electrònics, basats en l'arquitectura de von Neumann aixina com les màquines quàntiques tindrien exactament el mateix poder d'expressió que el d'una màquina de Turing si dispongueren de recursos illimitats de temps i espai. Com a conseqüència, els llenguages de programació tenen com a molt el mateix poder d'expressió que el dels programes per a una màquina de Turing i en la pràctica no tots ho alcancen. Els llenguages en poder d'expressió equivalent al d'una màquina de Turing es denominen Turing complets.

Entre els #formalisme equivalents a una màquina de Turing estan:

• Màquines de Turing en vàries cintes

• Màquines de Turing en cintes bidimensionales, Turmite (o una infinitat de cintes llineals)
• Màquines de Turing en número llimitat d'estats i símbols per a la cinta
• Màquines de Turing en sol dos estats
• Autómates finitos en dos piles
• Autómates finitos en dos contadors
• Gramàtiques formals
• Màquina de Post
• Càlcul Lambda
• Funcions recursivas parcials
• Casi tots els llenguages de programació moderns si dispongueren de memòria illimitada
• Autómates celulars
• El Joc de la vida de John Conway
• Màquines de Turing no determinísticas
• Màquines de Turing provabilístiques
• Computador quàntic

Els últims tres eixemples utilisen una definició llaugerament diferent d'acceptació d'un llenguage. Elles accepten una paraula si qualsevol, còmput accepta (en el cas de no determinisme), o la majoria dels #còmput accepten (per a les versions provabilística i quàntica). En estes definicions, estes màquines tenen el mateix poder d'expressió que una màquina de Turing.

¿Quins problemes requerixen màquines més poderoses?

Es considera que algunes màquines tenen major poder que les màquines de Turing. Per eixemple, una màquina oràcul que utilisa una caixa negra que pot calcular una funció particular que no és calculable en una màquina de Turing. La força de còmput d'una màquina oràcul ve descrita pel seu grau de Turing. La teoria de #còmput reals estudia màquines en precisió absoluta en els número real. Dins d'esta teoria, és possible demostrar afirmacions interessants, tals com «el complement d'un conjunt de Mandelbrot és solament parcialment decidible».

Eixemples de funcions recursivas primitives

EIXEMPLE 1. Siga k ∈, I siga k la funció constant. Definit per k (x) = k per a tot x ∈. Demostre que k està en prim.

SOLUCIÓ Ho vàrem mostrar per inducció sobre k. ya que 0 és una funció inicial, tenim 0 ∈ prim. Diga's k ∈ prim, alguna cosa donat k. Llavors (k + 1) (x) = (k (x)) 0, per a cada x ∈ ℕ. Aixina que K + 1 ∈ prim (per substitució de k en 0).

EIXEMPLE 2. Demostre que la diferència absoluta, definida per $|m-n|=\{\begin{array}{ccc}m-n,& \text{si }& m\ge n\\ n-m,& \text{si }& m<n\end{array}$.

SOLUCIÓ. En este cas, obtenim la funció per mig de la substitució usant ya Funcions recursivas primitives provades: |m − n| = (m−· n) + (n−· m). ¡No tots els eixemples necessiten un esquema recursivo primitiu!

Podem esperar que este procés de construcció cada volta siga més complicat. Devem usar funcions anteriors fins que tingam totes les funcions computables, en la mida en que a partir de 1928 Wilhelm Ackermann va definir una funció computable que no és primitiu recursivo. Per a definir la funció de Ackermann A, va utilisar un anidado recursivo. Ací està una versió simplificada pel matemàtic hongarés R'osza P'eter, un cofundador en gran mida oblidat de la teoria 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 en l'última llínea conduïx a que A (m, m) siga molt més ràpit que el creiximent de qualsevol funció recursiva primitiva f (m) podria ser. Un pot obtindre una impressió de la rapidea en la computació només uns pocs valors. Per a això, utilise el fet de que la recursión anidada antedicha dona les equacions equivalents:

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'a on obtindrem els valors: A(0,0)=1, A(1,1)=3, A(2,2)=7, A(3,3)=61, A(4,4)= 65536. Podem remediar esta insuficiència de prim afegint només una regla més per a obtindre noves funcions.

Bibliografia

• 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
• I. 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. Abdós-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
• I. 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.
• I. 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 I. 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.
• I. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
• I. 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.
• (1999).«Defining the Turing jump».Mathematical Research Letters.6

711–722.ISSN 1073-2780.

• 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.
• https://www.uv.es/jkliment/Documents/TeoComp.pc.pdf
• http://www.cs.us.es/fsancho/?p=computabilidad