Informationsdämpfung als Basis eines stochastischen Algorithmus zur Lösung des SAT-Problems

Informationsdämpfung als Basis eines stochastischen Algorithmus zur Lösung des SAT-Problems

Das „Game of Life“ ist ein mathematisches Computerspiel, bei dem auf einer Art Schachbrett viele Zellen nebeneinanderliegen, die entweder „lebendig“ oder „tot“ sind. Im Spielverlauf dürfen manchen Zellen gemäß bestimmter Regeln weiterleben, andere müssen sterben. Das Erstaunliche daran: Trotz einfacher Vorschriften können komplexe, sich bei jedem Spielschritt verändernde Muster entstehen. Joshua Meyer untersuchte in seinem Projekt zunächst, unter welchen Voraussetzungen diese Muster regelrecht einfrieren und zum Stillstand kommen können. Dann versuchte er seine Erkenntnisse auf einen anderen mathematischen Bereich zu übertragen, die Logik. Verblüffenderweise funktioniert das überaus gut – heraus kam ein Algorithmus, der im Prinzip für den Entwurf elektronischer Schaltung verwendet werden könnte.