Home » Articole » Articole » Calculatoare » Computabilitatea

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

Alte tipuri de probleme includ probleme de căutare și probleme de optimizare.

Un obiectiv al teoriei computabilității este de a determina care probleme sau clase de probleme pot fi rezolvate în fiecare model de calcul.

(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)

Ghidul autorului de cărţi electronice
Ghidul autorului de cărţi electronice

Ai scris o carte. Foarte frumos. Dar nu ai scris-o pentru a o ţine pentru tine. Trebuie să o publici. Problema e că editurile percep preţuri foarte mari pentru buzunarele unora dintre autori, şi aceasta în mod obiectiv, datorită costurilor … Citeşte mai mult

Nu a fost votat 4.64 Selectează opțiunile
Facebook pentru afaceri şi utilizatori
Facebook pentru afaceri şi utilizatori

Ediția a doua (revăzută și îmbunătățită) Un ghid pentru dezvoltarea profilului propriu al utilizatorilor Facebook, şi pentru promovarea imaginii, produselor şi serviciilor firmei prin paginile de Facebook. Include volumele Ghid Facebook pentru utilizatori și Ghid pagini Facebook – Campanii de … Citeşte mai mult

Nu a fost votat 4.64 Selectează opțiunile
Ghid pagini Facebook – Campanii de promovare pe Facebook
Ghid pagini Facebook – Campanii de promovare pe Facebook

Paginile Facebook sunt cea mai simplă modalitate de a dezvolta o afacere online. Sunt gratuite, relativ ușor de configurat, și foarte flexibile. Indiferent dacă vrei să vinzi un produs sau un serviciu, sau să promovezi o organizaţie, o idee sau … Citeşte mai mult

Nu a fost votat 3.71 Selectează opțiunile

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *