Czy wszystkie języki są kompletne wymienne?

Uwaga: chociaż umiem programować, jestem całkiem początkującym w teorii CS.

Zgodnie z tą odpowiedzią

Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język Turinga.

I każdy program napisany w dowolnym języku kompletne Turinga mogą być zapisane w innym .

Dobrze. To ma sens. Potrafię przetłumaczyć (skompilować) C na Asembler (i robię to codziennie!) I mogę przetłumaczyć Asembler na C (Możesz napisać maszynę wirtualną w C). To samo dotyczy każdego innego języka - możesz skompilować dowolny język w asemblerze, a następnie uruchomić go na maszynie wirtualnej napisanej w innym języku.

Ale czy każdy program napisany w pełnym języku Turinga może zostać napisany w innym?

Co się stanie, jeśli moje Zgromadzenie ma kod operacyjny LIGHTBUTTON? Nie mogę naśladować tego języka w systemie (języku) bez żarówki.

Dobrze. Powiesz więc, że skoro mamy do czynienia z teorią komputerową , nie rozmawiamy o ograniczeniach fizycznych urządzeń.

Ale co z urządzeniem, które nie ma mnożenia? podział? Według mojej najlepszej wiedzy (choć jest to bardziej pytanie dotyczące matematyki.SE), nie można naśladować mnożenia (a na pewno nie dzielenia) z dodawaniem i odejmowaniem [1].

Jak więc „pełny język turinga” (który może dodawać, odejmować i przeskakiwać) naśladować inny język, w którym można dodawać, odejmować, pomnażać i skakać?

EDYTOWAĆ

[1] Na dowolnych liczbach rzeczywistych.

Kompletność Turinga mówi jedno i tylko jedno: model obliczeniowy jest kompletny Turinga, jeśli dowolne obliczenia, które mogą być modelowane przez maszynę Turinga, mogą być również modelowane przez ten model.

Jakie więc obliczenia może modelować maszyna Turinga? Przede wszystkim Alan Turing i wszyscy jego koledzy byli zawsze zainteresowani funkcjami liczb naturalnych. Tak więc Maszyna Turinga (i rachunek λ, rachunek kombinatoryczny SK, funkcje rekurencyjne μ,…) mówią tylko o obliczalności funkcji na liczbach naturalnych. Jeśli nie mówimy o funkcji na liczbach naturalnych, koncepcja kompletności Turinga nawet nie ma sensu, po prostu nie ma zastosowania.

Zauważ jednak, że możemy zakodować wiele interesujących rzeczy jako liczby naturalne. Możemy kodować ciągi jako liczby naturalne, możemy kodować wykresy jako liczby naturalne, możemy kodować logiczne liczby naturalne. Możemy zakodować Maszyny Turinga jako liczby naturalne, co pozwala nam tworzyć Maszyny Turinga, które mówią o Maszynach Turinga!

I oczywiście nie wszystkie funkcje liczb naturalnych są obliczalne. Maszyna Turinga może obliczyć tylko niektóre funkcje na liczbach naturalnych, rachunek λ może obliczyć tylko niektóre funkcje na liczbach naturalnych, rachunek kombinacyjny SK może obliczyć tylko niektóre funkcje na liczbach naturalnych,… Zaskakujące (lub nie) okazuje się, że każdy model obliczeń (który jest faktycznie możliwy do zrealizowania w naszym fizycznym wszechświecie) może obliczać te same funkcje na liczbach naturalnych (przynajmniej dla wszystkich modeli, które znaleźliśmy do tej pory). [Uwaga: oczywiście istnieją słabsze modele obliczeń, ale nie znaleźliśmy jeszcze takiego, który jest silniejszy, z wyjątkiem niektórych, które są oczywiście niezgodne z naszym fizycznym wszechświatem, takich jak modele wykorzystujące liczby rzeczywiste lub podróże w czasie.]

Fakt, że po długim okresie poszukiwania wielu różnych modeli, za każdym razem odkrywamy, że mogą one wyliczyć dokładnie te same funkcje, jest podstawą tezy Kościoła-Turinga, która mówi (z grubsza), że wszystkie modele obliczeń są równie potężne i że wszystkie zawierają „idealne” pojęcie tego, co to znaczy być „obliczalnym”. (Istnieje również drugi, bardziej filozoficzny aspekt CTT, a mianowicie to, że człowiek podążający za algorytmem może również obliczyć dokładnie te same funkcje, które TM może obliczyć i nie więcej.)

