Czy C faktycznie Turinga jest kompletny?

39

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?

TLW
źródło
3
Jakie są „abstrakcyjne semantyki” C? Czy są zdefiniowane gdziekolwiek?
Yuval Filmus
4
@YuvalFilmus - Zobacz np. Tutaj , tj. C jak zdefiniowano w standardzie w przeciwieństwie do np. „Tak robi to gcc”.
TLW
1
istnieje „techniczność” polegająca na tym, że współczesne komputery nie mają nieskończonej pamięci jak TM, a mimo to są uważane za „komputery uniwersalne”. i zauważmy, że języki programowania w swojej „semantyce” tak naprawdę nie zakładają skończonej pamięci, z wyjątkiem tego, że wszystkie ich implementacje mają oczywiście ograniczoną pamięć. patrz np. czy nasz komputer działa jak maszyna Turinga . w zasadzie wszystkie języki programowania „głównego nurtu” są kompletne.
vzn
2
C (podobnie jak maszyny Turinga) nie ogranicza się do korzystania z wewnętrznej pamięci komputera do obliczeń, więc to naprawdę nie jest prawidłowy argument przeciwko kompletności Turinga C.
reinierpost
@reinierpost - to tak, jakby powiedzieć, że teletype jest mądry. To znaczy, że „C + zewnętrzny odpowiednik TM” jest kompletny Turinga, a nie że C jest kompletny Turinga.
TLW

Odpowiedzi:

34

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.

2CHAR_BITt2CHAR_BIT×sizeof(t)

2CHAR_BIT×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×2CHAR_BIT×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).

Gilles „SO- przestań być zły”
źródło
Nie jest od razu jasne, dlaczego zbiór adresów powinien być skończony. Napisałem kilka przemyśleń w odpowiedzi na pytanie, które łączysz
Alexey B.,
4
Przykro nam, ale według tej samej logiki w ogóle nie ma kompletnych języków programowania Turinga. Każdy język ma wyraźne lub dorozumiane ograniczenie przestrzeni adresowej. Jeśli utworzysz maszynę z nieskończoną pamięcią, wskaźniki dostępu losowego będą oczywiście miały nieskończoną długość. Dlatego jeśli taka maszyna się pojawi, będzie musiała zaoferować zestaw instrukcji dla sekwencyjnego dostępu do pamięci, wraz z interfejsem API dla języków wysokiego poziomu.
IMil
14
@IMil To nie jest prawda. Niektóre języki programowania nie mają ograniczenia przestrzeni adresowej, nawet pośrednio. Weźmy oczywisty przykład: uniwersalna maszyna Turinga, w której początkowy stan taśmy tworzy program, jest kompletnym językiem programowania Turinga. Wiele języków programowania faktycznie używanych w praktyce ma tę samą właściwość, na przykład Lisp i SML. Język nie musi mieć pojęcia „wskaźnik dostępu swobodnego”. (ciąg dalszy)
Gilles „SO- przestań być zły”
11
@IMil (cd.) Implementacje zwykle mają na celu zwiększenie wydajności, ale wiemy, że implementacja działająca na określonym komputerze nie jest ukończona przez Turinga, ponieważ jest ograniczona wielkością pamięci komputera. Ale to oznacza, że ​​implementacja nie implementuje całego języka, tylko podzbiór (programów działających w N bajtów pamięci). Możesz uruchomić program na komputerze, a jeśli zabraknie mu pamięci, przenieś go na większy komputer i tak dalej, na zawsze lub do momentu zatrzymania. Byłby to prawidłowy sposób na wdrożenie całego języka.
Gilles 'SO - przestań być zły'
6

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.

feersum
źródło
To może zadziałać. Możliwym problemem jest to, że polega on na przydzieleniu nieograniczonej liczby va_listzmiennych automatycznych stack. Te zmienne muszą mieć adres &stack, a my możemy mieć tylko ich ograniczoną liczbę. Może ten wymóg można obejść, deklarując każdą zmienną lokalną register?
chi
@chi AIUI zmienna nie musi mieć adresu, chyba że ktoś spróbuje go pobrać. Ponadto nielegalne jest deklarowanie argumentu bezpośrednio poprzedzającego elipsę register.
feersum
Zgodnie z tą samą logiką, czy nie powinno intbyć wymagane, aby mieć granicę, chyba że ktoś użyje tej granicy lub sizeof(int)?
chi
@chi Wcale nie. Standard definiuje jako część abstrakcyjnej semantyki, że an intma wartość między niektórymi skończonymi granicami INT_MINa INT_MAX. A jeśli wartość intprzelewu przekroczy te związane, zachodzi niezdefiniowane zachowanie. Z drugiej strony standard celowo nie wymaga, aby wszystkie obiekty były fizycznie obecne w pamięci pod określonym adresem, ponieważ pozwala to na optymalizacje, takie jak przechowywanie obiektu w rejestrze, przechowywanie tylko części obiektu, reprezentując go inaczej niż standard układ lub całkowicie go pominąć, jeśli nie jest potrzebny.
feersum
4

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.

