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

55

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?

Chanzor
źródło
6
Być może twoje pytanie powinno brzmieć „Czy istnieje minimalny zestaw konstrukcji programistycznych ...?”, Ponieważ, jak to sformułowano, odpowiedź brzmi „Wszystkie obliczalne”.
Dave Clarke
@DaveClarke, dzięki, zaktualizowałem to. Uważam, że twój komentarz nieco nasuwa pytanie, chociaż zakładam, że to dlatego, że mój język jest kiepski. Chciałem zapytać, czy istnieje kilka operacji, które jeśli język mógłby obliczyć, byłby równoważny.
Khanzor,

Odpowiedzi:

45

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:μ

  1. Stała funkcja0
  2. Funkcja następcy
  3. Wybór parametrów
  4. Skład funkcji
  5. Pierwotna rekurencja
  6. -operator (poszukaj najmniejszych takie, że ...)μ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
Raphael
źródło
1
Myślę, że to oczywiste, że nie można upuścić 5. reguły w języku. Ponieważ whilepętla w 6 porównuje się ze stałym zerem, zmienne mogą być zwiększane tylko przez regułę 2 i nie ma żadnych stałych ujemnych od początku (reguła 1), whilepętla w 6 albo nie została wprowadzona (x = 0), albo jest nieskończona ( x> 0, a ciało pętli nie może go zmniejszyć).
MSalters
1
@MSalters Myślę, że masz rację; do symulacji, o której myślę, że miałem na myśli, potrzebujemy _ - 1i nie potrafię wymyślić sposobu na jej wdrożenie for. Dzięki za złapanie tego! (Co jest „lepsze” - w tym _ - 1lub for? Hmm.)
Raphael
20

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.

sepp2k
źródło
Jedyne, czego nie jestem pewien, to odpowiedź na minimalny zestaw niezbędnych operacji. Wydaje się, że ograniczasz swoją definicję operacji do Struktur Kontroli, które wydają się mieć znacznie węższy zakres niż jest to wymagane, a poza własnym wymogiem nieokreślania ich „tak niejasno, że [stają się] bez znaczenia”.
Joshua Drake
@JoshuaDrake Nie jestem pewien, co masz na myśli. Nie ograniczam operacji do kontrolowania struktur. Po prostu nie mówię o żadnych operacjach, które nie są strukturami kontrolnymi w moim kontrprzykładzie, ponieważ nie dotyczą one tego przykładu. Właściwie wspominam o „sposobie przechowywania dowolnych ilości danych” - to nie jest struktura kontrolna.
sepp2k
Zwracasz uwagę na to, że niektóre języki obsługują kompletność Turinga, gotoale niektóre nie, najwyraźniej twierdząc, że ponieważ niektórzy go używają, a niektóre nie, gototo nie może być częścią zestawu operacji wymaganych dla kompletności Turinga. Chodzi mi o to, że gotojest to po prostu syntaktyczny sposób implementacji określonej, bardziej ogólnej operacji, takiej jak skok. Dlatego uważam, że gdybyś po prostu oderwał się od konkretnych struktur kontrolnych, zbliżyłbyś się do zestawu operacji, które przynajmniej wskazywałyby na Kompletność Turinga.
Joshua Drake
@JoshuaDrake Nie sądzę, aby użycie „skoku” zamiast goto doprowadziło nas do punktu, w którym możemy zdefiniować wystarczający i niezbędny zestaw operacji. Prawdopodobnie to prawda, że ​​każdy język wymagałby jakiejś operacji przeskoku (a jeśli to tylko wywołania funkcji), ale nie sądzę, że będziesz w stanie wymyślić dalsze operacje, aby to wystarczyło. Na przykład rachunek lambda ma dwie operacje: aplikację (tj. Naszą operację skoku) i abstrakcję (tj. Tworzenie funkcji) ...
sepp2k
1
@JoshuaDrake Nie sądzę, że artykuł próbuje twierdzić, że jakikolwiek język z Turingiem musi mieć takie operacje. Zwłaszcza, że ​​ogranicza to stwierdzenie wyłącznie do języków proceduralnych. Z wyjątkiem formy goto (tj. Aplikacji funkcji) Lambda Calculus nie ma żadnej z tych rzeczy. Myślę, że „minimum” oznacza tutaj tylko, że w języku, który ma tylko te funkcje, nie można usunąć żadnej z nich bez utraty kompletności Turinga. Nie dlatego, że nie ma innego minimalnego zestawu operacji, który byłby wystarczający dla kompletności Turinga.
sepp2k
14

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”.

Carl Mummert
źródło
13

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.

Patrick87
źródło
13

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 ) = xSK(S x y z)=(x z (y z))(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 .X=λx.((x S) K)

Dave Clarke
źródło
5

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.

Piotr jest
źródło