To nie jest ogólna odpowiedź na twoje pytanie, ale dzięki twierdzeniu o programowaniu strukturalnym wszystko, czego potrzeba, to umiejętność wyboru (np. ifW C / C ++) i powtarzania (np. whileW C / C ++). Edycja: jak zauważył Dave Clarke w komentarzach, twierdzenie o programowaniu strukturalnym również wymaga sekwencji. Początkowo nie wymieniłem tego, ponieważ uważałem za oczywiste, że czytelnik zrozumie, że podstawowe bloki innych instrukcji, takich jak te, do których później nawiązywał odczyt i zapis do pamięci itp., Były również konieczne). Oczywiście lepiej jest być wyraźnym; musisz także móc robić te rzeczy.
Ponieważ oba z nich można zaimplementować za pomocą instrukcji skoku warunkowego (np. JNZW x86), jest to również wystarczające dla równoważności Turinga.
Zauważ, że wymagane są inne rzeczy, tj. Możliwość zapisu nieograniczonej liczby symboli (np. Bitów ... 0 lub 1) w jakimś zewnętrznym magazynie pamięci. W tym sensie prawdziwe komputery nie są odpowiednikami Turinga, ponieważ żaden z nich nie ma nieskończonej ilości pamięci. Model Turinga jest jednak nadal użyteczny, ponieważ ilość pamięci jest zwykle ogromna i chociaż każdy problem, który może rozwiązać prawdziwy komputer, może zostać rozwiązany przez deterministyczny automat skończony, użycie tego modelu obliczeniowego nie jest szczególnie przydatne (ponieważ liczba stanów byłaby niedorzecznie ogromna).
Zauważ, że niekoniecznie jest to sprzeczne z odpowiedzią sepp2k; to jest po prostu inny sposób myślenia o tym samym pytaniu.
EDYTOWAĆ:
Należy również zauważyć, że tak naprawdę nie potrzebują zarówno ifa whilew C / C ++. Możesz przeprowadzić symulację ifza pomocą while:
bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program
Poniższy kod jest zawsze równoważny:
bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program
Cóż ... konstrukcja powinna działać i być możliwa, jeśli jesteś ostrożny. Zauważ też, że jeśli masz funkcje rekurencyjne, w końcu potrzebujesz również wyboru; ponieważ funkcje rekurencyjne bez wyboru nie mogą tak naprawdę implementować przypadków bazowych, więc każda funkcja rekurencyjna spowodowałaby nieskończoną rekurencję.
EDYTOWAĆ:
Ponadto, jeśli chodzi o twoje pytanie, czy umiejętność napisania programu, który nie zatrzymuje się, jest wystarczający dla równoważności Turinga, odpowiedź brzmi „nie”; jest to konieczne, ale niewystarczające. Możemy rozwiązać problem zatrzymania programów napisanych w języku, który nie potrafi wyrazić programów, które się nie zatrzymują; odpowiedź brzmi „program się zatrzymuje” dla wszystkich instancji. Możemy jednak zdefiniować język, w którym jedyna instrukcja powoduje, że maszyna wchodzi w nieskończoną pętlę ... taki język nie jest odpowiednikiem Turinga.