PyRulez
źródło
Jak wyglądałoby wdrożenie?
reinierpost
@reinierpost Zgaduję, że reprezentowałby dane przy użyciu jakiegoś policzalnego niestandardowego modelu PA. Obliczałby operacje arytmetyczne przy użyciu stopnia PA . Myślę, że każdy taki model powinien zapewniać poprawną implementację C.
PyRulez
Przepraszamy, to nie działa. sizeof(t)jest wartością typu size_t, więc jest naturalną liczbą całkowitą z zakresu od 0 do SIZE_MAX.
Gilles „SO- przestań być zły”
@Gilles SIZE_MAX również byłby wtedy niestandardowym zjawiskiem naturalnym.
PyRulez
To ciekawe podejście. Zauważ, że potrzebujesz również np. Intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t, aby być niestandardowym. W C ++ byłoby to sprzeczne z gwarancjami postępu ... nie jestem pewien co do C.
TLW
0

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.

Yves Daoust
źródło
Czy to nie jest główny punkt przyjętej odpowiedzi? Nie sądzę, aby dodało to nowych odpowiedzi do tego pytania z 2016 roku.
chi
@chi: nie, zaakceptowana odpowiedź nie wspomina o zamianie na pamięć zewnętrzną, co można by uznać za obejście.
Yves Daoust
-1

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ć.]

doktor
źródło
7
Nie sądzę, że to odpowiada na pytanie. Pytanie już przewidywało tę odpowiedź i wyjaśniło, dlaczego jest ona nieprawidłowa: „chociaż standard C pozwala na dowolne duże size_t, musi być ustalony na pewnej długości i bez względu na to, na jakiej długości jest ustalony, jest wciąż skończony „. Czy masz odpowiedź na ten argument? Nie sądzę, abyśmy policzyli pytanie jako odpowiedź, chyba że odpowiedź wyjaśnia, dlaczego ten argument jest zły (lub słuszny).
DW
5
W dowolnym momencie wartość typu size_tjest skończona. Problem polega na tym, że nie można ustalić powiązania, size_tktóre jest ważne podczas obliczeń: dla dowolnego powiązania program może go przepełnić. Ale język C stwierdza, że ​​istnieje granica size_t: w danej implementacji może ona rosnąć tylko do sizeof(size_t)bajtów. Ponadto, byłoby miło . Mówienie, że ludzie, którzy cię krytykują „nie mogą myśleć samodzielnie”, jest niegrzeczne.
Gilles 'SO - przestań być zły'
1
To jest poprawna odpowiedź. Maszyna tokarska nie wymaga taśmy nieskończonej, wymaga taśmy „arbitralnie długiej”. Oznacza to, że można założyć, że taśma jest tak długa, jak to konieczne, aby zakończyć obliczenia. Możesz również założyć, że komputer ma tyle pamięci, ile potrzebuje. Nieskończona taśma absolutnie nie jest wymagana, ponieważ żadne obliczenia, które zatrzymają się w skończonym czasie, nie mogą użyć nieskończonej ilości taśmy.
Jeffrey L Whitledge
Ta odpowiedź pokazuje, że dla każdej TM można napisać implementację C o wystarczającej długości wskaźnika, aby ją zasymulować. Nie jest jednak możliwe napisanie jednej implementacji C, która może symulować dowolną bazę TM. Tak więc specyfikacja zabrania, aby jakakolwiek konkretna implementacja była kompletna. To też nie jest T-complete, ponieważ długość wskaźnika jest stała.
1
To kolejna poprawna odpowiedź, która jest ledwo widoczna z powodu niezdolności większości osób w tej społeczności. Tymczasem zaakceptowana odpowiedź jest fałszywa, a jej sekcja komentarzy jest strzeżona przez moderatorów usuwających krytyczne komentarze. Pa pa, cs.stackexchange.
xamid
-1

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.

