Kompletność Turinga ma miejsce wtedy, gdy język programowania jest w stanie wykonywać funkcje maszyny Turinga. Jest to koncepcja bardzo podstawowego komputera mechanicznego, czasami określanego jako najprostsza maszyna, którą można uznać za komputer. Praktycznie wszystkie obecnie używane języki programowania i teoretycznie komputery, które je obsługują, posiadają kompletność Turinga.
Pojęcie kompletności Turinga pochodzi od Alana Turinga, brytyjskiego informatyka, którego praca obejmowała odszyfrowywanie zakodowanych wiadomości podczas II wojny światowej. Wśród jego pracy nad informatyką było opracowanie filozofii tego, co komputer może faktycznie zrobić. Obejmowało to koncepcję, że komputery działają po prostu przez uruchamianie algorytmów. To znaczy, że przestrzegają ustalonego zestawu reguł przetwarzania danych, a co za tym idzie rozwiązywania problemów. Oznacza to, że komputer nie „myśli” ani nie podejmuje decyzji tak, jak człowiek.
Aby zilustrować tę koncepcję, Turing opisał hipotetyczną maszynę, którą nazwał „a-maszyną”, przy czym „a” oznacza automat; inni później nazwali to maszyną Turinga. Maszyna przetwarzała rolkę taśmy, która mogła poruszać się do przodu lub do tyłu i zawierać linię symboli. W każdej chwili maszyna może przetworzyć jeden symbol iw razie potrzeby zmienić go. Na potrzeby koncepcji rolka taśmy mogła być nieskończenie długa, co oznacza, że pamięć komputera nie była z natury ograniczona. Jest to analogia do idei, że gdy komputer ma zestaw instrukcji do wykonania, ilość danych, do których może zastosować te instrukcje, podlega jedynie ograniczeniom fizycznym.
Jak na ironię, większość dzisiejszych komputerów nie ma kompletności Turinga. Dzieje się tak, ponieważ mają ograniczenia dostępnej przestrzeni dyskowej, a tym samym danych, które mogą przetwarzać. Mają też ograniczenia fizyczne, a przede wszystkim to, że w końcu się zużyją. W rzeczywistości jest to język programowania, który ma kompletność Turinga. Z tego powodu komputer, na którym działa taki program, nie jest komputerem Turinga, ale może być użyty do jego symulacji.
Kompletność Turinga nie powinna być mylona z testem Turinga. Był to eksperyment zaprojektowany przez Turinga, aby sprawdzić, czy komputery mogą rozmawiać w języku naturalnym. Zasada testu polega na tym, że jeśli człowiek nie jest w stanie odróżnić rozmowy tekstowej z komputerem od innego człowieka, komputer zdaje test. Podczas gdy niektóre komputery zdały test, gdy zakres tematów konwersacji jest ograniczony, żaden nie zrobił tego w przypadku konwersacji nieograniczonej.