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_BIT
bity 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ć register
argumentów nieadresowalnych ( ). Zatem implementacja C, która pozwala na dowolną rekurencję i nie ma ograniczenia liczby register
obiektó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?
źródło
Odpowiedzi:
unsigned char
unsigned char*
sizeof(unsigned char*)
sizeof(unsigned char *)
unsigned char
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.
źródło
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.
źródło
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 :-)
head
Będzie wskaźnikiem docell_t
strukturystacker
funkcję, gdy odczytuje ostatni symbol taśmy wejściowej (za pomocą readchar)EDYCJA: po krótkiej refleksji pojawia się problem ze wskaźnikami ...
jeśli każde wywołanie funkcji rekurencyjnej
stacker
moż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).źródło
stacker
newcell
stacker
sizeof(cell_t)
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, aleb^k
działa tylko dla skończonej liczbyk
s).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?
źródło
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:
Przynajmniej myślę, że to działa. Możliwe jednak, że popełniam jakiś fundamentalny błąd.
Naprawiona wersja:
źródło
it = *it
należy go zastąpićit = * (void **) it
, ponieważ w przeciwnym razie*it
jest to rodzajvoid
.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
unsigned char*
sizeof(unsigned char*)
sizeof(unsigned char*)
W tym momencie należy sprawdzić, czy norma C rzeczywiście na to pozwala.
sizeof
źródło
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).uintptr_t
też 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ęcsize_t
musi 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ą, żeUINT_MAX+1
muszą się przepełnić.size_t
typó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.