Próbowałem wyjaśnić komuś, że C jest kompletne w Turinga, i zdałem sobie sprawę, że tak naprawdę nie wiem, czy w rzeczywistości jest to kompletny Turing. (C jak w semantyce abstrakcyjnej, a nie jak w rzeczywistej implementacji).

„Oczywista” odpowiedź (z grubsza: może zająć się dowolną ilością pamięci, więc może emulować maszynę RAM, więc jest kompletna z Turinga), w rzeczywistości, o ile wiem, nie jest poprawna, ponieważ chociaż standard C pozwala aby size_t był arbitralnie duży, musi być ustalony na pewną długość i bez względu na to, na jakiej długości jest ustalony, jest wciąż skończony. (Innymi słowy, chociaż można, biorąc pod uwagę dowolne zatrzymanie maszyny Turinga, wybrać długość size_t tak, aby działała ona „prawidłowo”, nie ma sposobu, aby wybrać długość size_t, tak aby wszystkie maszyny zatrzymujące Turinga działały poprawnie)

Więc: czy C99 Turing jest kompletny?

Nie jestem pewien, ale myślę, że odpowiedź brzmi „nie” z dość subtelnych powodów. I poprosił o Theoretical Computer Science kilka lat temu i nie uzyskać odpowiedź, która wykracza poza to, co ja tu obecnych.

W większości języków programowania można symulować maszynę Turinga poprzez:

• symulowanie skończonego automatu za pomocą programu, który wykorzystuje skończoną ilość pamięci;
• symulowanie taśmy za pomocą pary połączonych list liczb całkowitych reprezentujących zawartość taśmy przed bieżącą pozycją i po niej. Przesunięcie wskaźnika oznacza przeniesienie nagłówka jednej z list na drugą.

W konkretnej implementacji działającej na komputerze zabrakłoby pamięci, gdyby taśma była zbyt długa, ale idealna implementacja mogłaby wiernie wykonać program maszyny Turinga. Można to zrobić za pomocą długopisu i papieru lub kupując komputer z większą pamięcią i kompilatorem ukierunkowanym na architekturę z większą liczbą bitów na słowo itd., Jeśli programowi zabraknie pamięci.

To nie działa w C, ponieważ nie można mieć połączonej listy, która mogłaby rosnąć wiecznie: zawsze istnieje pewne ograniczenie liczby węzłów.

Aby wyjaśnić, dlaczego, najpierw muszę wyjaśnić, czym jest implementacja C. C to właściwie rodzina języków programowania. Standard ISO C (dokładniej, specyficzna wersja tego standardu) określa (z poziomu formalizmu, który pozwala angielska) składni i semantyki to rodzina języków programowania. C ma wiele niezdefiniowanych zachowań i zachowań zdefiniowanych w implementacji. „Implementacja” C kodyfikuje wszystkie zachowania zdefiniowane w implementacji (lista rzeczy do skodyfikowania znajduje się w dodatku J dla C99). Każda implementacja C jest oddzielnym językiem programowania. Zauważ, że znaczenie słowa „implementacja” jest nieco dziwne: tak naprawdę oznacza wariant językowy, może istnieć wiele różnych programów kompilujących, które implementują ten sam wariant językowy.

$2^{\texttt{CHAR_BIT}}$t$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$

$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$

Wartości CHAR_BITi sizeof(void*)są obserwowalne, więc jeśli zabraknie pamięci, nie możesz po prostu wznowić działania programu z większymi wartościami dla tych parametrów. Uruchomiłbyś program w innym języku programowania - innej implementacji C.

$n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$$n$

C nie nakłada bezpośrednio maksymalnej głębokości rekurencji. Implementacja może mieć maksimum, ale także może nie mieć takiego. Ale w jaki sposób komunikujemy się między wywołaniem funkcji a jego rodzicem? Argumenty nie są dobre, jeśli można je adresować, ponieważ pośrednio ograniczyłoby to głębokość rekurencji: jeśli masz funkcję, int f(int x) { … f(…) …}wszystkie wystąpienia xaktywnych ramek fmają swój własny adres, a więc liczba zagnieżdżonych wywołań jest ograniczona liczbą możliwych adresów dla x.

