Teoría da computabilidade

A teoría da computabilidade é a parte da computación que estuda os problemas de decisión que poden ser resoltos cun algoritmo ou equivalentemente coa chamada máquina de Turing. A teoría da computabilidade interésase por catro preguntas:

• Que problemas pode resolver unha máquina de Turing?
• Que outros formalismos equivalen ás máquinas de Turing?
• Que problemas requiren máquinas máis poderosas?
• Que problemas requiren máquinas menos poderosas?

VEB Robotron Elektronik Dresden.

A teoría da complexidade computacional clasifica as funcións computables segundo o uso que fan de diversos recursos en diversos tipos de máquina.

Antecedentes

Alan Turing en 1930

A orixe dos modelos abstractos de computación encádrase na década de 1930, antes de que existisen os computadores modernos, no traballo dos lóxicos Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post e Alan Turing. Estes traballos iniciais tiveron unha fonda influencia, tanto no desenvolvemento teórico como en abundantes aspectos da práctica da computación; prevendo incluso a existencia de computadores de propósito xeral, a posibilidade de interpretar programas, a dualidade entre software e hardware, e a representación de linguaxes por estruturas formais baseadas en regras de produción.

O punto inicial destes primeiros traballos foron as cuestións fundamentais que David Hilbert formulou en 1900, durante o transcurso dun congreso internacional.

O que Hilbert pretendía era crear un sistema matemático formal completo e consistente no que todas as aseveracións fosen expostas con precisión. A súa intención era atopar un algoritmo que determinase a verdade ou a falsidade de calquera proposición no sistema formal. O problema en cuestión denominouse Entscheidungsproblem. No caso de que Hilbert cumprise o seu obxectivo calquera problema ben definido resolveríase simplemente ao executar o devandito algoritmo.

Porén, foron outros os que mediante unha serie de investigacións mostraron que isto non era posible. En contra desta idea Gödel sacou á luz o seu coñecido Primeiro Teorema de Incompletitude, que vén expresar que todo sistema de primeira orde consistente que conteña os teoremas da aritmética e cuxo conxunto de axiomas sexa recursivo non é completo. Gödel construíu unha fórmula que é satisfactoria pero que non pode ser probada no sistema. Como consecuencia, non é posible atopar o sistema formal desexado por Hilbert no marco da lóxica de primeira orde, a non ser que se tome un conxunto non recursivo de axiomas.

Unha versión posterior, máis xeral, do teorema de incompletitude de Gödel, indica que ningún sistema dedutivo que conteña os teoremas da aritmética, e cos axiomas recursivamente enumerables pode ser consistente e completo á vez. Isto fai pensar, a nivel intuitivo, que non vai ser posible definir un sistema formal.

Problemas que pode resolver unha máquina de Turing

Non todos os problemas poden ser resoltos. Un problema indecidible é un que non pode ser resolto cun algoritmo aínda se se dispón de espazo e tempo ilimitado. Actualmente coñécense moitos problemas indecidibles, por exemplo:

• O Entscheidungsproblem, que se define como: Dada unha frase do cálculo de predicados de primeira orde, decidir se é un teorema. Church e Turing demostraron independentemente que este problema é indecidible (tese de Church-Turing).
• O problema da parada, que se define como: Dado un programa e a súa entrada, decidir se ese programa terminará para esa entrada ou se seguirá indefinidamente. Turing demostrou que se trata dun problema indecidible.
• Un número computable é un número real que pode ser aproximado por un algoritmo cun nivel de exactitude arbitrario. Turing demostrou que case todos os números non son computables. Por exemplo, a constante de Chaitin non é computable aínda que si que está ben definida.

Formalismos que equivalen ás máquinas de Turing

As linguaxes formais que son aceptados por unha máquina de Turing son exactamente aqueles que poden ser xerados por unha gramática formal. O cálculo Lambda é unha forma de definir funcións. As funcións que poden ser computadas co cálculo Lambda son exactamente aquelas que poden ser computadas cunha máquina de Turing. Este tres formalismos, as máquinas de Turing, as linguaxes formais e o cálculo Lambda son formalismos moi desemellantes e foron desenvolvidos por diferentes persoas. Con todo, todos eles son equivalentes e teñen o mesmo poder de expresión. Xeralmente tómase esta notable coincidencia como evidencia de que a tese de Church-Turing é certa, que a afirmación de que a noción intuitiva de algoritmo ou procedemento efectivo de cómputo corresponde á noción de cómputo nunha máquina de Turing.

Os computadores electrónicos, baseados na arquitectura de von Neumann así como as máquinas cuánticas terían exactamente o mesmo poder de expresión que o dunha máquina de Turing se dispuxesen de recursos ilimitados de tempo e espazo. Como consecuencia, as linguaxes de programación teñen como máximo o mesmo poder de expresión que o dos programas para unha máquina de Turing e na práctica non todos o alcanzan. As linguaxes con poder de expresión equivalente ao dunha máquina de Turing denomínanse Turing completos.

Entre os formalismos equivalentes a unha máquina de Turing están:

• As máquinas de Turing con varias cintas, con cintas bidimensionais, cun número limitado de estados e símbolos para a cinta ou con só dous estados; as máquinas de Turing non determinísticas e as probabilísticas.
• Os autómatas finitos con dúas pilas ou con dous contadores.
• As gramáticas formais.
• A máquina de Post.
• O cálculo Lambda.
• As funcións recursivas parciais.
• Case todas as linguaxes de programación modernas se dispuxesen de memoria ilimitada.
• Os autómatas celulares.
• O xogo da vida de John Conway.
• O Computador cuántico.

Problemas que requiren máquinas máis poderosas

Considérase que algunhas máquinas teñen maior poder que as máquinas de Turing. Por exemplo, unha máquina oráculo que utiliza unha caixa negra que pode calcular unha función particular que non é calculable cunha máquina de Turing. A forza de cómputo dunha máquina oráculo vén descrita polo seu grao de Turing. A teoría de cómputos reais estuda máquinas con precisión absoluta nos números reais. Dentro desta teoría, é posible demostrar afirmacións interesantes, tales como «o complemento dun conxunto de Mandelbrot é só parcialmente decidible».

Véxase tamén

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
• E. 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 os-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
• E. 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, Nova 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.
• 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 [1]
• 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.

Outros artigos

• Función computábel