Czy istnieją minimalne kryteria dla języka programowania Turinga?

Czy istnieje zestaw konstrukcji języka programowania w języku programowania, aby można go uznać za ukończony jako Turing?

Z tego, co mogę powiedzieć z wikipedii , język musi obsługiwać rekursję lub, pozornie, musi być w stanie działać bez zatrzymywania się. Czy to już wszystko?

Zawsze myślałem, że to rekurencyjne funkcje go przykuły . Oto, co definiuje cały zestaw funkcji obliczalnych; jest to najmniejszy zestaw funkcji zawierających odpowiednio. zamknięte przeciwko:$\mu$

1. Stała funkcja$0$
2. Funkcja następcy
3. Wybór parametrów
4. Skład funkcji
5. Pierwotna rekurencja
6. -operator (poszukaj najmniejszych takie, że ...)$\mu$$x$

Sprawdź powyższy link, aby uzyskać szczegółowe informacje; widzisz, że tworzy bardzo kompaktowy język programowania. Programowanie w programie jest również okropne - brak darmowego lunchu. Jeśli upuścisz którykolwiek z nich, stracisz pełną moc, więc jest to minimalny zestaw aksjomatów.

Możesz przełożyć je dosłownie na podstawowe elementy składniowe programów WHILE , a mianowicie

1. Stała 0
2. Przyrost _ + 1
3. Zmienny dostęp x
4. Łączenie programu / oświadczenia _; _
5. Pętle odliczające for ( x to 0 ) do _ end
6. Podczas pętli while ( x != 0 ) do _ end

Czy istnieje zestaw obliczeń, które należy wykonać w języku programowania, aby można je było uznać za ukończone Turinga?

Tak, aby uznać Turing za kompletny, język programowania musi być w stanie wykonać dowolne obliczenia, które mogą być wykonane przez maszynę Turinga. Tak więc, co można by powiedzieć minimalnym wymogiem, musisz być w stanie zaimplementować w nim uniwersalną maszynę Turinga - lub tłumacza dla dowolnego innego kompletnego języka Turinga.

Z tego, co mogę powiedzieć z wikipedii, język musi obsługiwać rekursję lub, pozornie, musi być w stanie działać bez zatrzymywania się. Czy to już wszystko?

Nie. Na przykład językiem, w którym jedyną dozwoloną operacją jest rekurencja (tzn. Jedyną możliwą funkcją, którą można napisać f(x) = f(x), jest brak ukończenia Turinga, ponieważ wszystko, co można w nim pisać, to programy, które nigdy się nie kończą. Jak powiedziałem wcześniej, kompletny język Turinga musi być w stanie zaimplementować dowolne obliczenia, które mogą być wykonane przez maszynę Turinga. Tak wyraźnie, że to nie wystarczy.

Również język nie musi obsługiwać rekurencji w sposób, w jaki myślisz. Po prostu nieograniczony sposób wyrażania pętli. To może być rekurencja, ale może to być również pętla czasowa lub goto. Język, który w ogóle nie ma funkcji, nadal może być kompletny. I znowu pętle lub funkcje rekurencyjne nie są wystarczającym warunkiem. Nadal potrzebujesz sposobu na wykonanie innego kodu w zależności od warunku i sposobu na obliczenie nowych wartości ze starych (w przeciwnym razie wszystkie pętle / rekurencja byłyby nieskończone lub w ogóle nie działały).

Jeśli chodzi o to, czy istnieje minimalny zestaw niezbędnych i wystarczających operacji, tak, że każdy język, który obsługuje te operacje, jest Turing kompletny, a każdy język, który tego nie robi: Nie, nie ma (chyba że tak niejasno zdefiniujesz „operacja” , że staje się bez znaczenia):

Na przykład, jak już powiedziałem, istnieją kompletne języki Turinga, które nie obsługują funkcji rekurencyjnych (ani żadnych innych funkcji). Te nadal mogą być kompletne, jeśli mają gotoinstrukcję lub whilepętlę (i sposób przechowywania dowolnych ilości danych). Jednak język z funkcjami rekurencyjnymi nie musi być whileani gotokompletny w języku Turinga. Tak więc gotonie byłoby w zestawie niezbędnych wystarczających operacji, ale istnieją języki, które nie są już ukończone przez Turinga, jeśli je usuniesz goto. Zatem nie ma takiego zestawu.

Istnieje wiele pojedynczych instrukcji, które prowadzą do kompletnych języków Turinga. Typowym przykładem jest „odejmij i rozgałęź, jeśli zero”. Są one dobrze znane w kontekście programowania w asemblerze. Szczegółowe informacje można znaleźć w artykule w Wikipedii .

Prowadzi to do scharakteryzowania: język Turinga jest kompletny wtedy i tylko wtedy, gdy jest w stanie symulować operacje pobierania i przechowywania liczb całkowitych w pamięci i wykonywania na nich operacji „odejmowania i rozgałęziania, jeśli zero”.

To nie jest ogólna odpowiedź na twoje pytanie, ale dzięki twierdzeniu o programowaniu strukturalnym wszystko, czego potrzeba, to umiejętność wyboru (np. ifW C / C ++) i powtarzania (np. whileW C / C ++). Edycja: jak zauważył Dave Clarke w komentarzach, twierdzenie o programowaniu strukturalnym również wymaga sekwencji. Początkowo nie wymieniłem tego, ponieważ uważałem za oczywiste, że czytelnik zrozumie, że podstawowe bloki innych instrukcji, takich jak te, do których później nawiązywał odczyt i zapis do pamięci itp., Były również konieczne). Oczywiście lepiej jest być wyraźnym; musisz także móc robić te rzeczy.

