Der Barbier und die Unberechenbarkeit

In dem Satz "der Barbier rasiert genau die Leute, die sich nicht selbst rasieren" steckt ein Widerspruch, denn: Wer rasiert den Barbier? Nach diesem Muster lässt sich zu jedem Berechnungsmodell und jeder Programmiersprache eine Aufgabe formulieren, die sich damit nicht lösen lässt. Wo dabei jedoch im Einzelnen das Problem liegt, hängt vom jeweiligen Berechnungsmodell ab. Wir schauen uns in diesem Video zwei Modelle an: Die Loop-Sprache und die While-Sprache. Bei der While-Sprache besteht das Problem darin, dass man das Halteproblem nicht lösen kann.

0:00 Barbier-Paradoxon
3:45 Die "Barbier"-Sprache
7:29 Algorithmus zur "Barbier"-Sprache
11:22 Berechnungsmodell 1: Loop-Sprache
14:21 Berechnungsmodell 2: While-Sprache
17:24 Halteproblem

Videos zum Thema:
1.    • Die Loop-Sprache  
2.    • While kann mehr als Loop  
3.    • Der Barbier und die Unberechenbarkeit   (dieses Video)