Co to jest Turing Complete?

Co oznacza wyrażenie „Turing Complete”?

Czy możesz podać proste wyjaśnienie bez wchodzenia w zbyt wiele teoretycznych szczegółów?

Oto najkrótsze wyjaśnienie:

System Turing Complete oznacza system, w którym można napisać program, który znajdzie odpowiedź (choć bez gwarancji dotyczących czasu wykonywania lub pamięci).

Jeśli więc ktoś powie „moją nową rzeczą jest Turing Complete”, oznacza to w zasadzie (choć często nie w praktyce), że można go użyć do rozwiązania dowolnego problemu obliczeniowego.

Czasami to żart ... facet napisał symulator maszyny Turinga w vi, więc można powiedzieć, że vi jest jedynym silnikiem obliczeniowym, jakiego kiedykolwiek potrzebowano na świecie.

Oto najprostsze wyjaśnienie

Alan Turing stworzył maszynę, która może wziąć program, uruchomić ten program i pokazać jakiś wynik. Ale potem musiał stworzyć różne maszyny dla różnych programów. Stworzył więc „Uniwersalną maszynę Turinga”, która może wziąć KAŻDY program i uruchomić go.

Języki programowania są podobne do tych maszyn (choć wirtualne). Biorą programy i je uruchamiają. Teraz język programowania nazywa się „Turing zakończony”, jeśli może on uruchomić dowolny program (niezależnie od języka), który może uruchomić maszyna Turinga, mając wystarczającą ilość czasu i pamięci.

Na przykład: Załóżmy, że istnieje program, który pobiera 10 liczb i dodaje je. Maszyna Turinga może z łatwością uruchomić ten program. Ale teraz wyobraź sobie, że z jakiegoś powodu twój język programowania nie może wykonać tego samego dodania. To sprawiłoby, że „Turing byłby niepełny” (że tak powiem). Z drugiej strony, jeśli można uruchomić dowolny program, który może uruchomić uniwersalna maszyna Turinga, oznacza to, że Turing jest ukończony.

Większość współczesnych języków programowania (np. Java, JavaScript, Perl itp.) Jest w pełni ukończona, ponieważ każdy z nich implementuje wszystkie funkcje wymagane do uruchamiania programów, takie jak dodawanie, mnożenie, warunek if-else, instrukcje zwrotne, sposoby przechowywania / pobierania / usuwania dane i tak dalej.

Aktualizacja: Możesz dowiedzieć się więcej na moim blogu: „JavaScript jest ukończona Turing” - wyjaśnienie

Z wikipedii :

Kompletność Turinga, nazwana na cześć Alana Turinga, jest znacząca w tym, że każdy wiarygodny projekt urządzenia komputerowego tak zaawansowanego może być naśladowany przez uniwersalną maszynę Turinga - spostrzeżenie, które stało się znane jako teza Kościoła. Zatem maszyna, która może działać jak uniwersalna maszyna Turinga, może w zasadzie wykonać dowolne obliczenia, do których zdolny jest każdy inny programowalny komputer. Nie ma to jednak nic wspólnego z wysiłkiem wymaganym do napisania programu dla maszyny, czasem potrzebnym na wykonanie obliczeń przez maszynę, ani żadnymi zdolnościami, które maszyna może posiadać, niezwiązanymi z obliczeniami.

Chociaż maszyny z pełnym wyposażeniem Turing są najprawdopodobniej fizycznie niemożliwe, ponieważ wymagają nieograniczonej pamięci, kompletność Turinga jest często luźno przypisywana maszynom fizycznym lub językom programowania, które byłyby uniwersalne, gdyby miały nieograniczoną pamięć. Wszystkie nowoczesne komputery są w tym sensie kompletne Turinga.

Nie wiem, jak możesz być bardziej nietechniczny, niż mówiąc: „Turing Complete oznacza„ być w stanie odpowiedzieć na problem obliczeniowy, mając wystarczająco dużo czasu i miejsca ”.

Nieformalna definicja

