Multiway Turing Machines: Überraschende Komplexität in den einfachsten Regeln

Multiway Turing Machines (2021 pre-ai)

In diesem Beitrag untersucht Stephen Wolfram Multiway-Turingmaschinen (auch nichtdeterministische Turingmaschinen genannt) als minimale Modelle für nebenläufiges Rechnen und Quantenmechanik. Er zeigt, dass schon Regeln mit nur zwei Fällen erstaunlich komplexe Multiway-Graphen erzeugen können, und diskutiert die Grenze zur Universalität. Die Arbeit verbindet Konzepte aus seinem Physikprojekt, wie Multispace und Branchialraum, mit der Theorie der Turingmaschinen.