Maksymalna moc obliczeniowa implementacji C.

Jeśli przejdziemy do tej książki (lub innej wersji specyfikacji języka, jeśli wolisz), ile mocy obliczeniowej może mieć implementacja języka C?

Należy zauważyć, że „implementacja C” ma znaczenie techniczne: jest to szczególna instancja specyfikacji języka programowania C, w której udokumentowano zachowanie zdefiniowane w implementacji. Implementacja AC nie musi być w stanie działać na rzeczywistym komputerze. Musi implementować cały język, w tym każdy obiekt mający reprezentację ciągu bitowego i typy o rozmiarze zdefiniowanym przez implementację.

Na potrzeby tego pytania nie ma pamięci zewnętrznej. Jedyne wejście / wyjście, które możesz wykonać, to getchar(aby odczytać wejście programu) i putchar(aby zapisać wyjście programu). Również każdy program, który wywołuje niezdefiniowane zachowanie, jest nieprawidłowy: jego zachowanie musi być zdefiniowane w specyfikacji C plus opis implementacji zachowań zdefiniowanych w implementacji wymieniony w załączniku J (dla C99). Zauważ, że wywoływanie funkcji bibliotecznych, które nie są wymienione w standardzie, jest niezdefiniowanym zachowaniem.

Moja początkowa reakcja była taka, że ​​implementacja C jest niczym więcej niż automatem skończonym, ponieważ ma ograniczenie ilości adresowalnej pamięci (nie można adresować więcej niż sizeof(char*) * CHAR_BITbity pamięci, ponieważ różne adresy pamięci muszą mieć różne wzorce bitów podczas przechowywania we wskaźniku bajtowym).

Myślę jednak, że wdrożenie może zrobić więcej. O ile mi wiadomo, standard nie nakłada żadnych ograniczeń na głębokość rekurencji. Możesz więc wykonywać tyle rekurencyjnych wywołań funkcji, ile chcesz, tylko wszystkie oprócz ograniczonej liczby wywołań muszą używać registerargumentów nieadresowalnych ( ). Zatem implementacja C, która pozwala na dowolną rekurencję i nie ma ograniczenia liczby registerobiektów, może kodować deterministyczne automaty wypychające.

Czy to jest poprawne? Czy możesz znaleźć mocniejszą implementację C? Czy istnieje kompletna implementacja C Turinga?

unsigned charunsigned char*sizeof(unsigned char*)sizeof(unsigned char *)unsigned char$UCHAR\_MAX ^{sizeof(unsigned\ char*)}$$10^{10^{10}}$

Program może przechowywać nieograniczoną ilość informacji na stosie, jeśli nigdy nic nie zostanie przydzielone na stosie ; można więc mieć program C zdolny do robienia pewnych rzeczy, których nie mógłby wykonać żaden automat skończony dowolnej wielkości. Zatem, chociaż (a może dlatego, że) dostęp do zmiennych stosu jest znacznie bardziej ograniczony niż dostęp do zmiennych dynamicznie przydzielanych, zmienia C z automatu skończonego w automat popychający.

$UCHAR\_MAX ^{sizeof(unsigned\ char*)}$możliwe sekwencje wartości znaków, jakikolwiek program, który utworzył pewną liczbę wskaźników dla różnych obiektów ponad to, nie byłby zgodny ze standardem C, gdyby kod kiedykolwiek zbadał sekwencję znaków związanych z tymi wskaźnikami . W niektórych przypadkach kompilator mógłby jednak stwierdzić, że żaden kod nigdy nie będzie badał sekwencji znaków powiązanych ze wskaźnikiem. Jeśli każdy „char” rzeczywiście był w stanie pomieścić skończoną liczbę całkowitą, a pamięć maszyny była niezliczoną liczbą liczb całkowitych [biorąc pod uwagę maszynę Turinga z nieograniczoną taśmą, można by emulować taką maszynę, chociaż byłaby ona naprawdę wolna], to rzeczywiście można by uczynić język C kompletnym językiem Turinga.

Dzięki opcjonalnej bibliotece wątków C11 możliwe jest wykonanie pełnej implementacji Turinga przy nieograniczonej głębokości rekurencji.

