Completitudinea Turing este atunci când un limbaj de programare este capabil să îndeplinească funcțiile unei mașini Turing. Acesta este un concept pentru un computer mecanic foarte simplu, uneori descris ca fiind cea mai simplă mașină care poate fi considerată un computer. Practic, toate limbajele de programare utilizate astăzi și, teoretic, computerele care le rulează, au caracterul Turing complet.
Conceptul de completitudine Turing vine de la Alan Turing, un informatician britanic a cărui activitate a inclus descifrarea mesajelor codificate în timpul celui de-al Doilea Război Mondial. Printre lucrările sale în domeniul calculului s-a numărat dezvoltarea unei filozofii a ceea ce poate face de fapt un computer. Aceasta a inclus conceptul că computerele funcționează pur și simplu prin rularea algoritmilor. Adică urmează un set fix de reguli pentru a procesa datele și, la rândul lor, pentru a rezolva probleme. Aceasta înseamnă că un computer nu „gândește” și nu ia decizii așa cum poate o persoană.
Pentru a ilustra conceptul, Turing a descris o mașină ipotetică pe care el a numit-o „a-machine”, cu „a” însemnând automat; alții au numit-o mai târziu mașina Turing. Aparatul procesa o bobină de bandă care se putea mișca înapoi sau înainte și conținea o linie de simboluri. În orice moment, mașina poate procesa un simbol și, dacă este necesar, să-l modifice. În sensul conceptului, bobina de bandă ar putea fi infinit de lungă, ceea ce înseamnă că memoria computerului nu era limitată în mod inerent. Aceasta este o analogie cu ideea că, odată ce un computer are un set de instrucțiuni de urmat, cantitatea de date la care poate aplica acele instrucțiuni este supusă doar limitelor fizice.
În mod ironic, majoritatea computerelor de astăzi nu au de fapt caracterul complet Turing. Acest lucru se datorează faptului că au limitări în ceea ce privește spațiul de stocare disponibil și, prin urmare, datele pe care le pot procesa. Au și limitări fizice, mai ales că în cele din urmă se vor uza. Este de fapt limbajul de programare care are caracterul complet al lui Turing. Din această cauză, un computer care rulează un astfel de program nu este un computer Turing, dar poate fi folosit pentru a simula unul.
Completitudinea Turing nu trebuie confundată cu testul Turing. Acesta a fost un experiment conceput de Turing pentru a vedea dacă computerele pot conversa în limbaj natural. Principiul testului este că, dacă un om nu poate face diferența dintre o conversație doar text cu computerul și un alt om, computerul trece testul. În timp ce unele computere au trecut testul atunci când gama de subiecte de conversație este restricționată, niciunul nu a făcut acest lucru în conversația nerestricționată.