Kompletny język Turinga to taki, który może wykonywać dowolne obliczenia. The Church-Turinga Thesis stwierdza, że wszelkie wykonalne obliczenia mogą być wykonywane przez maszynę Turinga. Maszyna Turinga to maszyna o nieskończonej pamięci o dostępie swobodnym i „programu” skończonego dyktuje kiedy powinien czytać, pisać i przesuwający się wzdłuż tej pamięci, kiedy powinien wypowiedzieć z pewnym wyniku, a co ma robić dalej. Dane wejściowe do maszyny Turinga są zapisywane w pamięci przed jej uruchomieniem.

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

Maszynie Turinga może podejmować decyzje w oparciu o to, co widzi w pamięci - „język”, który obsługuje tylko +, -, *, i /na całkowite Turinga nie jest kompletna, ponieważ nie można dokonać wyboru w oparciu o jego wejściu, ale maszyna Turinga może.

Maszyna Turinga może działać wiecznie - jeśli weźmiemy Java, JavaScript lub Python i usuniemy możliwość wykonywania dowolnego rodzaju pętli, GOTO lub wywołania funkcji, nie będzie to Turing zakończony, ponieważ nie może wykonać dowolnego obliczenia, które nigdy nie kończy. Coq jest twierdzeniem twierdzącym, że nie potrafi wyrazić programów, które się nie kończą, więc nie jest kompletny.

Maszyna Turinga może korzystać z pamięci nieskończonej - język, który byłby dokładnie taki jak Java, ale zakończyłby się, gdyby użył więcej niż 4 gigabajtów pamięci, nie byłby kompletny, ponieważ maszyna Turinga może używać pamięci nieskończonej. Właśnie dlatego nie możemy zbudować maszyny Turinga, ale Java jest nadal kompletnym językiem Turinga, ponieważ język Java 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 w Turingu.

Maszyna Turinga ma pamięć o swobodnym dostępie - język, który pozwala tylko pracować z pamięcią, pusha popoperacje na stosie nie byłyby kompletne. Jeśli mam „język”, który odczytuje ciąg raz i może używać pamięci tylko poprzez wypychanie i wyskakiwanie ze stosu, może mi powiedzieć, czy każdy (ciąg ma swój własny )później, pchając, gdy widzi, (i wyskakując, gdy widzi ). Jednak nie może mi powiedzieć, czy każdy (ma swój własny )później i każdy [ma swój własny ]później (pamiętaj, że ([)]spełnia te kryteria, ale ([]]nie spełnia). Maszyna Turinga może wykorzystywać swoją pamięć o swobodnym dostępie do śledzenia ()i[]jest osobno, ale ten język z tylko stosem nie może.

Maszyna Turinga może symulować dowolną inną maszynę Turinga - Maszyna Turinga, jeśli otrzyma odpowiedni „program”, może pobrać „program” innej maszyny Turinga i przeprowadzić symulację na dowolnym wejściu. Jeśli posiadasz język, który nie może implementować interpretera Pythona, nie byłby to kompletny Turing.

Przykłady kompletnych języków Turinga

Jeśli twój język ma nieskończoną pamięć o swobodnym dostępie, wykonanie warunkowe i jakąś formę powtarzanego wykonania, prawdopodobnie Turing jest ukończony. Istnieje więcej egzotycznych systemów, które wciąż mogą osiągnąć wszystko, co może zrobić maszyna Turinga, co czyni je również kompletnymi:

• Rachunek lambda bez typu
• Gra Conwaya w życie
• Szablony C ++
• Prolog

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

Nawet nie związany pamięcią.

Myślałem o tym niezależnie, ale oto dyskusja na temat tego twierdzenia. Moja definicja LSP zapewnia większy kontekst.

Pozostałe odpowiedzi tutaj nie definiują bezpośrednio podstawowej istoty kompletności Turinga.

Turing Complete oznacza, że ​​jest co najmniej tak potężny jak Maszyna Turinga . Oznacza to, że wszystko, co można obliczyć za pomocą maszyny Turinga, można obliczyć za pomocą systemu Turing Complete.

