estudi sobre les funcions computables From Wikipedia, the free encyclopedia
La teoria de la computabilitat és la part de la computació que estudia els problemes de decisió que poden ser resolts amb un algorisme o equivalentment amb una màquina de Turing.[1][2][3] La teoria de la computabilitat s'interessa per quatre preguntes:
La teoria de la complexitat computacional classifica les funcions computables segons l'ús que fan de diversos recursos en diversos tipus de màquina.
El concepte de computabilitat o calculabilitat és una noció formal del llenguatge de la lògica i de les matemàtiques. Un problema és computable si es pot resoldre mitjançant un algorisme i no computable en el cas contrari, és a dir, serà computable si es pot expressar en termes de funció parcial en què les dades i els resultats siguin cadenes de caràcters (o pertanyin a un tipus de dades la implementació de les quals hagi estat provada), de manera que aquesta funció es pugui computar.[4]
La Teoria de la Computabilidad o d'algorismes és una disciplina enquadrada en la Informàtica teòrica que té com a objectiu establir els límits lògics que presenten els sistemes informàtics a l'hora de resoldre problemes mitjançant els algorismes.[5] Des de la teoria de la computabilitat s'ha pogut determinar una gradació de problemes no computables. Cal tenir en compte que en aquesta jerarquia hi poden haver problemes que encara que siguin solubles, no hi pot haver cap mecanisme lògic capaç de garantir-ne la solució, així com els problemes insolubles, pels quals la teoria n'ha demostrat la insolubilitat.[6]
No tots els problemes poden ser resolts.[7] Un problema indecidible és un que no pot ser resolt amb un algorisme inclús si es disposa d'espai i temps il·limitat. Actualment es coneixen molts problemes indecidibles, com per exemple:
Els llenguatges 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 amb el càlcul Lambda són exactament aquelles que poden ser computades amb una màquina de Turing. Aquests tres formalismes, les màquines de Turing, els llenguatges formals i el càlcul Lambda són formalismes molt dissímils i van ser desenvolupats per diferents persones. Tot i això, tots tres són equivalents i tenen el mateix poder d'expressió. Generalment es pren aquesta coincidència com evidència de què la Tesi de Church-Turing és certa, que l'afirmació de què la noció intuïtiva d'algorisme 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 Von Neumann així com les màquines quàntiques tindrien exactament el mateix poder d'expressió que el d'una màquina de Turing si disposés de recursos il·limitats de temps i espai. Com a conseqüència, els llenguatges de programació tenen com a molt el mateix poder d'expressió que el dels programes per una màquina de Turing i a la pràctica no tots hi arriben. Els llenguatges amb poder d'expressió equivalent al d'una màquina de Turing s'anomenen Turing complets.
Entre els formalismes equivalents a una màquina de Turing hi ha:
Els tres últims exemples utilitzen una definició lleugerament diferent d'acceptació d'un llenguatge. Aquestes accepten una paraula si qualsevol còmput accepta (en el cas de no determinisme), o la majoria dels còmputs accepten (per les versions probabilística i quàntica). Amb aquestes definicions, aquestes màquines tenen el mateix poder d'expressió que una màquina de Turing.
Es considera que algunes màquines tenen un major poder que les màquines de Turing. Per exemple, una màquina oracle que utilitza una caixa negra que pot calcular la funció particular que no és calculable amb una màquina de Turing. La força de còmput d'una màquina oracle ve descrita pel seu grau de Turing. La teoria de còmputs reals estudia màquines amb precisió absoluta en els nombres reals. Dins d'aquesta teoria, és possible demostrar afirmacions interessants, tals com el "el complement d'un conjunt de Mandelbrot és només parcialment decidible".