Teoria de la computabilitat

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?

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:

• L'Entscheidungsproblem (problema de decisió en alemany) que es defineix com: donada una frase del càlcul de predicats de primer ordre, decidir si és un teorema. Alonzo Church i Alan Turing demostraren independentment que aquest problema és indecidible.
• El Problema de la parada, que es defineix així: donat un programa i la seva entrada, decidir si aquest programa acabarà per aquesta entrada o si correrà indefinidament. Alan Turing va demostrar que és un problema indecidible.
• Un nombre computable és un nombre real que pot ser aproximat per un algorisme amb un nivell d'exactitud arbitrari. Alan Turing va demostrar que quasi tots els nombres no són computables. Per exemple, la Constant de Chaitin no és computable tot i que sí que està ben definida.

Quins altres formalismes equivalen a les màquines de Turing?

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:

• Màquines de Turing amb diverses cintes
• Màquines de Turing amb cintes bidimensionals (o una infinitat de cintes lineals)
• Màquines de Turing amb nombre limitat d'estats i símbols per a la cinta.
• Màquina de Turing amb només dos estats.
• Autòmats finits amb dues piles
• Autòmats finits amb dos contadors
• Gramàtiques formals
• Sistemes de correspondència de Post
• Càlcul lambda
• Funcions recursives parcials
• Quasi tots els Llenguatges de programació moderns si disposessin de memòria il·limitada.
• Autòmats cel·lulars
• El joc de la vida de John Conway
• Màquines de Turing no derterminístiques
• Màquines de Turing probabilístiques
• Computador quàntic

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?

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