5.3Berechenbarkeit und Turing-Maschinen

Weitere Berechnungsmodelle

Loop, While, Goto und rekursive Funktionen: Welche Sprachmittel braucht man für volle Berechnungsstärke?

Leitformel
LOOP⊊WHILE=GOTO=TM\text{LOOP} \subsetneq \text{WHILE} = \text{GOTO} = \text{TM}
LOOP⊊WHILE\text{LOOP} \subsetneq \text{WHILE}=GOTO=TM= \text{GOTO} = \text{TM}
Lernziel

Loop-, While- und Goto-Programme schreiben, ihre Berechnungsstärke vergleichen und primitiv- sowie μ-rekursive Funktionen einordnen.

Einheit wird geladen …