Berechenbarkeit Flashcards
Was besagt die Church-Turing These?
Eine universelle TM kann jede Berechnung durchführen, die durch jedes Physikalisch realisierbare Rechengerät beschrieben werden kann.
Wird die TM durch das Hinzufügen eines weiteren Bandes noch mächtiger?
Nein ein weiteres Band macht die TM nicht mächtiger.
Wird die TM mächtiger durch das Hinzufügen von Nichtdeterminismus?
nein
Wie kann man eine Begrenzung der TM erreichen?
- Durch das Begrenzen des Bandes auf beiden Seiten.
- Überschreiben von Symbolen ist geblockt
- streichen von Links und Haltezustand bzw. rechts und Haltezustand
Wie heiß der Typ Sprache die, die TM darstellen kann?
Type-0 Sprachen
Wann ist ein Modell Turing-vollständig?
Modell kann gleiche Menge
- von sprachen erkennen
- an Funktionen berechnen.
Wie heißen die drei TM-äquivalenten Modelle?
- Lambda Kalkül
- Zählmaschinen
- Zellulärer Automat
Der Computer ist genauso mächtig wie eine TM?
Ja
Sind alle Programmiersprachen Turing-vollständig?
Ja
Unterscheiden sich durch: Instandhaltung, Übertragbarkeit, Erreichbarkeit, Zuverlässigkeit
Definition Algo mit TM
Ein Algorithmus ist nichts anderes als eine TM
Wann ist ein Problem unlösbar?
Wenn keine Sprache existiert, die entscheidbar ist und keine Funktion berechenbar ist.
-> Es existiert auch keine TM
Was besagt die Beweisform Reductio ad absurdum?
Wenn eine Annahme zu einer absurden Schlussfolgerung führt, muss die ursprüngliche Annahme falsche sein
Was besagt das Halteproblem?
Es ist ein Programm gegeben und der Eingang bestimmt, ob das Programm anhalten wird oder endlos laufen wird.
Ist es möglich ein Programm zu entwickeln, welches das feststellen kann, ob das Programm in einer Endlosschleife läuft?
Nicht möglich Programm zu entwickeln, das für alle
möglichen Programme und Eingänge überprüfen kann, ob das Programm in einer Endlosschleife endet
Welche arten von Komplexität gibt es und ws sagt sie aus?
- Zeitkomplexität
- Platzkomplexität
Maß für die Schwere des Problems