Program AC może używać pamięci nieadresowalnej w postaci registerzmiennych. „Normalne” implementacje mogą mieć tylko niewielką, skończoną liczbę zmiennych, które nie mają adresu, ale teoretycznie implementacja może pozwolić na nieograniczoną ilość registerpamięci. W takiej implementacji można wykonać nieograniczoną liczbę rekurencyjnych wywołań funkcji, o ile są to jej argumenty register. Ale ponieważ argumentami są register, nie możesz zrobić dla nich wskaźnika, więc musisz jawnie skopiować ich dane: możesz przekazać tylko skończoną ilość danych, a nie strukturę danych o dowolnej wielkości złożoną ze wskaźników.

Dzięki nieograniczonej głębokości rekurencji i ograniczeniu, że funkcja może tylko pobierać dane z bezpośredniego wywołującego ( registerargumenty) i zwracać dane do bezpośredniego wywołującego (wartość zwracana przez funkcję), uzyskujesz moc deterministycznych automatów do przekazywania .

Nie mogę znaleźć sposobu, aby pójść dalej.

(Oczywiście można zmusić program do przechowywania zawartości taśmy na zewnątrz za pomocą funkcji wejścia / wyjścia pliku. Ale wtedy nie zapytałbyś, czy C jest kompletny w Turingu, ale czy C plus nieskończony system pamięci jest kompletny w Turingu, aby na które odpowiedź brzmi nudno „tak”. Równie dobrze możesz zdefiniować pamięć jako wezwanie Turinga  fopen("oracle", "r+"), fwritepoczątkową zawartość taśmy i freadcofnąć końcową zawartość taśmy).

Dodanie przez C99 va_copyargumentu variadic API może dać nam tylne drzwi do kompletności Turinga. Ponieważ staje się możliwe wielokrotne iterowanie poprzez listę argumentów variadic więcej niż raz w funkcji innej niż ta, która pierwotnie otrzymała argumenty, va_argsmożna zastosować do implementacji wskaźnika bez wskaźnika.

Oczywiście prawdziwa implementacja interfejsu API argumentu variadic prawdopodobnie będzie miała gdzieś wskaźnik, ale w naszej abstrakcyjnej maszynie może być zaimplementowana za pomocą magii.

Oto wersja demonstracyjna implementująca automat na 2 stosy z dowolnymi regułami przejścia:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Uwaga: Jeśli va_listjest to typ tablicowy, to w rzeczywistości istnieją ukryte parametry wskaźnika do funkcji. Więc prawdopodobnie lepiej byłoby zmienić typy wszystkich va_listargumentów na wrapped_stack.

Może niestandardowa arytmetyka?

Wygląda więc na to, że problemem jest skończona wielkość sizeof(t). Myślę jednak, że znam rozwiązanie.

O ile mi wiadomo, C nie wymaga implementacji, aby używać standardowych liczb całkowitych dla swojego typu liczb całkowitych. Dlatego moglibyśmy zastosować niestandardowy model arytmetyczny . Wówczas ustalilibyśmy sizeof(t)jakąś niestandardową liczbę, a teraz nigdy nie osiągniemy jej w skończonej liczbie kroków. Dlatego długość taśmy maszyn Turinga zawsze będzie mniejsza niż „maksimum”, ponieważ maksimum jest dosłownie niemożliwe do osiągnięcia. sizeof(t)po prostu nie jest liczbą w zwykłym tego słowa znaczeniu.

Jest to oczywiście jedna technika: twierdzenie Tennenbauma . Stwierdza, że ​​jedynym modelem arytmetyki Peano jest model standardowy, który oczywiście nie zrobiłby tego. Jednak, o ile mi wiadomo, C nie wymaga implementacji do używania typów danych, które spełniają aksjomaty Peano, ani nie wymaga implementacji do obliczenia, więc nie powinno to stanowić problemu.

Co powinno się stać, jeśli spróbujesz wypisać niestandardową liczbę całkowitą? Cóż, możesz reprezentować dowolną niestandardową liczbę całkowitą za pomocą niestandardowego ciągu, więc po prostu przesyłaj cyfry z przodu tego ciągu.

IMO, silnym ograniczeniem jest to, że przestrzeń adresowalna (poprzez rozmiar wskaźnika) jest skończona i nie można jej odzyskać.

