Show Notes
Mit dieser Folge nehme ich am Wettbewerb Fast Forward Science 2025 teil.
Dieses Mal geht’s wieder etwas in die theoretische Informatik. Ein paar sogenannte Hobbymathematiker*innen haben nämlich BB(5) berechnet, d.h. die maximale Laufzeit einer anhaltenden Turingmaschine mit 5 internen Zuständen.
Was das mit Berechenbarkeit, großen Zahlen und der Goldbachvermutung zu tun hat, bespreche ich hier in der Sommerfolge. Wir müssen nämlich nur noch bis BB(27) vorstoßen, bis wir die Goldbachvermutung algorithmisch lösen können. Kann aber noch dauern, denn BB(5) hat 41 Jahre gedauert.
- Scott Aaronson’s blog post on BB(5)
- The busy beaver frontier (vor Juli 2024)
- π=3 Große Zahlen
- BBchallenge.org
- Tolle interaktive Erklärung der Turingmaschine auf bbchallenge.org
- Hat Turing wirklich das Halteproblem diskutiert?
- LEGO Turingmaschine
- Code Golf
- Rado 1961 Paper On non-computable functions
- Bericht der GI-Konferenz von 1983
- Der fertige formale Coq-Beweis
- Eine 748-state Turingmaschine, die genau dann anhält, wenn ZFC inkonsistent ist.
- BB(5)-Artikel in Quanta Magazine
Feedback gerne auf Mastodon @[email protected], an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Verwandte Folge:
Ein automatisch generiertes Transkript (also den Volltext) dieser Folge gibt es auf der Episodenseite.