TheoLog (Subject) / Berechenbarkeit (Lesson)

This lesson was created by Sogn.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Wie zeigt man ob ein Problem berechenbar oder nicht berechenbar ist? Berechenbar Gebe einen Algorithmus an, der das Problem löst Nicht-berechenbar Festlegen einer Definition, was nun berechenbar ist, zB. durch Berechnungsmodelle Wird ein Problem von keinem BM erkannt, so ist es nicht berechenbar
• Nenne die Berechnungsmodelle! μ-rekursive Funktionen WHILE-Programme GOTO-Programme Turing Maschinen
• Was besagt die Churche These? Die (intuitiv) berechenbaren Funktionen sind genau die mit Turingmaschinen (und damit mit GOTO-, WHILE-, Pascal-Programmen, URMs,...) berechenbaren Funktionen
• Wann ist eine Turingmaschine nicht deterministisch? Wenn es für eine Eingabe mehrere Möglichkeiten gibt Beispiel: (q0,a,b1,t1,q1),(q0,a,b2,t2,q2)
• Wann ist eine Sprache turing akzeptierbar bzw. turing berechenbar? Eine Sprache ist turing akzeptierbar, wenn es eine NTM gibt, welche die Sprache erkennt. Gibt es ebenfalls eine DTM , dann ist die Sprache turing berechenbar.
• Sind k-Band TM und TM gleichmächtig? Ja, jede Sprache, welche von einer k-Band TM erkannt wird, wird auch von einer ein Band TM erkannt
• Gibt es zu jeder NTM eine DTM? Ja
• Unterschied zwischen partiellen und totalen Funktionen? partiell Nicht jedes x hat ein y -> Nicht jede Funktion hat für alle x eine Lösung aus y (Bsp. 1/x) total Jedes x hat ein y -> Jede Funktion hat eine Lösung für alle x aus y
• Wann ist eine Relation rekursiv bzw. entscheidbar? Falls ihre charakteristische Funktion berechenbar ist
• Sei R eine Relation. Wann ist R entscheidbar? Was sagt die Entscheidbarkeit dieser über andere Eigenschaften aus? R ist genau dann entscheidbar, wenn R und /R partiell entscheidbar sind. Ist R entscheidbar so ist sie auch partiell entscheidbar. Genau dann wenn R partiell entscheidbar ist, ist R auch rekrusiv aufzählbar.
• Advertisement
• Was bedeutet es , wenn eine Funktion partiell entscheidbar ist? Es gibt einen Algorithmus der bei der Eingabe von x eine positive Entscheidung über Berechenbarkeit treffen kann, ansonsten aber keine. In unserem Fall bedeutet dies es gibt eine TM die x erkennt, fall x Element der Relation ist, aber ansonsten einfach in eine Endlosschleife übergeht.
• Wie lauten die Grundfunktionen der primitiv rekursiven Funktionen? Nachfolgerfunktion Projektion Nullfunktion
• Um welche Art Funktionen handelt es sich bei primitiv rekursiven Funktionen? Um totale Funktionen. Die Klasse der primitiv rekursiven Funktion besteht aus allen Funktionen, welche sich aus den Grundfunktionen mithilfe von Komposition und primitiver Rekursion bilden lassen.
• Worin unterscheiden sich LOOP und WHILE Programme? LOOP Programme terminieren immer und können nur Programme mit feststehendem Schleifendurchlauf berechnen.
• Sind LOOP Programme und WHILE Programme gleichmächtig? Nein, aber LOOP Programme und primitiv Rekursive Funktionen sind gleichmächtig und somit sind alle Loop-berechenbaren Funktionen auch rekursiv und umgekehrt. Gegenbeispiel wäre die Ackermannfunktion.
• Gibt es totale berechenbare Funktionen, welche nicht LOOP berechenbar sind? Ja, Ackermann Funktion ist total aber kann nicht von LOOP oder primitiv rekursiv berechnet werden.
• Wie erweitert man die primitiv Rekursiven Funktionen, um alle Funktionen berechnen zu können? Man führt unbeschränkte Minimalisierung ein.
• Lässt sich jedes LOOP in ein WHILE Programm umwandeln? Ja, durch y = x + 0; und WHILE y =! 0 DO [P] y = y - 1 END
• Welche Berechnungsmodelle enthalten die turing-berechenbaren Funktionen? Nach der These von Church Turingmaschinen, WHILE Programme und u-rekursive Funktionen.
• Was ist UNIV? Ist UNIV entscheidbar? UNIV= {code(A)w ∈ Σ∗| A ist DTM über Σ,die w akzeptiert} Nein, aber partiell entscheidbar.
• Welche drei Grundprobleme sind unentscheidbar? Wortproblem für DTM Gehört ein Wort w in die Sprache? wäre es entscheidbar, wäre auch UNIV entscheidbar, ist es aber nicht Halteproblem für DTM Hält die DTM A mit dem Wort w als Eingabe iwann an? Wäre das Halteproblem entscheidbar, so auch das Wortproblem (Reduktion) Leerheitsproblem für DTM ist L = Ø ? Wäre das Leerheitsproblem entscheidbar, so auch das Halteproblem Äquivalenzproblem für DTM Sind zwei Sprachen äquivalent? Wäre das Äquivalenzproblem entscheidbar, so auch das Leerheitsproblem, da man L(A) = L(B), wobei B = LEER
• Welche Eigenschaften besitzt L0? L0 ist nicht unter Komplement abgeschlossen
• Was besagt der Satz von RICE? Sei E eine nicht-triviale, semantische  Eigenschaft einer Deterministischen Turingmaschine. Dann ist das Problem, ob DTM diese Eigenschaft besitzt , unerfüllbar. nicht trivial: Ist DTM eine DTM? semantisch: Die Bedingung hängt nur von der Sprache, nicht von der Turingmaschine ab
• Beispiele für syntaktische und semantische Probleme von DTMs (RICE)? syntaktisch (nicht funktional) TM hält nach n Schritten an TM schreibt kein a auf das Band semantisch (funktional) L(M) = Ø W ist regulär Alles mit "M berechnet"
• Was ist das Ziel von Reduktion? Ein bereits bekannt unentscheidbares Problem auf ein neues Problem zu reduzieren, welche mindestens genauso schwer wie das bekannte Problem ist. Denn dann lässt sich folgern, dass dieses auch nicht lösbar sein kann.
• Was ist das PKP? Wofür dient es? Das Postsche Korrespondez Problem ist ein unentscheidbares Problem. Eine Instanz besteht aus einer Folge von Wortpaaren. Ziel ist es die Instanzen so übereinander zu reihen, dass es passt. Mit seiner Hilfe kann das Beweisen von Unentscheidbarkeit von Prädikatenlogik oder auch kontextfreien Grammatiken ermöglich werden.
• Welche Entscheidbarkeitsprobleme gelten für Sprachen? L1 ist in Bezug auf das Leerheitsproblem und das Äquivalenzproblem unentscheidbar. L2 ist in Bezug auf das Äquivalenzproblem unentscheidbar. Es ist nicht entscheidbar , ob die Schnittmenge zweier kontextfreier Grammatiken leer ist. All diese lassen sich mithilfe des PKP beweisen.
• Sind alle Relationen entscheidbar? Nein, Beispiel UNIV.
• Sind alle partiellen Funktionen berechenbar? Nein
• Welche Sprachen befinden sich in L0? Alle partiell entscheidbaren, bzw. turing-akzeptierbaren Sprachen.

back  |  next 1 / 1