Ponieważ oba z nich można zaimplementować za pomocą instrukcji skoku warunkowego (np. JNZW x86), jest to również wystarczające dla równoważności Turinga.

Zauważ, że wymagane są inne rzeczy, tj. Możliwość zapisu nieograniczonej liczby symboli (np. Bitów ... 0 lub 1) w jakimś zewnętrznym magazynie pamięci. W tym sensie prawdziwe komputery nie są odpowiednikami Turinga, ponieważ żaden z nich nie ma nieskończonej ilości pamięci. Model Turinga jest jednak nadal użyteczny, ponieważ ilość pamięci jest zwykle ogromna i chociaż każdy problem, który może rozwiązać prawdziwy komputer, może zostać rozwiązany przez deterministyczny automat skończony, użycie tego modelu obliczeniowego nie jest szczególnie przydatne (ponieważ liczba stanów byłaby niedorzecznie ogromna).

Zauważ, że niekoniecznie jest to sprzeczne z odpowiedzią sepp2k; to jest po prostu inny sposób myślenia o tym samym pytaniu.

EDYTOWAĆ:

Należy również zauważyć, że tak naprawdę nie potrzebują zarówno ifa whilew C / C ++. Możesz przeprowadzić symulację ifza pomocą while:

bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

Poniższy kod jest zawsze równoważny:

bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

Cóż ... konstrukcja powinna działać i być możliwa, jeśli jesteś ostrożny. Zauważ też, że jeśli masz funkcje rekurencyjne, w końcu potrzebujesz również wyboru; ponieważ funkcje rekurencyjne bez wyboru nie mogą tak naprawdę implementować przypadków bazowych, więc każda funkcja rekurencyjna spowodowałaby nieskończoną rekurencję.

EDYTOWAĆ:

Ponadto, jeśli chodzi o twoje pytanie, czy umiejętność napisania programu, który nie zatrzymuje się, jest wystarczający dla równoważności Turinga, odpowiedź brzmi „nie”; jest to konieczne, ale niewystarczające. Możemy rozwiązać problem zatrzymania programów napisanych w języku, który nie potrafi wyrazić programów, które się nie zatrzymują; odpowiedź brzmi „program się zatrzymuje” dla wszystkich instancji. Możemy jednak zdefiniować język, w którym jedyna instrukcja powoduje, że maszyna wchodzi w nieskończoną pętlę ... taki język nie jest odpowiednikiem Turinga.

Kombinatory i gdzie, i są wystarczające do wyrażenia dowolnego (zamkniętego) wyrażenia lambda, a zatem dowolnej funkcji obliczalnej. Zobacz tę stronę wikipedii, aby uzyskać szczegółowe informacje.K ( S x y z ) = ( x z ( y z ) ) ( K x y ) = $\mathbf{S}$$\mathbf{K}$$(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$$(\mathbf{K}\ x\ y) = x$

W rzeczywistości termin lambda jest wystarczającą podstawą do wyrażenia wszystkich terminów lambda. Zobacz później na tej samej stronie Wikipedii .$\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$

Konstrukcje językowe są wymienne

Nie ma ustalonych minimalnych kryteriów dotyczących tego, jakie konstrukcje muszą być natywnie dostarczane przez język programowania. Jeśli zapewnia jakieś dziwne konstrukty, które można w jakiś sposób skręcić w celu wyrażenia systemu pełnego Turinga, to najwyraźniej te konstrukty są „tak samo odpowiednie” jak inne.

Aby to udowodnić - język, który zapewnia tylko operację „odejmowania i rozgałęziania, jeśli zero” jest zakończony Turing; istnieją kompletne języki Turinga, które nie zapewniają osobnej konstrukcji „odejmowania i rozgałęzienia, jeśli zero”, ergo, nie ma takiej konstrukcji ani zestawu konstrukcji, które są obowiązkowe.

Efekty dowolnej konstrukcji języka pełnego TP mogą być emulowane przez konstrukcje dowolnego innego języka pełnego TP.