Co to jest Turing Complete?

Oto najprostsze wyjaśnienie

Alan Turing stworzył maszynę, która może wziąć program, uruchomić go i pokazać jakiś wynik. Ale potem musiał tworzyć różne maszyny dla różnych programów. Stworzył więc "uniwersalną maszynę Turinga", która może wziąć dowolny program i uruchomić go.

Języki programowania są podobne do tych maszyn (choć wirtualne). Biorą programy i uruchamiają je. Teraz język programowania nazywa się "Turing complete", jeśli można go uruchomić każdy program (niezależnie od języka), który maszyna Turinga może uruchomić, biorąc pod uwagę wystarczająco dużo czasu i pamięci.

Na przykład: załóżmy, że istnieje program, który pobiera 10 liczb i dodaje je. Maszyna Turinga może łatwo uruchomić ten program. Ale teraz wyobraź sobie, że z jakiegoś powodu twój język programowania nie może zrobić tego samego dodatku, a następnie jest to maszyna Turinga niekompletna. Z drugiej strony, jeśli może uruchomić dowolny program, taki jak uniwersalna maszyna Turinga, to jest to Turing kompletny.

Najbardziej nowoczesne języki programowania takie jak Java, JavaScript, Perl itp. są kompletne, ponieważ wszystkie implementują wszystkie funkcje wymagane do uruchamiania programów, takich jak dodawanie, mnożenie, warunek if-else, instrukcje return, sposoby przechowywania/pobierania/kasowania danych i tak dalej.

Aktualizacja: możesz dowiedzieć się więcej na moim blogu: "JavaScript is Turing Complete" - Explained

From wikipedia :

Turing, nazwany na cześć Alana Turinga, jest istotne w tym, że każdy / align = "left" / Linear urządzenie do tej pory zaawansowane można emulować przez uniwersalną maszynę Turinga-an obserwacja, która stała się znana jako teza Kościoła-Turinga. Tak więc, a maszyna, która może działać jako uniwersalny Maszyna Turinga może w zasadzie, wykonać wszelkie obliczenia, które Inne programowalny komputer jest w stanie. Jednak to nie ma nic do zrobienia z wysiłek potrzebny do napisania programu dla Maszyny, czas może zająć aby maszyna wykonała kalkulacji, lub dowolne umiejętności maszyna może posiadać niezwiązane ze sobą do obliczeń.

Podczas gdy prawdziwie Turing-kompletne maszyny są bardzo prawdopodobne fizycznie niemożliwe, ponieważ wymagają nieograniczonej przestrzeni dyskowej, Kompletność Turinga jest często luźno przypisane do maszyn fizycznych lub języki programowania, które byłyby uniwersalne, gdyby miały nieograniczone magazyn. Wszystkie nowoczesne komputery są Turing-kompletny w tym sensie.

Nie wiem, jak możesz być bardziej nietechniczny niż to, z wyjątkiem powiedzenia "turing kompletny oznacza' w stanie odpowiedzieć na problem obliczeniowy, biorąc pod uwagę wystarczająco dużo czasu i przestrzeni'".

Definicja Nieformalna

Kompletny język Turinga to taki, który może wykonywać dowolne obliczenia. Teza Churcha-Turinga stwierdza, że wszelkie możliwe obliczenia mogą być wykonane przez maszynę Turinga. Maszyna Turinga jest maszyną z nieskończoną pamięcią o dostępie losowym i skończonym 'programem', który dyktuje, kiedy powinna czytać, pisać i poruszać się po tej pamięci, kiedy powinna zakończyć się z określonym wynikiem i co powinna zrobić dalej. Wejście do maszyny Turinga jest zapamiętuj go, zanim się zacznie.

Rzeczy, które mogą sprawić, że język nie będzie kompletny

Maszyna Turinga może podejmować decyzje w oparciu o to, co widzi w pamięci - "język", który obsługuje tylko+, -, *, i / na liczbach całkowitych nie jest Turing kompletny, ponieważ nie może dokonać wyboru na podstawie swoich danych wejściowych, ale maszyna Turinga może.

Maszyna Turinga może działać w nieskończoność - jeśli weźmiemy Javę, Javascript lub Python i usuniemy możliwość wykonaj dowolne wywołanie pętli, GOTO lub funkcji, nie będzie to Turing kompletny, ponieważ nie może wykonać dowolnych obliczeń, które nigdy się nie kończą. Coq jest twierdzeniem, które nie może wyrażać programów, które nie kończą się, więc nie jest kompletne.

Język, który był podobny do Javy, ale kończyłby się po zużyciu więcej niż 4 gigabajtów pamięci, nie byłby kompletny, ponieważ maszyna Turinga może używać nieskończona pamięć. Dlatego nie możemy zbudować maszyny Turinga, ale Java nadal jest kompletnym językiem Turinga, ponieważ język Java {41]} {42]} nie ma żadnych ograniczeń uniemożliwiających korzystanie z nieskończonej pamięci. Jest to jeden z powodów, dla których wyrażenia regularne nie są kompletne.

