kompletność Turinga - Turing completeness

W teorii obliczalności system reguł manipulacji danymi (taki jak zestaw instrukcji komputera , język programowania lub automat komórkowy ) jest uważany za kompletny pod względem Turinga lub uniwersalny obliczeniowo, jeśli może być użyty do symulacji dowolnej maszyny Turinga . Oznacza to, że ten system jest w stanie rozpoznawać lub decydować o innych zestawach reguł manipulacji danymi. Kompletność Turinga jest używana jako sposób wyrażenia mocy takiego zestawu reguł manipulacji danymi. Praktycznie wszystkie dzisiejsze języki programowania są zupełne pod względem Turinga. Koncepcja została nazwana na cześć angielskiego matematyka i informatyka Alana Turinga .

Pokrewną koncepcją jest równoważność Turinga  – dwa komputery P i Q są nazywane równoważnymi, jeśli P może symulować Q, a Q może symulować P. Teza Churcha-Turinga przypuszcza, że ​​każda funkcja, której wartości mogą być obliczone przez algorytm, może być obliczona przez Maszyna Turinga, a zatem jeśli jakikolwiek komputer w świecie rzeczywistym może symulować maszynę Turinga, jest to odpowiednik Turinga maszyny Turinga. Uniwersalna maszyna Turinga może być używany do symulacji każdą maszynę Turinga, a co za tym idzie obliczeniowe aspekty ewentualnego komputera w świecie rzeczywistym.

Aby pokazać, że coś jest zupełne pod względem Turinga, wystarczy pokazać, że można go użyć do symulacji jakiegoś systemu z kompletnością Turinga. Na przykład język imperatywny jest Turing-kompletny, jeśli ma warunkowe rozgałęzienia (np. instrukcje „if” i „goto” lub instrukcję „gałąź, jeśli zero”; patrz komputer z jednym zestawem instrukcji ) i możliwość zmiany dowolnego ilość pamięci (np. możliwość utrzymywania dowolnej liczby elementów danych). Oczywiście żaden system fizyczny nie może mieć nieskończonej pamięci; ale jeśli zignoruje się ograniczenie pamięci skończonej, większość języków programowania jest w przeciwnym razie zupełna pod względem Turinga.

Użycie niematematyczne

W potocznym użyciu terminy „kompletny Turinga” i „równoważnik Turinga” oznaczają, że każdy komputer ogólnego przeznaczenia lub język komputerowy w świecie rzeczywistym może w przybliżeniu symulować obliczeniowe aspekty dowolnego innego komputera ogólnego przeznaczenia w świecie rzeczywistym lub język komputerowy.

Prawdziwe komputery skonstruowane do tej pory mogą być analizowane funkcjonalnie jak jednotaśmowa maszyna Turinga ("taśma" odpowiadająca ich pamięci); w ten sposób powiązana matematyka może być zastosowana poprzez abstrahowanie ich działania wystarczająco daleko. Jednak prawdziwe komputery mają ograniczone zasoby fizyczne, więc są tylko kompletnym automatem liniowo ograniczonym . W przeciwieństwie do tego, uniwersalny komputer jest definiowany jako urządzenie z kompletnym zestawem instrukcji Turinga, nieskończoną pamięcią i nieskończonym dostępnym czasem.

Formalne definicje

W teorii obliczalności stosuje się kilka ściśle powiązanych terminów do opisania mocy obliczeniowej systemu obliczeniowego (takiego jak abstrakcyjna maszyna lub język programowania ):

