Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
20
Gödelnummerierung
- ist injektive Abbildung von der Menge aller TMn in die Menge 
- Präfixfreiheit: keine Gödelnummer darf Anfangsteilwort einer anderen Gödelnummer sein (111 am Ende und nirgends sonst in der Kodierung)
Kodierung:
- Präfixfreiheit: keine Gödelnummer darf Anfangsteilwort einer anderen Gödelnummer sein (111 am Ende und nirgends sonst in der Kodierung)
Kodierung:
 | Menge der Zustände |
 | Anfangszustand (statt  ) |
 | Stoppzustand |
 mit  | Bandalphabet durchnummeriert |
 | mögliche Kopfbewegungen durchnummeriert |
 als  | Übergangsfunktion als Binärstring kodiert |
| <M>= code(1)11code(2)11...11code(s)111 | Kodierung des t-ten Übergangs ist code(t) |