Jednak nic z tego nie mówi

• jak wydajne są różne modele
• jak wygodne są w użyciu
• co jeszcze mogą zrobić oprócz funkcji obliczeniowych na liczbach naturalnych

I że jest dokładnie tam, gdzie różnice pomiędzy różnymi modelami obliczeń (i językach programowania) wchodzą w grę.

Jako przykład innej wydajności zarówno maszyna o dostępie swobodnym, jak i maszyna Turinga mogą kopiować tablicę. Jednak RAM musi operacji do tego, podczas gdy TM musi Ò ( s ı ż e 2 r r y ) operacji, ponieważ musi ona przejść w poprzek y ı Z e r r a y elementy układu do kopiowania każdy element i są y i z $O(size_{array})$$O(size_{array}^2)$$size_{array}$ elementy do kopiowania.$size_{array}$

Jako przykład różnej wygody możesz po prostu porównać kod napisany w języku bardzo wysokiego poziomu, kod napisany w asemblerze oraz opis bazy TM do rozwiązania tego samego problemu.

A twój włącznik światła jest przykładem trzeciego rodzaju różnicy, rzeczy, które niektóre modele mogą zrobić, które nie działają na liczbach naturalnych, a zatem nie mają nic wspólnego z kompletnością Turinga.

Aby odpowiedzieć na konkretne pytania:

Ale czy każdy program napisany w pełnym języku Turinga może zostać napisany w innym?

Nie. Tylko jeśli program oblicza funkcję obliczalną Turinga na liczbach naturalnych. I nawet wtedy może wymagać złożonego kodowania. Na przykład rachunek λ nie ma nawet liczb naturalnych, należy je zakodować za pomocą funkcji (ponieważ funkcje są jedyną rzeczą, jaką ma rachunek λ).

To kodowanie danych wejściowych i wyjściowych może być bardzo złożone, podobnie jak wyrażanie algorytmu. Tak więc, chociaż prawdą jest, że każdy program można przepisać, przepisany program może być znacznie bardziej złożony, znacznie większy, zużywać znacznie więcej pamięci i być znacznie wolniejszy.

Co się stanie, jeśli moje Zgromadzenie ma kod operacyjny LIGHTBUTTON? Nie mogę naśladować tego języka w systemie (języku) bez żarówki.

Żarówka nie jest funkcją obliczalną Turinga dla liczb naturalnych. Naprawdę żarówka nie jest ani funkcją, ani obliczeniem. Włączanie i wyłączanie żarówki to efekt uboczny we / wy. Maszyny Turinga nie modelują efektów ubocznych I / O, a kompletność Turinga nie jest dla nich istotna.

Na dowolnych liczbach rzeczywistych.

Kompletność Turinga dotyczy tylko funkcji obliczalnych na liczbach naturalnych, nie dotyczy liczb rzeczywistych.

Kompletność Turinga jest po prostu niezbyt interesująca, jeśli chodzi o pytania takie jak twoje z dwóch powodów:

1. To nie jest bardzo wysoka przeszkoda. Wszystko czego potrzebujesz to IF, GOTO, WHILE, i zmienna jedna liczba całkowita (zakładając, że zmienna może posiadać dowolnie dużych liczb całkowitych). Lub rekurencja. Wiele, wiele, wiele innych rzeczy jest kompletnych w Turinga. Gra karciana Magic: The Gathering jest kompletna. CSS3 jest kompletny w Turingu. Plik sendmailkonfiguracyjny jest kompletny Turinga. Procesor Intel x86 MMU jest kompletny. Instrukcja Intel x86 MOVjest kompletna. Animacje PowerPoint są kompletne. Program Excel (bez skryptów, tylko przy użyciu formuł) jest kompletny Turinga. Protokół routingu BGP jest kompletny Turinga. sedjest ukończony przez Turinga. mod_rewriteReguły Apache są kompletne. Google dla „ (przypadkowo LUB zaskakująco) zakończone"znaleźć inne ciekawe przykłady. Jeśli prawie wszystko jest kompletne, to bycie kompletnym przestaje być interesującą właściwością.
2. W rzeczywistości nie jest konieczne, aby być użytecznym. Wiele przydatnych rzeczy nie jest kompletnych w Turinga. CSS przed wersji 3 nie jest Turing-complete (oraz fakt, że CSS3 to nie jest faktycznie wykorzystywany przez nikogo). SQL przed 1999 rokiem nie był kompletny w Turinga, ale był niezwykle przydatny nawet wtedy. Język programowania C bez dodatkowych bibliotek nie wydaje się być kompletny w Turingu . Języki pisane zależnie, mniej więcej z definicji, nie są pełne Turinga, ale można w nich pisać systemy operacyjne, serwery sieciowe i gry.