Utworzenie nowego wątku daje drugi stos; dwa stosy wystarczą do ukończenia Turinga. Jeden stos reprezentuje to, co jest na lewo od głowy, drugi stos, co jest na prawo.

Myślę, że jest to ukończenie Turinga : możemy napisać program symulujący UTM za pomocą tej sztuczki (szybko napisałem kod ręcznie, więc prawdopodobnie są pewne błędy składniowe ... ale mam nadzieję, że nie ma (poważnych) błędów w logice :-)

• zdefiniuj strukturę, która może być używana jako podwójnie połączona lista do reprezentacji taśmy

    typdef struct {
      cell_t * pred; // komórka po lewej stronie
      cell_t * succ; // komórka po prawej stronie
      int val; // wartość komórki
    } cell_t 

headBędzie wskaźnikiem do cell_tstruktury

• zdefiniuj strukturę, której można użyć do przechowywania bieżącego stanu i flagi

    typedef struct {
      stan wewnętrzny;
      flaga int;
    } info_t 

• następnie zdefiniuj funkcję pojedynczej pętli, która symuluje Universal TM, gdy głowa znajduje się między granicami podwójnie połączonej listy; gdy głowa uderzy w granicę, ustaw flagę struktury info_t (HIT_LEFT, HIT_RIGHT) i zwróć:

void simulate_UTM (cell_t * head, info_t * info) {
  podczas gdy (prawda) {
    head-> val = UTM_nextsymbol [info-> state, head-> val]; // napisz symbol
    info-> state = UTM_nextstate [info-> state, head-> val]; // następny stan
    if (info-> state == HALT_STATE) {// wydrukuj, jeśli zaakceptuje i wyjdź z programu
       putchar ((info-> state == ACCEPT_STATE)? '1': '0');
       wyjście (0);
    }
    int move = UTM_nextmove [info-> state, head-> val];
    if (move == MOVE_LEFT) {
      głowa = głowa-> pred; // przesuń w lewo
      if (head == NULL) {info-> flag = HIT_LEFT; powrót; }
    } else {
      głowa = głowa-> sukc; // ruch w prawo
      if (head == NULL) {info-> flag = HIT_RIGHT; powrót; }
    }
  } // wciąż na granicy ... kontynuuj
}

• następnie zdefiniuj funkcję rekurencyjną, która najpierw wywołuje procedurę symulacji UTM, a następnie wywołuje się rekurencyjnie, gdy taśma wymaga rozszerzenia; kiedy taśma musi zostać rozwinięta na górze (HIT_RIGHT), nie ma problemów, kiedy musi zostać przesunięta na dole (HIT_LEFT), wystarczy przesunąć w górę wartości komórek za pomocą podwójnie połączonej listy:

void stacker (cell_t * góra, cell_t * dół, cell_t * head, info_t * info) {
  simulate_UTM (głowa, informacje);
  cell_t newcell; // nowa komórka
  newcell.pred = top; // zaktualizuj podwójnie połączoną listę o nową komórkę
  newcell.succ = NULL;
  top-> succ = & newcell;
  newcell.val = EMPTY_SYMBOL;

  przełącznik (informacje -> hit) {
    przypadek HIT_RIGHT:
      układacz (& newcell, bottom, newcell, info);
      złamać;
    sprawa HIT_BOTTOM:
      cell_t * tmp = newcell;
      while (tmp-> pred! = NULL) {// zmiana wartości w górę
        tmp-> val = tmp-> pred-> val;
        tmp = tmp-> pred;
      }
      tmp-> val = EMPTY_SYMBOL;
      układacz (& newcell, bottom, bottom, info);
      złamać;
  }
}

• początkowa taśma może być wypełniona prostą funkcją rekurencyjną, która tworzy podwójnie połączoną listę, a następnie wywołuje stackerfunkcję, gdy odczytuje ostatni symbol taśmy wejściowej (za pomocą readchar)

void init_tape (cell_t * góra, cell_t * dół, info_t * informacje) {
  cell_t newcell;
  int c = readchar ();
  if (c == END_OF_INPUT) układarka (& top, bottom, bottom, info); // koniec symboli, zacznij
  newcell.pred = top;
  if (top! = NULL) top.succ = & newcell; else bottom = & newcell;
  init_tape (& newcell, bottom, info);
}

