Das wird heiß

Makarius

Programm für das zweiunddreißigste Treffen am 2. November 2017

Gepostet am 11. Okt 17 von uwap

Ingo wird mit uns die bei den letzten beiden Treffen begonnene Reise durch wundersame Phänomene der Logik abschließen.

Wir werden uns Beispielen und Anwendungen von Gödels Unvollständigkeitssatz in der theoretischen Informatik widmen: Es gibt Computerprogramme (offiziell Turingmaschinen), deren Halteverhalten unentscheidbar ist – von denen also bewiesen wurde, dass weder ein Beweis, dass sie halten, noch ein Beweis, dass sie nicht halten, möglich ist. Ein Resultat aus dem Jahr 2016 zeigt, dass solche Programme schon sehr kurz sein können.

Andere Programme verändern ihr Verhalten je nach dem, in welchem mathematischen Alternativuniversum sie ausgeführt werden. Was diese seltsam anmutende Behauptung bedeutet, und wie sich diese Programme in der realen Welt verhalten, wird im Vortrag klar werden.

Wir schließen mit einem besonderen binären Baum von Kleene und einem Beispiel, das zeigt, dass es Situationen gibt, in denen man nur mit Verwendung von Zufall weiterkommt und keine deterministische Alternative existiert.

Vielleicht holt außerdem marudor seinen schon zum letzten Treffen angekündigten Vortrag über typisiertes JavaScript nach.