Można powiedzieć, że pamięć można „zamienić na dysk”, ale w pewnym momencie sama informacja o adresie przekroczy rozmiar adresowalny.

W praktyce ograniczenia te nie mają znaczenia dla kompletności Turinga. Rzeczywistym wymogiem jest, aby taśma była dowolna długa, a nie nieskończona. To stworzyłoby problem zatrzymania innego rodzaju (jak wszechświat „oblicza” taśmę?)

Jest to tak nieprawdziwe, jak powiedzenie „Python nie jest kompletny, ponieważ nie można zrobić nieskończenie dużej listy”.

[Edycja: dzięki Panu Whitledgeowi za wyjaśnienie, jak edytować.]

Nośniki wymienne pozwalają nam ominąć problem nieograniczonej pamięci. Być może ludzie pomyślą, że to nadużycie, ale myślę, że jest to w porządku i zasadniczo nieuniknione.

Napraw dowolne wdrożenie uniwersalnej maszyny Turinga. Do taśmy używamy nośników wymiennych. Gdy głowica opuści koniec lub początek bieżącej płyty, urządzenie wyświetli monit o włożenie następnego lub poprzedniego. Możemy użyć specjalnego znacznika do oznaczenia lewego końca symulowanej taśmy lub mieć taśmę, która jest nieograniczona w obu kierunkach.

Kluczową kwestią jest to, że wszystko, co program C musi zrobić, jest skończone. Komputer potrzebuje tylko wystarczającej ilości pamięci, aby zasymulować automat, i size_tmusi być wystarczająco duży, aby umożliwić adresowanie tej (właściwie raczej małej) ilości pamięci i na dyskach, które mogą mieć dowolny ustalony rozmiar. Ponieważ użytkownik jest monitowany tylko o włożenie następnej lub poprzedniej płyty, nie potrzebujemy bezgranicznie dużych liczb całkowitych, aby powiedzieć „Proszę włóż dysk o numerze 123456 ...”

Przypuszczam, że głównym zarzutem jest prawdopodobnie zaangażowanie użytkownika, ale wydaje się to nieuniknione w żadnej implementacji, ponieważ wydaje się, że nie ma innego sposobu implementacji nieograniczonej pamięci.

Wybierz size_tbyć nieskończenie duży

Możesz wybrać size_tnieskończenie duży rozmiar. Oczywiście nie można zrealizować takiego wdrożenia. Ale to nie jest niespodzianka, biorąc pod uwagę skończoną naturę świata, w którym żyjemy.

Praktyczne implikacje

Ale nawet gdyby możliwe było zrealizowanie takiego wdrożenia, pojawiałyby się problemy praktyczne. Rozważ następujące oświadczenie C:

printf("%zu\n",SIZE_MAX);

SIZE_MAXSIZE_MAX$O(2^{size\_t})$size_tSIZE_MAXprintf

Na szczęście dla naszych teoretycznych celów nie znalazłem w specyfikacji żadnego wymagania, które gwarantowałoby, że gwarancje printfwygasną dla wszystkich danych wejściowych. Tak więc, o ile mi wiadomo, nie naruszamy tutaj specyfikacji C.

O kompletności obliczeniowej

Pozostaje jeszcze udowodnić, że nasza teoretyczna implementacja jest zakończona w Turinga . Możemy to pokazać, wdrażając „dowolną maszynę Turinga z pojedynczą taśmą”.

Większość z nas prawdopodobnie wdrożyła maszynę Turinga jako projekt szkolny. Nie podam szczegółów konkretnej implementacji, ale oto często stosowana strategia:

• Liczba stanów, liczba symboli i tabela zmian stanów są ustalone dla dowolnej maszyny. Możemy więc reprezentować stany i symbole jako liczby, a tablicę przejścia stanu jako tablicę dwuwymiarową.
• Taśma może być reprezentowana jako lista połączona. Możemy użyć jednej podwójnie połączonej listy lub dwóch pojedynczo połączonych list (po jednej dla każdego kierunku od bieżącej pozycji).

Zobaczmy teraz, co jest wymagane do realizacji takiej implementacji:

