b'\n_START_ARTICLE_\nFun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel\n_START_SECTION_\nLinguagens formais\n_START_PARAGRAPH_\nEm teoria da computabilidade \xc3\xa9 comum se considerar linguagens formais. Um alfabeto \xc3\xa9 um conjunto arbitr\xc3\xa1rio. Uma palavra sobre um alfabeto \xc3\xa9 uma sequ\xc3\xaancia finita de s\xc3\xadmbolos de um alfabeto, que podem ser usados mais de uma vez na mesma sequ\xc3\xaancia. Por exemplo, cadeias bin\xc3\xa1rias s\xc3\xa3o palavras do alfabeto . Uma linguagem passa a ser um subconjunto da cole\xc3\xa7\xc3\xa3o de todas as palavras do alfabeto. Por exemplo, a cole\xc3\xa7\xc3\xa3o de todas as cadeias bin\xc3\xa1rias que cont\xc3\xa9m exatamente tr\xc3\xaas elementos \xc3\xa9 uma linguagem do alfabeto bin\xc3\xa1rio._NEWLINE_Um propriedade relevante de uma linguagem formal \xc3\xa9 o n\xc3\xadvel de dificuldade requerido para decidir se uma palavra pertence \xc3\xa0 linguagem. Alguns sistemas de codifica\xc3\xa7\xc3\xa3o devem ser desenvolvidos para permitir que uma fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel ser alimentada por uma palavra qualquer; isso \xc3\xa9 geralmente considerado uma rotina. Uma linguagem \xc3\xa9 chamada comput\xc3\xa1vel (ou ainda, recursiva ou decid\xc3\xadvel) se h\xc3\xa1 uma fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel  de forma que para cada palavra  do alfabeto,  se a palavra pertence \xc3\xa0 linguagem e  se a palavra n\xc3\xa3o pertence \xc3\xa0 linguagem. Portanto, a linguagem \xc3\xa9 comput\xc3\xa1vel somente se h\xc3\xa1 um procedimento que pode computar de palavras pertencem \xc3\xa0 linguagem._NEWLINE_Uma linguagem \xc3\xa9 computacionalmente enumer\xc3\xa1vel (ou ainda, recursivamente enumer\xc3\xa1vel, ou semidecid\xc3\xadvel) se h\xc3\xa1 uma fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel  de forma que  \xc3\xa9 definida se e somente se a palavra  est\xc3\xa1 na linguagem. Portanto, apesar de n\xc3\xa3o ser decid\xc3\xadvel \xc3\xa9 comput\xc3\xa1vel. O termo enumer\xc3\xa1vel possui a mesma etimologia dos conjuntos enumer\xc3\xa1veis dos n\xc3\xbameros naturais.\n_START_SECTION_\nFun\xc3\xa7\xc3\xb5es incomput\xc3\xa1veis e problemas insol\xc3\xbaveis\n_START_PARAGRAPH_\nToda fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel tem um procedimento finito definindo instru\xc3\xa7\xc3\xb5es expl\xc3\xadcitas e n\xc3\xa3o-amb\xc3\xadguas sobre como computar. Al\xc3\xa9m disso, este procedimento tem que ser codificado em um alfabeto finito usado pelo modelo computacional, assim existem somente contavelmente muitas fun\xc3\xa7\xc3\xb5es comput\xc3\xa1veis. Por exemplo, fun\xc3\xa7\xc3\xb5es podem ser codificadas usando uma cadeia de bits (o alfabeto \xce\xa3 = {0, 1} )._NEWLINE_O conjunto dos n\xc3\xbameros reais \xc3\xa9 incont\xc3\xa1vel. Assim, muitos n\xc3\xbameros reais n\xc3\xa3o s\xc3\xa3o comput\xc3\xa1veis. Veja n\xc3\xbamero comput\xc3\xa1vel. O conjunto de fun\xc3\xa7\xc3\xb5es finit\xc3\xa1rias sobre os n\xc3\xbameros naturais \xc3\xa9 incont\xc3\xa1vel, por isso a maior parte n\xc3\xa3o \xc3\xa9 comput\xc3\xa1vel. Exemplos concretos de tais fun\xc3\xa7\xc3\xb5es s\xc3\xa3o o algoritmo do castor, a complexidade de Kolmogorov, ou qualquer fun\xc3\xa7\xc3\xa3o que gere como sa\xc3\xadda os d\xc3\xadgitos de um n\xc3\xbamero n\xc3\xa3o comput\xc3\xa1vel, como a constante de Chaitin._NEWLINE_De maneira similar, a maior parte dos subconjuntos dos n\xc3\xbameros naturais n\xc3\xa3o \xc3\xa9 comput\xc3\xa1vel. O problema da parada foi o primeiro conjunto do tipo a ser constru\xc3\xaddo. O Entscheidungsproblem (termo alem\xc3\xa3o para "problema de decis\xc3\xa3o"), proposto por David Hilbert, perguntava se existe um procedimento efetivo para se determinar quais declara\xc3\xa7\xc3\xb5es matem\xc3\xa1ticas (codificadas como n\xc3\xbameros naturais) s\xc3\xa3o verdadeiras. Turing e Church mostraram, independentemente, na d\xc3\xa9cada de 1930 que este conjunto dos n\xc3\xbameros reais n\xc3\xa3o \xc3\xa9 comput\xc3\xa1vel, por ser incont\xc3\xa1vel. De acordo com a tese de Church\xe2\x80\x93Turing, n\xc3\xa3o h\xc3\xa1 procedimento efetivo, ou algoritmo, que possa realizar tais computa\xc3\xa7\xc3\xb5es.\n_START_SECTION_\nComputabilidade relativa\n_START_PARAGRAPH_\nA no\xc3\xa7\xc3\xa3o de computabilidade de uma fun\xc3\xa7\xc3\xa3o pode ser relativizada para um conjunto arbitr\xc3\xa1rio de n\xc3\xbameros naturais A. Uma fun\xc3\xa7\xc3\xa3o f \xc3\xa9 definida como sendo comput\xc3\xa1vel em A (equivalentemente, A-comput\xc3\xa1vel ou comput\xc3\xa1vel relativa a A) quando ela satisfaz a defini\xc3\xa7\xc3\xa3o de uma fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel com modifica\xc3\xa7\xc3\xb5es permitindo o acesso a A como um or\xc3\xa1culo. Tal como acontece com o conceito de uma fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel, a computabilidade relativa pode ter defini\xc3\xa7\xc3\xb5es equivalentes em muitos modelos de computa\xc3\xa7\xc3\xa3o diferentes. Geralmente, isto \xc3\xa9 alcan\xc3\xa7ado complementando o modelo de computa\xc3\xa7\xc3\xa3o com uma opera\xc3\xa7\xc3\xa3o primitiva adicional que pergunta se um dado inteiro \xc3\xa9 um membro de A. N\xc3\xb3s tamb\xc3\xa9m podemos falar sobre f ser comput\xc3\xa1vel em g identificando g com seu grafo.\n_START_SECTION_\nTeoria da recurs\xc3\xa3o superior\n_START_PARAGRAPH_\nA teoria hiperaritim\xc3\xa9tica estuda aqueles conjuntos que podem ser computados a partir de um n\xc3\xbamero ordinal comput\xc3\xa1vel de itera\xc3\xa7\xc3\xb5es de salto de Turing do conjunto vazio. Isto \xc3\xa9 equivalente aos conjuntos definidos por ambas f\xc3\xb3rmulas existenciais e universais na linguagem da aritm\xc3\xa9tica de segunda ordem e em alguns modelos da Hipercomputa\xc3\xa7\xc3\xa3o. Teorias de recurs\xc3\xa3o ainda mais gerais t\xc3\xaam sido estudadas, como a teoria da E-recurs\xc3\xa3o aonde qualquer conjunto pode ser usado como um argumento para uma fun\xc3\xa7\xc3\xa3o E-recursiva.\n_START_SECTION_\nHipercomputa\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nEmbora a tese de Church-Turing afirme que as fun\xc3\xa7\xc3\xb5es comput\xc3\xa1veis incluem todas as fun\xc3\xa7\xc3\xb5es com algoritmos, \xc3\xa9 poss\xc3\xadvel considerar classes mais amplas de fun\xc3\xa7\xc3\xb5es que relaxem os requerimentos que os algoritmos possuem. O campo da hipercomputa\xc3\xa7\xc3\xa3o estuda modelos de computa\xc3\xa7\xc3\xa3o que v\xc3\xa3o al\xc3\xa9m da computa\xc3\xa7\xc3\xa3o de Turing normal. Estas n\xc3\xa3o violam a tese de Church-Turing, j\xc3\xa1 que elas permitem opera\xc3\xa7\xc3\xb5es que, mesmo que possam (ou n\xc3\xa3o) ser implementadas em um dispositivo f\xc3\xadsico, n\xc3\xa3o podem ser realizadas por uma pessoa usando l\xc3\xa1pis e papel.'