kompletność Turinga
System obliczeniowy, który może obliczyć każdą obliczalną funkcję Turinga, nazywa się Turing-kompletny (lub Turing-potężny). Alternatywnie taki system to taki, który może symulować uniwersalną maszynę Turinga .
Równoważność Turinga
Kompletny system Turinga nazywa się równoważnikiem Turinga, jeśli każda funkcja, którą może obliczyć, jest również obliczalna według Turinga; tzn. oblicza dokładnie tę samą klasę funkcji, co maszyny Turinga . Alternatywnie, system równoważny Turingowi to taki, który może symulować i być symulowany przez uniwersalną maszynę Turinga. (Wszystkie znane fizycznie możliwe do wdrożenia systemy kompletnego Turinga są ekwiwalentem Turinga, co stanowi poparcie dla tezy Churcha-Turinga ).
(obliczeniowa) uniwersalność
System jest nazywany uniwersalnym w odniesieniu do klasy systemów, jeśli może obliczyć każdą funkcję obliczalną przez systemy w tej klasie (lub może symulować każdy z tych systemów). Zazwyczaj termin uniwersalność jest milcząco używany w odniesieniu do kompletnej klasy systemów Turinga. Terminem „słabo uniwersalny” używa się czasem do odróżnienia systemu (np. automatu komórkowego ), którego uniwersalność osiąga się jedynie poprzez modyfikację standardowej definicji maszyny Turinga tak, aby obejmowała strumienie wejściowe o nieskończenie wielu jedynkach.

Historia

Kompletność Turinga jest znacząca, ponieważ każdy projekt urządzenia komputerowego w świecie rzeczywistym może być symulowany przez uniwersalną maszynę Turinga . The Church-Turinga teza stwierdza, że jest to prawo matematyki - to uniwersalna maszyna Turinga może w zasadzie wykonywać żadnych obliczeń, że każdy inny programowalny komputer może. Nie mówi to nic o wysiłku potrzebnym do napisania programu , ani o czasie, jaki może zająć maszynie wykonanie obliczeń, ani o jakichkolwiek zdolnościach, które może posiadać maszyna, które nie mają nic wspólnego z obliczeniami.

Charles Babbage „s silnik analityczny (1830) byłaby pierwsza maszyna Turinga-zupełny, jeśli został zbudowany w czasie którego został zaprojektowany. Babbage doceniał to, że maszyna była zdolna do wielkich obliczeń, w tym prymitywnego logicznego rozumowania, ale nie doceniał, że żadna inna maszyna nie może zrobić lepiej. Od lat trzydziestych XIX wieku do lat czterdziestych XX wieku budowano i ulepszano mechaniczne maszyny liczące, takie jak sumatory i mnożniki, ale nie mogły one wykonać gałęzi warunkowej, a zatem nie były kompletne pod względem Turinga.

Pod koniec XIX wieku Leopold Kronecker sformułował pojęcia obliczalności, definiując pierwotne funkcje rekurencyjne . Funkcje te można obliczyć za pomocą obliczeń rotacyjnych, ale nie wystarczą one do stworzenia uniwersalnego komputera, ponieważ instrukcje, które je obliczają, nie pozwalają na nieskończoną pętlę. Na początku XX wieku David Hilbert poprowadził program aksjomatyzujący całą matematykę za pomocą precyzyjnych aksjomatów i precyzyjnych logicznych reguł dedukcji, które mogą być wykonywane przez maszynę. Wkrótce stało się jasne, że mały zestaw reguł dedukcji wystarczy, aby wytworzyć konsekwencje dowolnego zestawu aksjomatów. Te reguły zostały udowodnione przez Kurta Gödla w 1930 roku, aby były wystarczające do sformułowania każdego twierdzenia.

Właściwe pojęcie obliczeń zostało wyizolowane wkrótce potem, zaczynając od twierdzenia Gödla o niezupełności . Twierdzenie to pokazało, że systemy aksjomatów były ograniczone podczas wnioskowania o obliczeniach, które wyprowadzają ich twierdzenia. Church i Turing niezależnie wykazali, że Entscheidungsproblem Hilberta (problem decyzyjny) był nierozwiązywalny, identyfikując tym samym rdzeń obliczeniowy twierdzenia o niezupełności. Ta praca, wraz z pracą Gödla nad ogólnymi funkcjami rekurencyjnymi , wykazała, że ​​istnieją zestawy prostych instrukcji, które po złożeniu są w stanie wykonać dowolne obliczenia. Praca Gödla pokazała, że ​​pojęcie obliczeń jest zasadniczo unikalne.

W 1941 Konrad Zuse ukończył komputer Z3 . Zuse nie znał wówczas prac Turinga dotyczących obliczalności. W szczególności Z3 brakowało dedykowanych urządzeń do skoku warunkowego, co uniemożliwiało ukończenie Turinga. Jednak w 1998 roku Rojas pokazał, że Z3 jest zdolny do warunkowych skoków, a zatem Turinga jest kompletny, wykorzystując niektóre jego funkcje w niezamierzony sposób.