EDYCJA: po krótkiej refleksji pojawia się problem ze wskaźnikami ...

jeśli każde wywołanie funkcji rekurencyjnej stackermoże utrzymywać poprawny wskaźnik do zmiennej zdefiniowanej lokalnie w wywołującym, wówczas wszystko jest w porządku ; w przeciwnym razie mój algorytm nie będzie w stanie utrzymać prawidłowej podwójnie połączonej listy na nieograniczonej rekurencji (iw tym przypadku nie widzę sposobu na użycie rekurencji do symulacji nieograniczonej pamięci o dostępie swobodnym).

Tak długo, jak masz nieograniczony rozmiar stosu wywołań, możesz zakodować taśmę na stosie wywołań i uzyskać do nich dostęp losowy, przewijając wskaźnik stosu bez powrotu z wywołań funkcji.

Edycja : Jeśli możesz użyć tylko barana, który jest skończony, ta konstrukcja już nie działa, więc patrz poniżej.

Jest jednak wysoce wątpliwe, dlaczego twój stos może być nieskończony, ale wewnętrzny RAM nie jest. Powiedziałbym więc, że nawet nie rozpoznajesz wszystkich zwykłych języków, ponieważ liczba stanów jest ograniczona (jeśli nie policzysz sztuczki przewijania stosu w celu wykorzystania nieskończonego stosu).

Spekulowałbym nawet, że liczba języków, które można rozpoznać, jest skończona (nawet jeśli same języki mogą być nieskończone, np. a*Jest w porządku, ale b^kdziała tylko dla skończonej liczby ks).

EDYCJA : To nie jest prawda, ponieważ możesz zakodować aktualny stan w dodatkowych funkcjach, dzięki czemu możesz naprawdę rozpoznać WSZYSTKIE zwykłe języki.

Najprawdopodobniej możesz dostać wszystkie języki Type-2 z tego samego powodu, ale nie jestem pewien, czy uda ci się umieścić zarówno stan, jak i stałą stosu na stosie wywołań. Ale ogólnie rzecz biorąc, możesz skutecznie zapomnieć o pamięci RAM, ponieważ zawsze możesz skalować rozmiar automatu, aby Twój alfabet przekroczył pojemność pamięci RAM. Więc jeśli mógłbyś zasymulować TM tylko ze stosem, Typ 2 byłby równy Typowi 0, prawda?

Pomyślałem o tym raz i postanowiłem spróbować wdrożyć język bezkontekstowy, używając oczekiwanej semantyki; kluczową częścią wdrożenia jest następująca funkcja:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

$\{a^n b^n c^n\}$

Przynajmniej myślę, że to działa. Możliwe jednak, że popełniam jakiś fundamentalny błąd.

Naprawiona wersja:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

Wzdłuż linii odpowiedzi @ supercat:

Twierdzenia o niekompletności C wydają się być skoncentrowane wokół tego, że różne obiekty powinny mieć różne adresy, a zbiór adresów przyjmuje się za skończony. Jak pisze @supercat

Jak zauważono w pytaniu, standard C wymaga, aby istniała wartość UCHAR_MAXtaka, że ​​każda zmienna typu bez znaku char zawsze będzie miała wartość od 0 do UCHAR_MAXwłącznie. Wymaga to ponadto, aby każdy dynamicznie przydzielany obiekt był reprezentowany przez sekwencję bajtów, którą można zidentyfikować za pomocą wskaźnika typu unsigned char *, oraz aby istniała stała sizeof(unsigned char*)taka, że ​​każdy wskaźnik tego typu może być identyfikowany przez sekwencję sizeof(unsigned char *)wartości typu unsigned char zwęglać.

unsigned char*$\mathbb{N}$$\{0, 1\}$sizeof(unsigned char*)$\{0, 1\}^{\operatorname{sizeof}(\mathit{unsigned\ char*})}$$\mathbb{N}$sizeof(unsigned char*)$\mathbb{N}$$\omega$

W tym momencie należy sprawdzić, czy norma C rzeczywiście na to pozwala.

sizeof$\in \mathbb Z$