Mam ostatnio zagwozdke. Teoretycznie (na podstawie tego co bylo na studiach) przy pomocy maszyny Turinga mozna napisac kazdy mozliwy program. Taka maszyne da sie napisac chyba w kazdym mozliwym jezyku.
I tutaj pojawia sie pytanie, czy to oznacza ze w kazdym jezyku TEORETYCZNIE (a najlepiej praktycznie) da sie zarzadzac bezposrednia pamiecia jak w C/C++?
Są różne formy pamięci.
Jeśli masz zaimplementowaną maszynę Turinga to jeszcze nie oznacza że masz dostęp do wszystkich poziomów pamięci (czyli "jak w C/C++").
Co najwyżej oznacza, że masz dostęp do jakiejś określonej puli pamięci i że możesz napisać dowolnie złożoną funkcję. Ale możliwe że nie będzie to w ogóle optymalne.
@WhiteLightning nie bardzo rozumiem gdzie ty widzisz związek między jednym a drugim. Bo zupełność języków programownia w sensie Turinga, oznacza że można w każdym z tych języków zapisać każdy możliwy algorytm, który da się zapisać dla Maszyny Turinga.
A ty tu mówisz i jakiejś technicznej realizacji tego algorytmu i o jakimś zarządzaniu pamięcią. Zauważ że Maszyna Turinga zakłada że dysponujesz "pamięcią" w ujęciu abstrakcyjnym - jako nieskończona taśma na której możesz coś zapisywać. To w jaki sposób dany język programowania / dany komputer udostępnia tą pamięć to jest szczegół implementacyjny i nie ma nic wspólnego z abstrakcyjnym modelem o którym mówimy!
Są tacy, którzy bujają w obłokach, a na fotelu mojego dziadka można się bujać, czy to znaczy, że jeśli położę na fotelu dziadka dwa kilogramy cebuli i paczkę fajek to oznacza, że wspomniana cebula i papierosy będą mogły bujać w obłokach?
Jaki model pamięci? Na pewno płaski? Chcesz napisać program dla x86? W C tworzysz wskaźnik uint8_t *wsk = NULL, a następnie go incrementujesz i decrementujesz. Musisz tylko uważać, by nie nadpisać kodu lub danych programu, a poza tym w komputerze nie masz nieograniczonej ilości pamięci, więc najlepiej posłużyć się tablicą.