Nikt jeszcze nie znalazł systemu o większej mocy niż Maszyna Turinga. Na razie więc powiedzenie, że system jest Turing Complete, jest tym samym, co powiedzenie, że system jest tak potężny, jak każdy znany system komputerowy (patrz teza Churcha-Turinga ).

Mówiąc najprościej, system Turing-complete może rozwiązać każdy możliwy problem obliczeniowy.

Jednym z kluczowych wymagań jest nieograniczony rozmiar scratchpada i możliwe jest przewijanie w celu uzyskania dostępu do wcześniejszych zapisów na scratchpad.

Dlatego w praktyce żaden system nie jest kompletny w Turingu.

Raczej niektóre systemy przybliżają kompletność Turinga, modelując pamięć niezwiązaną i wykonując wszelkie możliwe obliczenia, które mieszczą się w pamięci systemu.

Myślę, że znaczenie pojęcia „Turing Complete” polega na zdolności do identyfikacji maszyny komputerowej (niekoniecznie mechanicznej / elektrycznej „komputera”), której procesy można przekształcić w „proste” instrukcje, złożone z prostszych i prostszych instrukcje, które maszyna Universal może zinterpretować, a następnie wykonać.

Bardzo polecam The Adnotated Turing

@ Mark Myślę, że to, co wyjaśniasz, jest mieszanką opisu Universal Turing Machine i Turing Complete.

Coś, co jest Turing Complete, w sensie praktycznym, byłoby maszyną / procesem / obliczeniem, które można zapisać i przedstawić jako program do wykonania przez maszynę uniwersalną (komputer stacjonarny). Chociaż nie bierze pod uwagę czasu ani miejsca przechowywania, jak wspomniali inni.

Co rozumiem w prostych słowach:

Turing Complete: język programowania / program, który może wykonywać obliczenia, jest Turing zakończony.

Na przykład :

1. Czy możesz dodać dwie liczby za pomocą samego HTML . (Odpowiedź brzmi „ Nie ”, aby wykonać dodawanie, musisz użyć javascript). Dlatego HTML nie jest Turing Complete.

2. Języki takie jak Java, C ++, Python, JavaScript, Solidity for Ethereum itp. Są Turing Complete, ponieważ możesz wykonywać obliczenia, takie jak dodawanie dwóch liczb za pomocą tych języków.

Mam nadzieję że to pomoże.

Jest kompletny, jeśli może testować i rozgałęziać się (ma „if”)

Maszyna Turinga wymaga, aby każdy program mógł przeprowadzić test warunków. To jest fundamentalne.

Rozważ rzut pianina gracza. Fortepian odtwarzający może odtwarzać bardzo skomplikowane utwory muzyczne, ale w muzyce nigdy nie ma logiki warunkowej. To jest Turing Complete.

Logika warunkowa to zarówno siła, jak i niebezpieczeństwo maszyny, która jest Turing Complete.

Rolka pianina gwarantuje zatrzymanie się za każdym razem. Nie ma takiej gwarancji na TM. Nazywa się to „problemem zatrzymania”.

Jak powiedział Waylon Flinn :

Turing Complete oznacza, że ​​jest co najmniej tak potężny jak Maszyna Turinga.

Uważam, że jest to niepoprawne, system jest kompletnie Turinga, jeśli jest dokładnie tak potężny jak Maszyna Turinga, tzn. Każde obliczenie wykonane przez maszynę może być wykonane przez system, ale również każde obliczenie wykonane przez system może być wykonane przez maszynę Turinga .

W praktycznych terminach językowych znanych większości programistów, zwykłym sposobem na wykrycie kompletności Turinga jest, jeśli język pozwala lub pozwala na symulację zagnieżdżonych instrukcji niezwiązanych while (w przeciwieństwie do instrukcji w stylu Pascala dla instrukcji z ustalonymi górnymi granicami).

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

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