Teoria obliczalności

Teoria obliczalności wykorzystuje modele obliczeń do analizy problemów i określenia, czy są one obliczalne iw jakich okolicznościach. Pierwszym rezultatem teorii obliczalności jest to, że istnieją problemy, dla których nie można przewidzieć, co system (z pełnym Turingiem) zrobi w arbitralnie długim czasie.

Klasycznym przykładem jest problem zatrzymania : stwórz algorytm, który pobiera jako dane wejściowe program w jakimś języku z pełną Turinga i pewne dane, które mają być wprowadzone do tego programu, i określa, czy program, operujący na wejściu, ostatecznie się zatrzyma, czy będzie kontynuował na zawsze. Stworzenie algorytmu, który może to zrobić dla niektórych danych wejściowych, jest trywialne , ale generalnie jest to niemożliwe. Dla jakiejkolwiek cechy wyjściowej programu nie można określić, czy ta cecha będzie się utrzymywać.

Ta niemożliwość stwarza problemy podczas analizy programów komputerowych w świecie rzeczywistym. Na przykład nie można napisać narzędzia, które całkowicie chroni programistów przed pisaniem nieskończonych pętli lub chroni użytkowników przed dostarczaniem danych wejściowych, które powodowałyby nieskończone pętle.

Zamiast tego można ograniczyć program do wykonywania tylko przez określony czas ( timeout ) lub ograniczyć moc instrukcji sterujących przepływem (na przykład, zapewniając tylko pętle, które iterują elementy istniejącej tablicy). Jednak inne twierdzenie pokazuje, że istnieją problemy, które można rozwiązać za pomocą języków z kompletnością Turinga, których nie można rozwiązać za pomocą żadnego języka posiadającego tylko skończone możliwości zapętlania (tj. dowolny język gwarantujący, że każdy program w końcu się zatrzyma). Zatem żaden taki język nie jest zupełny pod względem Turinga. Na przykład język, w którym gwarantuje się zakończenie i zatrzymanie programów, nie może obliczyć funkcji obliczalnej utworzonej przez argument przekątny Cantora dla wszystkich funkcji obliczalnych w tym języku.

wyrocznie Turinga

Komputer z dostępem do nieskończonej taśmy danych może być potężniejszy niż maszyna Turinga: na przykład taśma może zawierać rozwiązanie problemu zatrzymania lub innego nierozstrzygalnego problemu Turinga. Taka nieskończona taśma danych nazywana jest wyrocznią Turinga . Nawet wyrocznia Turinga z losowymi danymi nie jest obliczalna ( z prawdopodobieństwem 1 ), ponieważ istnieje tylko przeliczalnie wiele obliczeń, ale nieprzeliczalnie wiele wyroczni. Tak więc komputer z losową wyrocznią Turinga może obliczyć rzeczy, których maszyna Turinga nie może.

Fizyka cyfrowa

Wszystkie znane prawa fizyki mają konsekwencje, które można obliczyć za pomocą szeregu przybliżeń na komputerze cyfrowym. Hipoteza zwana fizyką cyfrową stwierdza, że ​​nie jest to przypadek, ponieważ sam wszechświat jest obliczalny na uniwersalnej maszynie Turinga. Oznaczałoby to, że nie można fizycznie zbudować żadnego komputera o większej mocy niż uniwersalna maszyna Turinga.

Przykłady

Systemy obliczeniowe (algebry, rachunki), które są omawiane jako systemy Turinga, są przeznaczone do studiowania teoretycznej informatyki . Mają być tak proste, jak to tylko możliwe, aby łatwiej było zrozumieć granice obliczeń. Tu jest kilka:

Większość języków programowania (ich abstrakcyjne modele, być może z pewnymi konkretnymi konstrukcjami, które zakładają pominięcie skończonej pamięci), konwencjonalnych i niekonwencjonalnych, jest zupełna pod względem Turinga. To zawiera:

Niektóre systemy przepisywania są kompletne pod względem Turinga.

