Z ist eine endliche Zustandsmenge.

\Gamma ist eine endliches Arbeitsalphabet und somit abzählbar.

\Gamma^{*}ist aufgrund des Satzes aus der Vorlesung ebenfalls abzählbar, da \Gamma abzählbar ist.

\Rightarrow Die Konfiguration k mit k\,\epsilon\,\Gamma^{*}Z\Gamma^{*} lässt sich durch eine geeignete Kodierung enummerieren und ist somit abzählbar.