Teoria de la computabilitat

De Viquipèdia
Dreceres ràpides: navegació, cerca

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. La teoria de la computabilitat s'interessa per quatre preguntes:

  • Quins problemes pot resoldre una màquina de Turing?
  • Quins altres formalismes equivalen a les màquines de Turing?
  • Quins problemes requereixen màquines més poderoses?
  • Quins problemes requereixen màquines menys poderoses?

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

Quins problemes pot resoldre una màquina de Turing?[modifica | modifica el codi]

No tots els problemes poden ser resolts. 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:

Quins altres formalismes equivalen a les màquines de Turing?[modifica | modifica el codi]

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.

Quins problemes requereixen màquines més poderoses?[modifica | modifica el codi]

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".