Kompletność Turinga jest abstrakcyjnym stwierdzeniem umiejętności, a nie przepisem na określone cechy języka używane do wdrożenia tej umiejętności. Funkcje używane do osiągnięcia kompletności Turinga mogą być zupełnie inne; Systemy Fortranu używałyby konstrukcji pętli, a nawet instrukcji goto , aby osiągnąć powtórzenie; Haskell i Prolog, prawie całkowicie pozbawiony pętli, używaliby rekurencji . Większość języków programowania opisuje obliczenia na architekturach von Neumanna , które mają pamięć (RAM i rejestr) i jednostkę sterującą. Te dwa elementy czynią tę architekturę Turinga kompletną. Nawet czysto funkcjonalne języki są zupełne pod względem Turinga.

Kompletność Turinga w deklaratywnym SQL jest zaimplementowana za pomocą rekurencyjnych wyrażeń tabelowych . Nic dziwnego, że proceduralne rozszerzenia SQL ( PLSQL , itp.) są również zgodne z Turingiem . Ilustruje to jeden z powodów, dla których stosunkowo potężne języki niekompletne Turinga są rzadkie: im silniejszy jest język początkowo, tym bardziej złożone są zadania, do których jest stosowany, i tym szybciej jego brak kompletności staje się postrzegany jako wada, zachęcająca do rozszerzenie aż do Turinga-ukończenia.

Rachunek lambda bez typu jest Turing-kompletny, ale wiele typów rachunków lambda, w tym System F , nie jest. Wartość systemów typowanych opiera się na ich zdolności do reprezentowania większości typowych programów komputerowych przy wykrywaniu większej liczby błędów.

Reguła 110 i Gra w życie Conwaya , oba automaty komórkowe , są kompletne pod względem Turinga.

Niezamierzona kompletność Turinga

Niektóre gry i inne oprogramowanie są kompletne pod względem Turinga przez przypadek, tj. nie przez projekt.

Oprogramowanie:

Gry wideo:

Media społecznościowe:

Gry karciane:

Gry zero-osobowe (symulacje):

Języki obliczeniowe:

Sprzęt komputerowy:

  • Instrukcja MOV x86

Biologia:

  • Wykazano, że sieci reakcji chemicznych i komputery DNA oparte na enzymach są równoważne z Turingiem

Języki niepełne Turinga

Istnieje wiele języków obliczeniowych, które nie są zupełne pod względem Turinga. Jednym z takich przykładów jest zbiór języków regularnych , które są generowane przez wyrażenia regularne i które są rozpoznawane przez automaty skończone . Potężniejszym, ale wciąż niepełnym Turinga rozszerzeniem automatów skończonych jest kategoria automatów ze stosem i gramatyk bezkontekstowych , które są powszechnie używane do generowania drzew analizy w początkowej fazie kompilacji programu . Dalsze przykłady obejmują niektóre z wczesnych wersji języków shaderów pikseli osadzonych w rozszerzeniach Direct3D i OpenGL .

We wszystkich funkcjonalnych językach programowania , takich jak Charity i Epigram , wszystkie funkcje są całkowite i muszą się zakończyć. Charity używa systemu typów i konstrukcji kontrolnych opartych na teorii kategorii , podczas gdy Epigram używa typów zależnych . Język LOOP został zaprojektowany tak, aby obliczał tylko te funkcje, które są prymitywne rekurencyjne . Wszystkie te obliczają właściwe podzbiory wszystkich funkcji obliczalnych, ponieważ pełny zestaw wszystkich funkcji obliczalnych nie jest przeliczalny . Ponadto, ponieważ wszystkie funkcje w tych językach są całkowite, algorytmy dla zbiorów rekurencyjnie przeliczalnych nie mogą być zapisywane w tych językach, w przeciwieństwie do maszyn Turinga.

Chociaż (nieopisany) rachunek lambda jest kompletny według Turinga, po prostu typowany rachunek lambda nie jest.

Języki danych

Pojęcie kompletności Turinga nie ma zastosowania do języków takich jak XML , HTML , JSON i YAML , ponieważ są one zwykle używane do reprezentowania danych strukturalnych, a nie do opisywania obliczeń. Są one czasami określane jako języki znaczników , a dokładniej „języki kontenerów” lub „języki opisu danych”.

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Zewnętrzne linki