Computabilitatea

Computabilitatea este capacitatea de a rezolva o problemă într-un mod eficient. Este un subiect cheie al domeniului teoriei computabilității în logica matematică și teoria calculului în informatică. Computabilitatea unei probleme este strâns legată de existența unui algoritm de rezolvare a problemei.

Cele mai studiate modele de computabilitate sunt funcțiile Turing-computable și μ-recursive și calculul lambda, toate având putere echivalentă din punct de vedere computațional. Sunt studiate și alte forme de computabilitate: noțiunile de computabilitate mai slabe decât mașinile Turing sunt studiate în teoria automatelor, în timp ce noțiunile de computabilitate mai puternice decât mașinile Turing sunt studiate în domeniul hipercalculului.

Probleme

O idee centrală în computabilitate este cea a unei probleme (computaționale), care este o sarcină a cărei computabilitate poate fi explorată.

Există două tipuri cheie de probleme:

O problemă de decizie fixează o mulțime S, care poate fi o mulțime de șiruri de caractere, numere naturale sau alte obiecte luate dintr-o mulțime mai mare U. O instanță particulară a problemei este de a decide, având în vedere un element u din U, dacă u este în S. De exemplu, fie U multimea numerelor naturale și S multimea numerelor prime. Problema de decizie corespunzătoare corespunde testării de primalitate.
O problemă de funcție constă dintr-o funcție f dintr-o mulțime U într-o mulțime V. O instanță a problemei este de a calcula, având în vedere un element u din U, elementul corespunzător f(u) din V. De exemplu, U și V pot fi mulțimea tuturor șirurilor binare finite, iar f poate lua un șir și returnează șirul obținut prin inversarea cifrelor de intrare (deci f(0101) = 1010).