Edwin Brady, autor Idris, używa terminu „Tetris-complete”, aby mówić o niektórych z tych aspektów. Bycie kompletnym w Tetris nie jest rygorystycznie zdefiniowane (poza oczywistym „może być użyty do implementacji Tetris”), ale obejmuje takie rzeczy, jak bycie na wysokim poziomie i na tyle ekspresyjnym, że można napisać grę bez szaleństwa, możliwość interakcja ze światem zewnętrznym (wejście i wyjście), zdolność do wyrażania skutków ubocznych, możliwość pisania pętli zdarzeń, zdolność do wyrażania programów reaktywnych, asynchronicznych i współbieżnych, możliwość interakcji z systemem operacyjnym, możliwość do interakcji z bibliotekami obcymi (innymi słowy: możliwość dzwonienia i bycia wywoływanym przez kod C) i tak dalej. Są to o wiele bardziej interesujące cechy języka programowania ogólnego przeznaczenia niż Turinga-kompletność.

Być może moja odpowiedź na pytanie, które połączyłeś, jest interesująca, która dotyczy niektórych tych samych punktów, mimo że odpowiada na inne pytanie.

Oczywiście możesz zastosować mnożenie z dodawaniem i odejmowaniem:

/* Assume b is positive for simplicity */
int multiply(int a, int b) {
  int res = 0;
  while (b > 0) { res += a; b -= 1; }
  return res;
}

Fakt, że prawdopodobnie tego nie zrobiłbyś, nie czyni tego mniej możliwym.

Podział nie jest trudniejszy:

/* Assume a and b are positive for simplicity */
int divide(int a, int b) {
  int res = 0;
  while (a >= b) { res += 1; a -= b; }
  return res;
}

Jak myślisz, w jaki sposób mnożenie i dzielenie są wykonywane przez obwody procesora? Wskazówka: nie jest to olbrzymi stół przeglądowy. Jest to bardziej wydajne niż powyższe, ponieważ stosuje się również przesunięcie bitów, ale jest zasadniczo realizowane pod względem dodawania i odejmowania.

Żadna fizyczna (faktycznie istniejąca) maszyna nie jest ani nigdy nie może być kompletna w Turingu, ponieważ kompletność Turinga wymaga nieskończonego przechowywania, a wszechświat nie jest nieskończony.

Wynika z tego, że twierdząca odpowiedź na to, czy dwie abstrakcyjne maszyny są równoważne, nie pomaga odpowiedzieć na pytanie, czy dwa fizyczne przybliżenia tych maszyn są równoważne.

Dlatego równoważność Turinga modeli abstrakcyjnych (na przykład) dwóch języków nie oznacza, że ​​każdy może obliczyć wszystko, co drugi może obliczyć w praktyce. Jeden może spotkać się z ograniczeniami fizycznymi przed drugim.

$nm = n + n(m-1)$$m/n = 1 + (m-n)/n$

W rzeczywistości operacje „dodaj 1”, „odejmij 1” i „skok warunkowy, jeśli określony rejestr ma wartość zero” są wystarczające do wykonania modelu obliczeniowego Turinga jako kompletnego (patrz maszyna 2-licznikowa jako odniesienie dla bardzo minimalny model obliczeniowy Turinga).

$2$$2n = n+n$$2$$m \times 2n = 2m \times n$$m \times (2n+1) = m + 2m \times n$

tl; dr - Maszyny Turinga to tylko podstawowy logiczny opis dla ogólnego działania systemu logicznego. Potrafią robić większość rzeczy, które możemy opisać, w tym wywoływać specjalne kody i konstruować operacje matematyczne.

Co się stanie, jeśli moje Zgromadzenie ma kod operacyjny LIGHTBUTTON? Nie mogę naśladować tego języka w systemie (języku) bez żarówki.