• Możliwość reprezentowania jakiegoś ustalonego, ale arbitralnie dużego zestawu liczb. Aby reprezentować dowolną liczbę, wybieramy MAX_INTrównież nieskończoność. (Alternatywnie, moglibyśmy użyć innych obiektów do przedstawienia stanów i symboli.)
• Możliwość zbudowania arbitralnie dużej listy połączonej dla naszej taśmy. Po raz kolejny nie ma skończonego limitu rozmiaru. Oznacza to, że nie możemy skonstruować tej listy z góry, ponieważ spędzilibyśmy wiecznie tylko na budowie naszej taśmy. Ale możemy budować tę listę stopniowo, jeśli użyjemy dynamicznej alokacji pamięci. Możemy użyć malloc, ale jest jeszcze coś, co musimy wziąć pod uwagę:
  • Specyfikacja C pozwala mallocna awarię, jeśli np. Dostępna pamięć zostanie wyczerpana. Dlatego nasze wdrożenie jest naprawdę uniwersalne, jeśli mallocnigdy nie zawiedzie.
  • Jeśli jednak nasza implementacja zostanie uruchomiona na maszynie z nieskończoną pamięcią, nie ma potrzeby, mallocaby zawieść. Bez naruszenia standardu C nasza implementacja zagwarantuje, że mallocnigdy nie zawiedzie.
• Możliwość wyłapywania wskaźników, wyszukiwania elementów tablicy i uzyskiwania dostępu do elementów połączonego węzła listy.

Tak więc powyższa lista jest niezbędna do wdrożenia maszyny Turinga w naszej hipotetycznej implementacji C. Funkcje te muszą zostać zakończone. Cokolwiek innego może jednak nie zostać wypowiedziane (chyba że wymaga tego standard). Obejmuje to arytmetykę, operacje we / wy itp.

Głównym argumentem tutaj było to, że rozmiar size_t jest skończony, chociaż może być nieskończenie duży.

Istnieje obejście tego problemu, choć nie jestem pewien, czy jest to zgodne z ISO C.

Załóżmy, że masz maszynę z nieskończoną pamięcią. Zatem nie jesteś ograniczony wielkością wskaźnika. Nadal masz typ size_t. Jeśli zapytasz mnie, co to jest sizeof (size_t), odpowiedzią będzie tylko sizeof (size_t). Jeśli na przykład zapytasz, czy jest większa niż 100, odpowiedź brzmi „tak”. Jeśli zapytasz, co to jest sizeof (size_t) / 2, jak można się domyślić, odpowiedzią jest nadal sizeof (size_t). Jeśli chcesz go wydrukować, możemy zgodzić się na niektóre wyniki. Różnica tych dwóch może być NaN i tak dalej.

Podsumowanie jest takie, że złagodzenie warunku dla size_t ma skończony rozmiar nie zepsuje żadnych programów już istniejących.

PS Przydzielanie pamięci sizeof (size_t) jest nadal możliwe, potrzebujesz tylko policzalnego rozmiaru, więc powiedzmy, że bierzesz wszystkie znaki (lub podobną sztuczkę).

Tak to jest.

1. Cytowana odpowiedź

W reakcji na dużą liczbę głosów negatywnych na moje (i inne) poprawne odpowiedzi - w porównaniu z alarmująco wysoką akceptacją fałszywych odpowiedzi - szukałem mniej teoretycznie głębokiego wyjaśnienia. Znalazłem to . Mam nadzieję, że obejmuje niektóre z typowych błędów, aby pokazać nieco więcej wglądu. Zasadnicza część argumentu:

[...] Jego argumentacja jest następująca: załóżmy, że napisano dany program kończący, który może wymagać, w trakcie jego wykonania, do dowolnej ilości pamięci. Bez zmiany tego programu można a posteriori zaimplementować kawałek sprzętu komputerowego i jego kompilatora C, który zapewnia wystarczającą ilość pamięci, aby pomieścić to obliczenie. Może to wymagać rozszerzenia szerokości znaków (przez CHAR_BITS) i / lub wskaźników (przez size_t), ale program nie musiałby być modyfikowany. Ponieważ jest to możliwe, C jest rzeczywiście Turing-Complete do kończenia programów.

