C
Die Argumentation oben zeigt "direkt", dass Σ nicht berechenbar ist. Nachdem ich nochmal drüber nachgedacht habe, ist mir klar geworden, dass es auch kürzer geht: Man könnte Σ aufs Halteproblem zurückführen, das bekanntermaßen nicht entscheidbar ist (darüber gibt's sehr viele Artikel). Wenn dir das Halteproblem nichts sagt, ist die Argumentation im letzten Posting vielleicht trotzdem leichter einzusehen.
"Aufs Halteproblem zurückführen" bedeutet hier folgendes: Angenommen Σ ist berechenbar, dann können wir für beliebige Turingmaschinen M entscheiden, ob sie terminiert oder nicht.
Angenommen Σ ist berechenbar. Sei M eine beliebige Turingmaschine. Betrachte die Turingmaschine N, die M simuliert und in jedem Simulationsschritt eine 1 aufs Band schreibt (und zwar so, dass die Simulation dadurch nicht gestört wird).
Nachdem die Maschine N die Maschine M für n Zeitschritte simuliert hat, stehen mindestens n viele 1en auf dem Band, nach Konstruktion von N. Außerdem terminiert N genau dann, wenn M terminiert.
Angenommen, N hat k Zustände. Dann kann N maximal Σ(k) viele 1en aufs Band geschrieben haben, wenn es terminiert. Das ist die Definition von Σ(k).
Wenn Σ(k) jetzt berechenbar wäre, könnten wir einfach N solange laufen lassen, bis mehr als Σ(k) viele 1en auf dem Band stehen, und zwar so, dass die Maschine M für mehr als Σ(k) Schritte simuliert wurde. Dann steht wegen der Definition von Σ(k) fest, dass N nicht mehr terminieren wird.
Denn würde N terminieren, dürften am Ende maximal Σ(k) viele 1en auf dem Band sein. Die 1en, die die Simulationsschritte zählen, werden aber nie weniger. Wenn N also schon Σ(k) viele Simulationsschritte durchgeführt hat, ist klar, dass es nicht mehr terminieren kann.
Wenn N nicht terminiert, terminiert auch M nicht. Wenn Σ berechenbar ist, könnten wir also in endlicher Zeit entscheiden, ob eine beliebige Turingmaschine M terminiert oder nicht. Das ist aber unmöglich, also ist Σ nicht berechenbar.
