Turingova potpunost je kada programski jezik može izvršavati funkcije Turingovog stroja. Ovo je koncept za vrlo osnovno mehaničko računalo, koje se ponekad opisuje kao najjednostavniji stroj koji se može smatrati računalom. Gotovo svi programski jezici koji se danas koriste, a u teoriji, računala koja ih pokreću, imaju Turingovu potpunost.
Koncept Turingove potpunosti dolazi od Alana Turinga, britanskog informatičara čiji je rad uključivao dešifriranje kodiranih poruka tijekom Drugog svjetskog rata. Među njegovim radom na računalstvu bio je razvoj filozofije onoga što računalo zapravo može učiniti. To je uključivalo koncept da računala rade jednostavno pokretanjem algoritama. To znači da slijede fiksni skup pravila za obradu podataka i rješavanje problema. To znači da računalo ne “razmišlja” i ne donosi odluke kao što to može osoba.
Kako bi ilustrirao koncept, Turing je opisao hipotetski stroj koji je nazvao “a-stroj”, a “a” znači automatski; drugi su ga kasnije nazvali Turingov stroj. Stroj bi obrađivao kolut vrpce koji se mogao kretati naprijed ili natrag i sadržavao je red simbola. U svakom trenutku stroj može obraditi jedan simbol i, ako je potrebno, izmijeniti ga. Za potrebe koncepta, kolut trake mogao bi biti beskonačno dugačak, što znači da memorija računala nije inherentno ograničena. Ovo je analogija za ideju da nakon što računalo ima skup instrukcija koje treba slijediti, količina podataka na koju može primijeniti te upute podliježe samo fizičkim ograničenjima.
Ironično, većina današnjih računala zapravo nema Turingovu potpunost. To je zato što imaju ograničenja dostupnog prostora za pohranu, a time i podataka koje mogu obraditi. Oni također imaju fizička ograničenja, ponajviše to što će se na kraju istrošiti. To je zapravo programski jezik koji ima Turingovu potpunost. Zbog toga računalo koje pokreće takav program nije Turingovo računalo, ali se može koristiti za simulaciju.
Turingovu potpunost ne treba miješati s Turingovim testom. Ovo je bio eksperiment koji je Turing osmislio kako bi vidio mogu li računala razgovarati na prirodnom jeziku. Načelo testa je da ako čovjek ne može napraviti razliku između tekstualnog razgovora s računalom i drugog čovjeka, računalo prolazi test. Dok su neka računala prošla test kada je raspon tema razgovora ograničen, nijedno to nije učinilo u neograničenom razgovoru.