Prozedur stoppt-collatz-bis?

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur stoppt-collatz-bis?, die eine Zahl n als Eingabe erwartet und feststellt, ob die endlichen Collatzfolgen für i=\text{ }2,3,...,n existieren.

Lösung

Beweis

Aufgabenstellung

Beweisen Sie, dass f_{total} nicht berechenbar ist, d.h. eine Prozedur totalmacher für f_{total} , die eine partielle zahlentheoretische Funktion f_{partiell} nimmt, gibt es nicht.

Lösung

Turingmaschine (TM) und RADOsche Funktion

Aufgabenstellung

Machen Sie sich mit dem in AtoCC eingebauten TM-Modell vertraut. Tragen Sie einige TM zusammen, die das Busy-Beaver-Problem für kleinere n lösen. Verwenden Sie AtoCC, um diese zu simulieren.

Lösung

Beweis

Aufgabenstellung

Zeigen Sie, dass die Vereinigungsmenge M_1 \cup M_2 zweier aufzählbarer Mengen M_1 \subseteq A^* und M_2 \subseteq A^* wiederum eine aufzählbare Menge ist.

Lösung