Man entwerfe ein Computer-Programm (Pseudocode), das zu einer vorgegebenen natürlichen Zahl ${\displaystyle {}n}$ entscheidet, ob ${\displaystyle {}n}$ gerade oder ungerade ist.

• Der Computer besitzt beliebig viele Speicher, die natürliche Zahlen enthalten können.
• Er kann einen Speicher leeren.
• Er kann einen Speicherinhalt um ${\displaystyle {}1}$ erhöhen.
• Er kann zu einem bestimmten Befehl springen.
• Er kann Speicherinhalte miteinander vergleichen und abhängig davon zu einem bestimmten Befehl springen.
• Er kann Speicherinhalte ausdrucken und vorgegebene Texte ausdrucken.
• Es gibt einen Haltebefehl.

Die Anfangskonfiguration sei

${\displaystyle (n,0,0,0,0,0,0,\ldots ).}$

${\displaystyle {}n}$

${\displaystyle {}n}$