Kompletność Turinga
Z Wikipedii
W teorii obliczalności o maszynie lub języku programowania mówimy, że jest kompletny w sensie Turinga lub zupełny, jeśli można 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 lub maszyna potrafi wykonać lub 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.
Spis treści |
[edytuj] Znaczenie
Kompletność Turinga jest jedną z najważniejszych teoretycznych podstaw informatyki. Dzięki niej możliwe jest porównywanie możliwości różnych 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ż jednocześ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 obecnie 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, ponieważ języki niskiego poziomu, którymi posługują się procesory są zupełne. Istnieją natomiast - i 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 nigdy nie został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 i uruchomionego w 1941 roku w Berlinie przez Konrada Zuse.
Przerwa mię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. Zobacz artykuł Teoria obliczalności, aby znaleźć listę modeli zupełnych w sensie Turinga, modeli o mniejszych możliwościach oraz teoretycznych, znacznie potężniejszych modeli.
[edytuj] 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 lub 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 istnieją problemy rozwiązywalne w językach zupełnych, a które nie mają rozwiązania w językach udostępniających jedynie skończone pętle, tzn. gwarantujących, że program się zatrzyma.
[edytuj] Przykłady
Zupełne w sensie Turinga modele obliczeniowe tworzone 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. Niektóre z takich modeli to:
Większość 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 programowania wykorzystują nierzadko diametralnie różne środki, aby osiągnąć kompletność Turinga. FORTRAN używa w tym celu pętli lub nawet komend GOTO. Haskell i Prolog, niemal zupełnie 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, ponieważ nie są one powszechne. Przykładami są 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.
[edytuj] Bibliografia
- D. Harel, Rzecz o istocie informatyki, Warszawa, 1992, ISBN 83-204-2506-9
