Co to jest kompletność Turinga?

Kompletność Turinga ma miejsce, gdy język programowania jest w stanie pełnić funkcje maszyny Turinga. Jest to koncepcja bardzo podstawowego komputera mechanicznego, czasami opisywanego 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ą, mają kompletność Turinga.

Koncepcja kompletności Turinga pochodzi od Alana Turinga, brytyjskiego informatyka, którego praca obejmowała odszyfrowanie zakodowanych wiadomości podczas II wojny światowej. Jednym z jego działań związanych z informatyką było opracowanie filozofii tego, co komputer mógłby zrobić. Obejmowało to koncepcję, że komputery działają po prostu przez uruchamianie algorytmów. To znaczy, że przestrzegają ustalonego zestawu zasad przetwarzania danych, a tym samym rozwiązywania problemów. Oznacza to, że komputer nie „myśli” ani nie podejmuje decyzji tak, jak ktoś może.

Aby zilustrować tę koncepcję, Turing opisał hipotetyczną maszynę, którą nazwał „maszyną”, przy czym „a” oznacza automat; inni później nazwali to maszyną Turinga. Maszyna przetwarzałaby rolkę taśmy, która mogłaby przesuwać się do tyłu lub do przodu i zawierała linię symboli. W dowolnym momencie urządzenie może przetworzyć jeden symbol i, jeśli to konieczne, zmienić go. Dla celów tej koncepcji rolka taśmy może być nieskończenie długa, co oznacza, że ​​pamięć komputera nie jest 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. Wynika to z faktu, że mają ograniczenia dotyczące dostępnej przestrzeni dyskowej, a tym samym danych, które mogą przetwarzać. Mają także ograniczenia fizyczne, zwłaszcza że w końcu się zużyją. W rzeczywistości jest to język programowania, który ma kompletność Turinga. Z tego powodu komputer z takim programem nie jest komputerem Turinga, ale można go symulować.

Kompletności Turinga nie należy mylić 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 potrafi odróżnić rozmowy tekstowej z komputerem od innego człowieka, komputer przechodzi test. Chociaż niektóre komputery zdały test, gdy zasięg tematów rozmowy jest ograniczony, żaden nie zrobił tego w rozmowie bez ograniczeń.