Maszyna Turinga ma pamięć o dostępie losowym - język, który pozwala pracować z pamięcią tylko przez operacje push i pop do stosu, który nie byłby kompletny. Jeśli mam "język", który odczytuje łańcuch raz i może używać pamięci tylko przez popychanie i wyskakiwanie ze stosu, może mi powiedzieć, czy każdy ( w łańcuchu ma swój własny ) później, naciskając, gdy widzi ( i popping, gdy widzi ). Jednak nie może mi powiedzieć, czy każdy ( ma swoje własne ) później i każdy [ ma swoje własne ] później (zauważ, że ([)] spełnia te kryteria, ale ([]] nie). Maszyna Turinga może wykorzystać swoją pamięć dostępu losowego do śledzenia ()'S I []' s oddzielnie, ale ten język z tylko stosem nie może.

Maszyna Turinga może symulować dowolną inną maszynę Turinga - maszyna Turinga, gdy otrzyma odpowiedni "program", może pobrać "program" innej maszyny Turinga i symulować go na dowolnym wejściu. Gdybyś miał język, któremu zabroniono implementacji interpretera Pythona, nie byłby to Turing kompletny.

Przykłady języków Turinga

Jeśli twój język ma nieskończona pamięć o dostępie losowym, warunkowe wykonanie i jakaś forma powtarzania wykonania, to pewnie Turing kompletny. Istnieją bardziej egzotyczne systemy, które mogą osiągnąć wszystko, co może osiągnąć maszyna Turinga, co sprawia, że Turing również jest kompletny]}

• Untyped lambda calculus
• Conway ' s game of life
• Szablony C++
• Prolog

Zasadniczo, Turing-kompletność jest jednym zwięzłym wymogiem, nieograniczoną rekurencją.

Nawet nie ograniczone pamięcią.

Myślałem o tym niezależnie, ale Oto jakaś dyskusja twierdzenia. moja definicja LSP dostarcza więcej kontekstu.

Inne odpowiedzi tutaj nie definiują bezpośrednio fundamentalnej istoty Turinga-kompletności.

Turing kompletny oznacza, że jest co najmniej tak samo potężny jak maszyna Turinga . Oznacza to, że wszystko, co może być obliczone przez maszynę Turinga, może być obliczone przez kompletny system Turinga.

Nikt jeszcze nie znalazł systemu potężniejszego niż maszyna Turinga. Na razie twierdzenie, że system jest kompletny Turinga jest tym samym, co twierdzenie, że system jest tak potężny ,jak każdy znany system obliczeniowy (zobacz teza Churcha-Turinga ).

Najprościej mówiąc, kompletny system Turinga może rozwiązać każdy możliwy problem obliczeniowy.

Jednym z kluczowych wymagań jest rozmiar scratchpad być nieograniczony i że jest możliwe do przewinięcia, aby uzyskać dostęp do wcześniejszych zapisów do scratchpad.

Tak więc w praktyce żaden system nie jest Turing-kompletny.

Raczej niektóre systemy przybliżają kompletność Turinga poprzez modelowanie nieograniczonej pamięci i wykonywanie wszelkich możliwych obliczeń, które mogą zmieścić się w pamięci systemu.

Myślę, że znaczenie pojęcia "Turing Complete" polega na zdolności do identyfikacji maszyny obliczeniowej (niekoniecznie mechanicznego / elektrycznego "komputera"), która może dekonstruować swoje procesy w "proste" instrukcje, złożone z prostszych i prostszych instrukcji, które Uniwersalna maszyna może zinterpretować, a następnie wykonać.

Gorąco polecam notowany Turing

@ Mark myślę, że to co wyjaśniasz to mieszanka opisu uniwersalnego Maszyna Turinga i Turinga w komplecie.

Czymś, co jest kompletnym Turingiem, w sensie praktycznym, byłaby maszyna / proces/obliczenia mogące być napisane i reprezentowane jako program, do wykonania przez uniwersalną maszynę (komputer stacjonarny). Chociaż nie bierze pod uwagę czasu ani przechowywania, jak wspominają inni.

As Waylon Flinn said :

Turing kompletny oznacza, że jest co najmniej tak potężny jak maszyna Turinga.

Uważam, że jest to niepoprawne, system jest kompletny, jeśli jest dokładnie tak potężny jak maszyna Turinga, tzn. każde obliczenia wykonywane przez maszynę mogą być wykonane przez system, ale także każde obliczenia wykonywane przez system mogą być wykonane przez maszynę Turinga.

W praktycznym języku znanym większości programistów, typowym sposobem wykrywania kompletności Turinga jest to, czy język pozwala Lub pozwala na symulację zagnieżdżonych, nieograniczonych poleceń while (W przeciwieństwie do poleceń w stylu Pascal, ze stałymi wyższymi granicami).

Czy relacyjna baza danych może wprowadzić szerokości i długości geograficzne miejsc i dróg oraz obliczyć najkrótszą ścieżkę między nimi-nie. Jest to jeden problem, który pokazuje, że SQL nie jest Turing kompletny.

Ale C++ potrafi to zrobić i potrafi zrobić każdy problem. Tak jest.