W teorii obliczalności o maszynie albo języku programowania mówimy, że jest kompletny w sensie Turinga albo zupełny, jeśli da się za jego pomocą rozwiązać identyczną klasę problemów obliczeniowych, jak na uproszczonym modelu programowalnego komputera zwanego maszyną Turinga. W praktyce oznacza to, że jeśli dany język albo maszyna potrafi wykonać albo wyrazić każdy algorytm, określany jest mianem zupełnego, przy czym nie jest wymagane, by algorytm ten realizowany był prosto, wydajnie bądź efektywnie.

Termin wywodzi się od nazwiska matematyka Alana Turinga, który jako pierwszy zaproponował model uniwersalnej maszyny Turinga.

Znaczenie

Kompletność Turinga jest jedną z najważniejszych teoretycznych podstaw informatyki. Dzięki niej możliwe jest porównywanie możliwości wielorakich projektów maszyn obliczeniowych. Jeżeli na zaproponowanym modelu obliczeniowym da się zasymulować uniwersalną maszynę Turinga, oznacza to, że jest on w stanie rozwiązać taką samą ilość problemów algorytmicznych, jak inne modele. Próba implementacji maszyny Turinga na takim modelu jest też równocześnie dowodem jego kompletności. Kompletność Turinga wynika z niemożliwej do udowodnienia hipotezy Churcha-Turinga.

Maszyna Turinga jest modelem wyidealizowanym, niemożliwym do skonstruowania ze względu na konieczność posiadania nieskończonej pamięci. Ograniczenie zasobów cechuje wszystkie istniejące aktualnie komputery, dlatego terminu kompletność Turinga używa się w odniesieniu do nich w znaczeniu, że byłyby one kompletne, gdyby posiadały nielimitowaną ilość zasobów. Zgodnie z tym rozumowaniem, wszystkie obecne komputery są zupełne w sensie Turinga - jest tak, albowiem języki niskiego poziomu, którymi posługują się procesory są zupełne. Istnieją natomiast - oraz to też jest oczywiste - języki programowania, które nie są zupełne w sense Turinga, przykładem jest język SQL.

Pierwszym projektem komputera zupełnego w sensie Turinga była maszyna analityczna zaproponowana w 1837 roku przez angielskiego matematyka Charlesa Babbage'a, lecz wcale nie była ona zbudowana. Do niedawna uważano, że pierwszym działającym zupełnym komputerem był amerykański ENIAC uruchomiony w 1944, jednak w 1998 roku Raúl Rojas udowodnił kompletność niemieckiego komputera Z3, zbudowanego oraz uruchomionego w 1941 roku w Berlinie przez Konrada Zuse.

Przerwa pomiędzy rokiem 1837 a 1941 nie była czasem systematycznego rozwoju mechanicznego komputera. Znaczący rozwój komputerów nastąpił dopiero po opracowaniu we wczesnych latach 30. XX wieku matematycznych sposobów wyrażania problemów obliczeniowych oraz pierwszych języków formalnych.

Istnieje hipoteza mówiąca, że cały wszechświat jest zupełny w sensie Turinga. Oznaczałoby to, że niemożliwe jest zbudowanie maszyny potężniejszej, niż uniwersalna maszyna Turinga oraz podobne do niej. Sprawdź artykuł Teoria obliczalności, aby znaleźć listę modeli zupełnych w sensie Turinga, modeli o mniejszych możliwościach oraz teoretycznych, wydatnie potężniejszych modeli.

Powiązane zagadnienia

Ważnym wnioskiem płynącym z teorii obliczalności jest niemożliwość określenia w ogólnym przypadku, czy dany program zatrzyma się dla wszystkich możliwych danych, czy też będzie wykonywać się w nieskończoność (tzw. problem stopu). Jedną z powszechnych metod radzenia sobie z problemem jest wymuszenie zatrzymania się po określonym czasie albo ograniczenie mocy instrukcji przepływu sterowania w programie, jednak takie systemy nie są zupełne w sensie Turinga.

Kolejnym interesującym zagadnieniem związanym z kompletnością jest fakt, że są problemy rozwiązywalne w językach zupełnych, a które nie posiadają rozwiązania w językach udostępniających zaledwie skończone pętle, tzn. gwarantujących, że program się zatrzyma.

Przykłady

Zupełne w sensie Turinga modele obliczeniowe wykonywane są do prac z dziedziny teorii obliczeń. Charakteryzują się one bardzo prostą konstrukcją tak, aby ograniczenia obliczalności były lepiej widoczne oraz łatwiejsze w matematycznym opisie. Pewne z takich modeli to:

• maszyna Turinga
• rachunek lambda
• system półthueowski

Przeważajaca ilość języków programowania jest zupełna w sensie Turinga. Włączone są w to:

• wszystkie języki ogólnego przeznaczenia, np.
  • języki proceduralne, np. C
  • języki obiektowe, np. Java
  • języki wieloparadygmatowe, np. Ada, C++, Common Lisp
• języki wykorzystujące mniej popularne paradygmaty:
  • języki funkcyjne, np. Haskell
  • języki logiczne, np. Prolog
  • języki deklaratywne, np. XSLT

Języki programowania wykorzystują nierzadko diametralnie zróżnicowane środki, aby osiągnąć kompletność Turinga. FORTRAN używa w tym celu pętli albo nawet komend GOTO. Haskell oraz Prolog, prawie całkowicie pozbawione pętli, korzystają z rekurencji. Kompletność Turinga jest tylko pewną własnością, lecz nie daje żadnego przepisu, jak ją osiągnąć.

Niezwykle trudno jest znaleźć języki niebędące zupełnymi, albowiem nie są one powszechne. Przykładami są SQL oraz wczesne języki programowania shaderów w DirectX oraz OpenGL. W najpowszechniejszym użyciu są wyrażenia regularne będące rodzajem automatów skończonych.

Bibliografia

• D. Harel, Rzecz o istocie informatyki, Warszawa, 1992, ISBN 83-204-2506-9

Sprawdź też

• hierarchia Chomsky'ego
• hipoteza Churcha-Turinga
• teoria obliczalności