Maksymalna moc obliczeniowa implementacji C.

28

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?

Gilles „SO- przestań być zły”
źródło
4
@Dave: Jak wyjaśnił Gilles, wydaje się, że możesz mieć nieograniczoną pamięć, ale nie ma możliwości bezpośredniego rozwiązania tego problemu.
Jukka Suomela
2
Z twojego wyjaśnienia wygląda na to, że każda implementacja C może być zaprogramowana tylko do akceptowania języków akceptowanych przez deterministyczne automaty wypychające, które są słabsze niż nawet języki bezkontekstowe. To spostrzeżenie nie jest jednak moim zdaniem interesujące, ponieważ pytanie dotyczy niewłaściwego zastosowania asymptotyków.
Warren Schudy
3
Należy pamiętać, że istnieje wiele sposobów na wywołanie „zachowania zdefiniowanego w implementacji” (lub „niezdefiniowanego zachowania”). Ogólnie rzecz biorąc, implementacja może zapewnić np. Funkcje biblioteczne, które zapewniają funkcjonalność, która nie jest zdefiniowana w standardzie C. Wszystkie zapewniają „luki”, przez które można uzyskać dostęp, powiedzmy, do maszyny Turinga. Lub nawet coś znacznie silniejszego, na przykład wyrocznia, która rozwiązuje problem zatrzymania. Głupi przykład: zdefiniowane w implementacji zachowanie przekroczenia liczby podpisanych liczb całkowitych lub konwersji liczb całkowitych może pozwolić na dostęp do takiej wyroczni.
Jukka Suomela
7
Nawiasem mówiąc, dobrym pomysłem może być dodanie tagu „rekreacyjny” (lub cokolwiek, czego używamy do śmiesznych łamigłówek), aby ludzie nie traktowali tego zbyt poważnie. Jest to oczywiście „niewłaściwe pytanie”, ale uznałem to za zabawne i intrygujące. :)
Jukka Suomela
2
@Jukka: Fajny pomysł. Na przykład przepełnienie X = zapisz X / 3 na taśmie i przejdź w kierunku X% 3, niedopełnienie = wyzwolić sygnał odpowiadający symbolowi na taśmie. To trochę przypomina nadużycie, ale zdecydowanie jest w duchu mojego pytania. Czy możesz napisać to jako odpowiedź? (@others: Nie to, że chcę zniechęcić inne takie sprytne sugestie!)
Gilles „SO- przestańcie być źli”

Odpowiedzi:

8

unsigned charunsigned char*sizeof(unsigned char*)sizeof(unsigned char *)unsigned charUCHAR_MAXsizeof(unsigned char)101010

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_MAXsizeof(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.

supercat
źródło
Przy takiej maszynie, co zwróciłoby sizeof (char)?
TLW
1
@TLW: Tak jak każda inna maszyna: 1. Makra CHAR_BITS i CHAR_MAX byłyby jednak nieco bardziej problematyczne; Standard nie dopuszczałby koncepcji typów, które nie mają granic.
supercat
Ups, miałem na myśli CHAR_BITS, jak powiedziałeś, przepraszam.
TLW
7

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.

Jared
źródło
Ale maszyny Turinga z taśmą nieskończenie postępującą tylko w jednym kierunku są tak samo wydajne jak maszyny Turinga z taśmą nieskończenie postępującą w dwóch kierunkach. Oprócz tego harmonogram może symulować wiele wątków. W każdym razie nie potrzebujemy nawet biblioteki wątków.
xamid
3

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

Marzio De Biasi
źródło
3
stackernewcellstacker2n/sns=sizeof(cell_t)
@Gilles: masz rację (zobacz moją edycję); jeśli ograniczysz głębokość rekurencji, otrzymasz skończony automat
Marzio De Biasi,
@MarzioDeBiasi Nie, myli się, ponieważ odnosi się do konkretnej implementacji, której standard nie zakłada. W rzeczywistości, nie ma teoretycznych ograniczeń co do głębokości rekursji w C . Wybór implementacji opartej na ograniczonym stosie nie mówi nic o teoretycznych ograniczeniach języka. Ale kompletność Turinga jest teoretycznym ograniczeniem.
xamid
0

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?

maska ​​bitowa
źródło
5
Co to jest „wskaźnik stosu”? (Zauważ, że słowo „stos” nie pojawia się w standardzie C.) Moje pytanie dotyczy C jako klasy języków formalnych, a nie implementacji C na komputerze (które są oczywiście skończonymi maszynami stanu). Jeśli chcesz uzyskać dostęp do stosu wywołań, musisz to zrobić w sposób podany przez język. Na przykład biorąc adres argumentów funkcji - ale każda implementacja ma tylko skończoną liczbę adresów, co następnie ogranicza głębokość rekurencji.
Gilles „SO- przestań być zły”
Zmodyfikowałem swoją odpowiedź, aby wykluczyć użycie wskaźnika stosu.
maska ​​bitowa
1
Nie rozumiem, dokąd zmierzasz z poprawioną odpowiedzią (oprócz zmiany sformułowania z funkcji obliczeniowych na rozpoznane języki). Ponieważ funkcje mają również adres, potrzebujesz implementacji wystarczająco dużej, aby zaimplementować dowolną maszynę skończoną. Powstaje pytanie, czy i w jaki sposób realizacja C może zrobić więcej (powiedzmy, realizować uniwersalną maszynę Turinga) bez polegania na un zdefiniowane zachowanie.
Gilles „SO- przestań być zły”
0

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();
}