Trudna część tego argumentu polega na tym, że działa on tylko przy rozważaniu zakończenia programów. Programy kończące mają tę fajną właściwość, że mają statyczną górną granicę wymaganą do przechowywania, którą można eksperymentalnie określić, uruchamiając program na pożądanym wejściu ze zwiększającymi się rozmiarami pamięci, aż „dopasuje się”.

Powodem, dla którego wprowadzono mnie w błąd, było to, że rozważałem szerszą klasę „użytecznych” nie kończących się programów [...]

Krótko mówiąc, ponieważ dla każdej funkcji obliczeniowej istnieje rozwiązanie w języku C (z powodu nieograniczonej liczby górnych granic), każdy problem obliczeniowy ma program w języku C, więc C jest kompletny w Turingu.

2. Moja oryginalna odpowiedź

Powszechne są pomyłki między pojęciami matematycznymi w informatyce teoretycznej (np. Kompletność Turinga) a ich zastosowaniem w świecie rzeczywistym, tj. Technikami w informatyce praktycznej. Kompletność Turinga nie jest własnością fizycznie istniejących maszyn ani żadnego modelu w ograniczonym czasie. To tylko abstrakcyjny obiekt opisujący właściwości teorii matematycznych.

C99 jest kompletny z Turinga bez względu na ograniczenia implementacyjne, tak jak praktycznie każdy inny wspólny język programowania, ponieważ jest w stanie wyrazić funkcjonalnie kompletny zestaw logicznych połączeń i ma w zasadzie dostęp do nieograniczonej ilości pamięci. Ludzie zauważyli, że C wyraźnie ogranicza dostęp do pamięci losowej, ale nie można tego obejść, ponieważ są to dodatkowo określone ograniczenia w standardzie C, podczas gdy kompletność Turinga obejmuje je już bez nich :

Oto bardzo podstawowa rzecz na temat systemów logicznych, która powinna wystarczyć do uzyskania konstruktywnego dowodu. Rozważmy rachunek z pewnymi schematami i regułami aksjomatycznymi, tak że zestaw logicznych konsekwencji wynosi X. Teraz, jeśli dodasz jakieś reguły lub aksjomaty, zestaw logicznych konsekwencji rośnie, tzn. Musi być nadzbiorem X. To na przykład dlatego , logika modalna S4 jest poprawnie zawarta w S5. Podobnie, gdy masz pod-specyfikację, która jest kompletna Turinga, ale dodajesz pewne ograniczenia na górze, nie zapobiegają one żadnej konsekwencjom w X, tj. Musi istnieć sposób na obejście wszystkich ograniczeń. Jeśli chcesz mieć niekompletny język Turinga, rachunek musi być zmniejszony, a nie rozszerzony. Rozszerzenia, które twierdzą, że coś nie byłoby możliwe, ale tak naprawdę tylko dodają niespójności. Te niespójności w standardzie C mogą jednak nie mieć praktycznych konsekwencji, podobnie jak kompletność Turinga nie ma związku z praktycznym zastosowaniem.

Symulowanie dowolnych liczb na podstawie głębokości rekurencji (tj. To ; z możliwością obsługi wielu liczb za pomocą harmonogramu / pseudo-wątków; nie ma teoretycznego ograniczenia głębokości rekurencji w C ), lub użycie pamięci plików do symulacji nieograniczonej pamięci programu ( pomysł ) prawdopodobnie tylko dwie z nieskończonych możliwości konstruktywnego udowodnienia kompletności Turinga C99. Należy pamiętać, że dla obliczalności złożoność czasu i przestrzeni nie ma znaczenia. W szczególności zakładanie ograniczonego środowiska w celu sfałszowania kompletności Turinga jest jedynie okrągłym rozumowaniem, ponieważ ograniczenie to wyklucza wszystkie problemy, które przekraczają założoną złożoność.

( UWAGA : Napisałem tę odpowiedź tylko po to, aby powstrzymać ludzi przed zatrzymaniem się w celu uzyskania intuicji matematycznej z powodu pewnego rodzaju ograniczonego myślenia zorientowanego na aplikację. Szkoda, że ​​większość uczniów przeczyta fałszywie przyjętą odpowiedź z powodu jej głosowania na podstawie fundamentalne wady rozumowania, aby więcej osób rozpowszechniało takie fałszywe przekonania. Jeśli głosujesz za tą odpowiedzią, jesteś tylko częścią problemu).