David Richerby
źródło
3
Twierdzę, że jeśli definicja C nie wymaga takiej nieograniczonej pamięci zewnętrznej, nie można tego zaakceptować jako dowodu kompletności Turinga. (ISO 9899 nie wymaga oczywiście, aby była napisana dla inżynierii w świecie rzeczywistym). Niepokoi mnie to, że jeśli to zaakceptujemy, z podobnego rozumowania możemy twierdzić, że DFA są kompletne, ponieważ można je wykorzystać do prowadzenia głowy nad taśmą (pamięć zewnętrzna).
chi
@chi Nie rozumiem, jak następuje argument DFA. Chodzi o to, że DFA ma dostęp tylko do odczytu do pamięci. Jeśli pozwolisz mu „prowadzić głowę nad taśmą”, czy nie jest to dokładnie maszyna Turinga?
David Richerby,
2
Rzeczywiście, trochę tu podrywam. Chodzi o to: dlaczego można dodawać „taśmę” do C, pozwolić C symulować DFA i wykorzystać ten fakt, aby twierdzić, że C jest zakończony Turing, skoro nie możemy zrobić tego samego z DFA? Jeśli C nie ma sposobu na samodzielne zaimplementowanie niepowiązanej pamięci, nie należy uważać Turing za ukończoną. (Nadal nazwałbym to „moralnie” Turingiem przynajmniej ukończonym, ponieważ granice są tak duże, że w praktyce nie mają znaczenia w większości przypadków) Myślę, że aby ostatecznie rozstrzygnąć sprawę, potrzebna byłaby ścisła formalna specyfikacja C (norma ISO nie wystarczy)
chi
1
@chi Jest OK, ponieważ C zawiera procedury we / wy pliku. DFA nie.
David Richerby,
1
C nie określa dokładnie, co robią te procedury - większość ich semantyki jest zdefiniowana implementacja. Implementacja AC nie jest wymagana do przechowywania zawartości pliku, na przykład myślę, że może zachowywać się tak, jakby każdy plik miał „/ dev / null”, że tak powiem. Nie jest również wymagane przechowywanie nieograniczonej ilości danych. Powiedziałbym, że twój argument jest poprawny, gdy rozważasz, co robi znaczna większość implementacji języka C, i uogólniasz to zachowanie na idealną maszynę. Jeśli ściśle polegamy tylko na definicji C, zapominając o praktyce, nie sądzę, że się to trzyma.
chi
-2

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_MAXO(2size_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.

Nathan Davis
źródło
6
Co printf("%zu\n",SIZE_MAX);wydrukuje na takiej implementacji?
Ruslan
1
@ Ruslan, taka implementacja jest niemożliwa, podobnie jak niemożliwa jest implementacja maszyny Turinga. Ale gdyby taka implementacja była możliwa, wyobrażam sobie, że wydrukowałaby ona dziesiętną reprezentację nieskończenie dużej liczby - prawdopodobnie nieskończonego strumienia cyfr dziesiętnych.
Nathan Davis,
2
@NathanDavis Możliwe jest wdrożenie maszyny Turinga. Sztuka polega na tym, że nie musisz budować nieskończonej taśmy - po prostu buduj zużytą część taśmy stopniowo, w razie potrzeby.
Gilles 'SO - przestań być zły'
2
@Gilles: W tym skończonym wszechświecie, w którym żyjemy, niemożliwe jest wdrożenie maszyny Turinga.
gnasher729
1
@NathanDavis Ale jeśli to zrobisz, zmienisz sizeof(size_t)(lub CHAR_BITS). Nie możesz wznowić od nowego stanu, musisz zacząć od nowa, ale wykonanie programu może być inne teraz, gdy te stałe są różne
Gilles 'SO - przestań być zły'
-2

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ę).

Eugene
źródło
1
„Różnica między tymi dwoma może być NaN”. Nie to nie może być. Nie ma czegoś takiego jak NaN typu całkowitego w C.
TLW
Zgodnie ze standardem sizeofmusi zwrócić a size_t. Musisz więc wybrać określoną wartość.
Draconis
-4

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

Xamid
źródło
4
Nie podążam za twoim ostatnim akapitem. Twierdzisz, że dodanie ograniczeń zwiększa siłę ekspresji, ale to oczywiście nie jest prawda. Ograniczenia mogą jedynie zmniejszyć siłę ekspresji. Na przykład, jeśli weźmiesz C i dodasz ograniczenie, że żaden program nie może uzyskać dostępu do więcej niż 640 kb pamięci (dowolnego rodzaju), zamienisz go w fantazyjny automat skończony, który najwyraźniej nie jest kompletny w Turinga.
David Richerby,
3
Jeśli masz stałą ilość miejsca, nie możesz symulować niczego, co wymaga więcej zasobów niż masz. Istnieje tylko skończona liczba konfiguracji, w których może znajdować się pamięć, co oznacza, że ​​jest tylko skończenie wiele rzeczy, które możesz zrobić.
David Richerby,
2
Nie rozumiem, dlaczego mówisz o „fizycznie istniejących maszynach”. Zauważ, że kompletność Turinga jest właściwością matematycznego modelu obliczeniowego, a nie układów fizycznych. Zgodziłbym się, że żaden system fizyczny, będący skończonym przedmiotem, nie może zbliżyć się do mocy maszyn Turinga, ale to nie ma znaczenia. Wciąż możemy wziąć dowolny język programowania, rozważyć matematyczną definicję jego semantyki i sprawdzić, czy ten obiekt matematyczny jest kompletny w Turingu. Gra życia Conwaya jest potężna w Turinga, nawet jeśli nie jest możliwa fizyczna implementacja.
chi
2
@xamid Jeśli masz obawy dotyczące zasad moderacji tej witryny, zanieś ją do Computer Science Meta . Do tego czasu bądź miły . Słowne znęcanie się nad innymi nie będzie tolerowane. (Usunąłem wszystkie komentarze, które nie dotyczą omawianego tematu.)
Raphael
2
Mówisz, że modyfikacja szerokości wskaźnika nie zmieni programu, ale programy mogą odczytać szerokość wskaźnika i zrobić wszystko, co chcą z tą wartością. To samo dotyczy CHAR_BITS.
Draconis