Kompletność Turinga

Kompletność Turinga – cecha systemu przetwarzającego dane lub języka programowania, polegająca na tym, że 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, maszyna lub inny system 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.

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 sensie 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.

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.

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 wykorzystujące mniej popularne paradygmaty:
  • okazuje się nawet, że pojedyncza instrukcja kopiowania danych procesorów rodziny x86 (mov cel,źródło) jest zupełna w sensie Turinga tzn. nie trzebeba używać innych instrukcji procesora by zakodować dowolny program który może wykonać maszyna Turinga[1] (istnieją kompilatory kompilujące kod C na kod procesora będący ciągem jedynie instrukcji mov[2])
  • automat komórkowy "reguła 110" potrafi wykonać dowolny algorytm (wykonywalny na maszynie Turinga) co zostało udowodnione w 2004r. przez Matthew Cooka[3]. To odkrycie ma ciekawe konsekwnecje np. ponieważ HTML5+CSS3 pozwala zaimplementować "regułę 110" (w sposób półautomatyczny gdyż wymagane jest pewne mechaniczne działanie użytkownika tj. naciskanie tab+spacja) więc wynika z tego że defacto za pomocą tych technologii możliwe jest wykonanie dowolnego algorytmu jaki może wykonać maszyna Turinga.

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ą SQL i 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.

Zobacz też

Przypisy

  1. ↑ Stephen Dolan: mov is Turing-complete. Computer Laboratory, University of Cambridg, 2013-07-19. (ang.).
  2. ↑ Christopher Domas: Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare. Derbycon 2015. (ang.).
  3. ↑ Matthew Cook: Universality in Elementary Cellular Automata. Complex Systems, 2004. (ang.).

Bibliografia

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