W modelu Turinga symbole, takie jak LIGHTBUTTONkod operacyjny, są po prostu łańcuchami w dowolnym alfabecie, którego używa komputer Turinga.

Tak więc maszyna Turinga byłaby odpowiedzialna za wytworzenie łańcucha "LIGHTBUTTON"lub jakiejś wartości całkowitej, która odpowiada temu kodowi operacji; to, czy podmiot zewnętrzny działa na nie, nie jest biznesem komputera Turinga.

Programy C mają to samo ograniczenie. Oznacza to, że program C może wywoływać kod operacji LIGHTBUTTON, jednak to, czy procesor faktycznie wykonuje operację związaną z tym kodem operacji, zależy od procesora.

Ale co z urządzeniem, które nie ma mnożenia? podział? Zgodnie z moją najlepszą wiedzą (choć jest to bardziej pytanie dotyczące matematyki.SE), nie można naśladować mnożenia (a na pewno nie dzielenia) z dodawaniem i odejmowaniem [na dowolnych liczbach rzeczywistych].

Tak, maszyna Turinga może robić te rzeczy, nawet na liczbach rzeczywistych, w zakresie, w jakim każda logika opisywana przez człowieka może to zrobić. Maszyna Turinga może być tak prosta jak automatyzacja komórkowa Rule 110 .

Sztuką jest zbudowanie układu logicznego z dowolnej fizyki, jaką ma naturalnie maszyna. Na przykład procesory głównego nurtu mogą dokonywać mnożenia i dzielenia, ponieważ mają arytmetyczną jednostkę logiczną (ALU) . Ale ALU nie są magią; same są po prostu prostymi bramkami logicznymi . I te bramki logiczne są wykonane z tranzystorów . Te tranzystory są wykonane z domieszkowanego piasku .

Tak więc, aby uzyskać kompletne urządzenie Turinga do wykonywania matematyki, wystarczy zaprogramować to w ten sposób.

$\pi-\pi=0$$\pi$$\pi$$\pi-\pi=0$

Ale czy każdy program napisany w pełnym języku Turinga może zostać napisany w innym?

Jeśli wejściem do programu jest dowolnie długa sekwencja bitów, a wyjście to również dowolnie długa sekwencja bitów, to TAK. Zakładając, że masz czas i energię na przepisanie go, że nie zależy ci na wydajności i że masz wystarczającą pamięć fizyczną na obie implementacje.

Praktyczne względy, które oznaczają, że dwa kompletne języki Turinga nie są zamienne, obejmują:

• obsługują różne rodzaje danych wejściowych i wyjściowych (np. dostęp do bazy danych SQL)

• mają różne biblioteki typów danych (np. obsługa ciągów Unicode)

• zapewniają różne paradygmaty programowania zoptymalizowane do różnych zadań (np. obiektów, wątków, coroutines, funkcji pierwszej klasy)

• zapewniają różne biblioteki funkcji (np. parsowanie i serializacja XML)

Nie. Kompletność Turinga nie ma nic wspólnego z programami , chodzi o funkcje matematyczne (lub algorytmy ). Dowolny algorytm - dowolne obliczenia - możesz wykonać w C, możesz to zrobić w dowolnym innym języku Turinga (powinno to być oczywiste). Ale kompletność Turinga wcale nie oznacza, że ​​możesz zrobić we / wy - w ogóle. W ogóle nie mówi o sprzęcie. Tylko obliczenia.

Możesz rozszerzyć język Turinga o dowolną operację sprzętową, którą chcesz (technicznie jest to jak fputci fgetcdziała w C). Jeśli weźmiesz dwa kompletne języki Turinga i rozszerzysz je o identyczne operacje specyficzne dla sprzętu, pozostaną one wymienne. Tak więc język asemblera z LIGHTBULBdziałaniem jest potężniejszy niż Turing-complete; można powiedzieć, że to koniec TuringaLIGHTBULB . Aby jakikolwiek inny język był identyczny, musi on być jeszcze ukończony przez Turinga LIGHTBULB; najłatwiej to zrobić, dodając do niej LIGHTBULBprymityw / instrukcję / funkcję / itp.

Z tego powodu implementacje C zazwyczaj obsługują wbudowany asembler lub dokumentują sposób wywoływania funkcji napisanych w asemblerze i dlatego implementacje innych języków zazwyczaj zapewniają sposób wywoływania funkcji napisanych w C.