Turingmaschinen Flashcards
Wie wird die Vollständigkeit eines Systems überprüft?
Vollständig heißt, wenn man die Wahrheit einer jeden Aussage nachweisen kann.
Was bedeutet, wenn ein System konsistent ist?
Ein System ist Konsistenz, wenn es innerhalb keine Widersprüche gibt.
Das System soll auch entscheidbar sein.
Entscheidbar heißt, es gibt einen Algorithmus, der die Wahrheit jeder Aussage ermitteln kann.
Woraus besteht eine Turingmaschine?
Q: Zustandsmenge E: Eingabealphabet, endlich pi: Ausgabe/Bandalphabet, endlich d: Zustandsübergnagsfunktion q0: Startzustand #: Leeres Feld F: Finalmenge
Welche fünf Elemente muss es in einer Turingmaschine geben?
- Linkszustand
- Rechtszustand
- Haltezustand
- Akzeptanzstand
- Ablehnungszustand
Welche fünf Elemente kann es in einer Turingmaschine geben?
- Linkszustand
- Rechtszustand
- Haltezustand
- Akzeptanzstand
- Ablehnungszustand
Mit welchen Datenstrukturen kann eine Turingmaschine in Java realisiert werden?
2 Stacks vom Typ Char
jeweils linke und rechte Seite vom Band
Wie ist ein Algorithmus definiert?
Eine TM, die eine Sprache entscheidet oder eine Funktion berechnet, repräsentiert einen Algorithmus für diese Aufgabe.
Wie viele final Zustände kann die Turingmaschine annehmen?
- Ja-Zustand
- Nein-Zustand
- Halte-Zustand
- Keine Lösung (Endlosschleife)
Wann erkennt eine TM eine Sprache?
Eine TM erkennt eine Sprache, die aus allen Eingangswörtern besteht, wenn sie die TM in einen Akzeptanzzustand führt.
Wann entscheidet eine TM eine Sprache?
Eine TM entscheidet eine Sprache, wenn die TM für alle Eingangswörter anhält und erkennt, dass sie nicht in derselben Sprache sind. Ja oder Nein Entscheidung.
Wann akzeptiert eine TM eine Sprache?
Die Eingabe wird genau dann akzeptiert, wenn die Turingmaschine in einem akzeptierenden Endzustand (ja Zustand) endet.
Was versteht man unter Berechenbarkeit?
kp
Was versteht man unter der universellen Turingmaschine?
Eine TM die, die Arbeitsweise einer TM simuliert wird als universelle TM bezeichnet.
Ist ein normaler Computer eine UTM?
Ja jeder PC ist auch einer UTM
