Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
kurse:ef05a-2021:turingmaschinen:pruefungsfragen [2021/09/09 09:28] Ivo Blöchliger |
kurse:ef05a-2021:turingmaschinen:pruefungsfragen [2021/10/20 10:29] (current) Ivo Blöchliger |
||
|---|---|---|---|
| Line 17: | Line 17: | ||
| * Sei $S(n,m)$ die maximale Anzahl Schritte, die eine TM mit $n$ Zuständen und einem Alphabet von $m$ Zeichen, auf einem leeren Band machen kann und am Schluss noch stoppt. Zeigen Sie, dass $S(n,m)$ eine nicht-berechenbare Funktion ist. | * Sei $S(n,m)$ die maximale Anzahl Schritte, die eine TM mit $n$ Zuständen und einem Alphabet von $m$ Zeichen, auf einem leeren Band machen kann und am Schluss noch stoppt. Zeigen Sie, dass $S(n,m)$ eine nicht-berechenbare Funktion ist. | ||
| + | {{kurse: | ||