{anbncn}

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();
}
Ben Standeven
źródło
Cóż, nie jest to podstawowy błąd, ale it = *itnależy go zastąpić it = * (void **) it, ponieważ w przeciwnym razie *itjest to rodzaj void.
Ben Standeven,
Byłbym bardzo zaskoczony, gdyby podróżowanie po stosie wywołań było zdefiniowane w C.
Radu GRIGore 12.12
Och, to nie zadziała, ponieważ pierwsze „b” powoduje błąd read_a (), a zatem powoduje odrzucenie.
Ben Standeven
Ale uzasadnione jest podróżowanie stosem wywołań w ten sposób, ponieważ standard C mówi: „Dla takiego obiektu [tj. Takiego z automatycznym przechowywaniem], który nie ma typu tablicy o zmiennej długości, jego żywotność wydłuża się od wejścia do bloku z który jest skojarzony, dopóki wykonanie tego bloku nie zakończy się w żaden sposób. (Wprowadzenie zamkniętego bloku lub wywołanie funkcji zawiesza, ale nie kończy, wykonanie bieżącego bloku.) Jeśli blok zostanie wprowadzony rekurencyjnie, nowa instancja obiektu jest tworzony za każdym razem. ” Tak więc każde wywołanie read_triple stworzy nowy wskaźnik, którego można użyć w rekursji.
Ben Standeven
2
2CHAR_BITsizeof(char*)
0

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*N{0,1}sizeof(unsigned char*){0,1}sizeof(unsigned char)Nsizeof(unsigned char*)Nω

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

sizeofZ

Alexey B.
źródło
1
Zdefiniowano wiele operacji na typach całkowych, aby uzyskać wynik „moduł mniejszy o jeden więcej niż maksymalna wartość reprezentowana w typie wyniku”. Jak by to działało, gdyby to maksimum było nieskończoną liczbą porządkową?
Gilles „SO- przestań być zły”
@Gilles To interesujący punkt. Rzeczywiście nie jest jasne, jaka byłaby semantyka uintptr_t p = (uintptr_t)sizeof(void*)(umieszczanie \ omega w czymś, co zawiera nieoznaczone liczby całkowite). Nie wiem. Możemy uciec od zdefiniowania wyniku jako 0 (lub dowolnej innej liczby).
Alexey B.
1
uintptr_tteż musiałby być nieskończony. Pamiętaj, że ten typ jest opcjonalny - ale jeśli masz nieskończoną liczbę różnych wartości wskaźnika, sizeof(void*)musi być również nieskończony, więc size_tmusi być nieskończony. Mój sprzeciw wobec modulo redukcji nie jest jednak tak oczywisty - wchodzi w grę tylko wtedy, gdy występuje przepełnienie, ale jeśli zezwolisz na nieskończone typy, mogą one nigdy się nie przepełnić. Ale w chwytającej ręce każdy typ ma wartości minimalne i maksymalne, które, o ile wiem, sugerują, że UINT_MAX+1muszą się przepełnić.
Gilles „SO - przestań być zły”,
Również dobra uwaga. Rzeczywiście, otrzymujemy kilka rodzajów (wskaźniki i size_t), które powinny być ℕ, ℤ, lub niektóre oparte na nich konstrukcje (dla size_t, jeśli byłoby coś takiego jak ℕ ∪ {ω}). Teraz, jeśli w przypadku niektórych z tych typów standard wymaga makra określającego maksymalną wartość (PTR_MAX lub coś w tym rodzaju), wszystko stanie się owłosione. Ale do tej pory byłem w stanie sfinansować wymaganie makr MIN / MAX dla typów niepochodzących ze wskaźnika.
Alexey B.
Inną możliwością zbadania jest zdefiniowanie obu size_ttypów wskaźników i ℕ ∪ {ω}. Pozbywa się to problemu min./maks. Nadal pozostaje problem z semantyką przepełnienia. To, co powinno być semantyką, uint x = (uint)ωnie jest dla mnie jasne. Znów możemy przypadkowo przyjąć 0, ale wygląda to trochę brzydko.
Alexey B.,