| Zeige Beiträge 1 bis 15 von 42 Treffern |
Seiten (3): [1] 2 3 nächste » |
 Thema: Selbsthalteproblem |
|
|
Hmm, ich würde sagen HALTETEST(M') hält, ist aber bissel verzwickt, da sich das ganze ja quais endlos selbst aufruft.
|
|
| Thema: Selbsthalteproblem |
|
|
Wie löse ich diese Aufgabe:
Zeigen Sie, dass die Sprache
HALT_Selbst = {<M> | DTM M hält auf Eingabe <M>}
nicht entscheidbar ist?
Ich habe versucht so zu argumentieren:
^Das "normale" Halteproblem ist wie folge definiert: {<M, w> |M ist eine TM und hält auf Eingabe w}. Dieses ist laut Vorlesung nicht entscheidbar. Angenommen, es gibt eine TM, die HALT entscheidet. Dann entscheidet diese TM auch HALT_Selbst, denn letzlich ist die Codierung einer Maschine nichts anderes als ein x-beliebiges Wort, da die TM nicht erkennen kann, ob es sich um ihre eigene Codierung handelt.
Da jedoch das Halteproblem nicht entscheidbar ist, ist auch das Selbsthalteproblem nicht entscheidbar.
Was kann man hier noch verbessern? Stimmt das so überhaupt?
|
|
| Thema: Kolmogorov-Komplexität |
|
|
Ja stimmt wohl, mir fehlte da nur irgendwie die Bedingung was passiert wenn w nicht in L ist. 
Also man bräuchte im schlimmsten Fall natürlich n Zeichen.
Jetzt habe ich es verstanden 
Hoffentlich kommt das dran
|
|
| Thema: Kolmogorov-Komplexität |
|
|
Dein Algo hat aber einen Fehler bzw. du hast was falsch verstanden. Es müssen NICHT alle Teilfolgen von 1* enthalten sein. Es kann zum Beispiel sein, dass 1, 111, 11111, ... enthalten sind, 11 und 1111 aber nicht. Es ist eben eine Teilmenge von 1*
Dein Algorithmus würde dann einfach aufhören zu zählen
So müsste es klappen:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
|
P(n):
count = 0;
i = -1;
while (count < n) { i = i+1;
if (M(1^i) == true) count = count+1;
else do_nothing();
}
Output(1^i); |
|
Die Konstante c enthält also offenbar alles außer der Schleife. Setze ich einen höheren Wert für n ein, so läuft die Schleife entsprechend länger. Die Länge ihrer Beschreibung dürfte sich dadurch aber nur minimal ändern. Es ändert sich ja nur der "Grenzwert" bis zu dem count zählt.
|
|
| Thema: Kolmogorov-Komplexität |
|
|
unär ist der Gegensatz zu BINÄR, Bi = zwei (O, 1) und uno = 1 (0 oder 1) 
Was ist |P(n)|? Die Anzahl der Zeilen des Programms, oder was?
|
|
| Thema: Kolmogorov-Komplexität |
|
|
Ja, das bezieht sich darauf, dass nur die 1 enthalten ist. Es werden Wörter unterschiedlicher Länge aus 1ern gebildet:
11, 111, 11111, ...
|
|
| Thema: Kolmogorov-Komplexität |
|
|
Mal wieder ne Frage:
Wie zeige ich, dass die KK des n-ten Elements einer rekursiven unären Mange A Teilmenge von 1* beschrieben wird durch
K(x_n) < n + c
Dürfte eigentlich nicht schwer sein, aber mir fehlt da die Übung.
Die Elemente sind der Größe nach sortiert, also z.B. 11, 1111, 11111, usw.
Die KK ist je gegeben durch die Länge des Kürzesten Programms, dass diese Zeichenkette erzeugt. Nur: Ich weiß ja garnicht wieviele 1er im n-ten Element stehen.
|
|
| Thema: Abgeschlossenheit rekursiv aufzählbarer Sprachen |
|
|
Da bei uns sehr klausurwahrscheinlich, frage ich hier mal nach:
über welchen Operationen sind rekursiv aufzählbare Sprachen abgeschlossen?
Schnitt
Man kann eine TM C aus den TMs A und B konstruieren (A akzeptiert Sprache A, B Sprache B). C funktioniert wie folgt:Auf Eingabe w wird zuerst A aufgerufen, dann B. Wenn beide akzeptieren, akzeptiert auch C. Ansonsten lehnt C ab.
Komplement
Hier kann man nur sagen weder noch. Das Komplement kann sowohl rekursi sein als auch rekursiv-ko-aufzählbar (=nicht rekursiv aufzählbar).
Wie schaut das bei den Operationen Stern und Kontakenation aus? Laut Buch sind sie abgeschlossen, nur, wie beweise ich das richtig?
|
|
| Thema: DFA in NFA umwandeln |
|
|
Also, wenn iich hier folgenden NFA habe
Q = {1, 2, 3}
q_0 = [1}
F= {3} und
Delta = (1, a) = 2
(2, b) = 3
(2, a) = 3
Wie sieht das dann also DFA aus?
Q' = Potenzmenge von Q, also insgesamt 7 Zustände
F' = alle Zustände, die einen akzeptierten "enthalten", q_0' = q_0
Und wie mache ich jetzt die Übergänge?
|
|
| Thema: DFA in NFA umwandeln |
|
|
Wie wandle ich einen NFA in einen DFA um? Erstmal ohne Epsilon-Übergänge.
Zustände sind die Potenzmenge, das ist klar. Startzustand bleibt gleich und auch die akzeptierten Zustände sind klar. Nur: Wie bekomme ich die Übergänge?
|
|
| Thema: dual channel linear mode |
|
|
Wenn es piept stimmt etwas nicht. Entweder hast du den RAM beschädigt beim Ausbauen oder du hast ihn irgendwie schief eingesetzt.
|
|
| Thema: Word |
|
|
80 MB? ieviele 1000 Seiten sind das denn? Du solltest mal die Bilder komprimieren(Rechtsklick aufs Bild)! Dann kriegst du selbst Dokumente mit vielen Bildern auf ein paar MB.
Das mit der vollen Festplatte kann ich mir so einfach nicht erklären. Möglicherweise hast du nur eine Partition erstellt und diese ist voll. Auf der HD befindet sich dann noch ungenutzter Speicher. Ich halte es auch nicht ür so gut eine 300 GB Festplatte in einen älteren Rechner einzubauen. Das könnte u.U. die beschriebenen Proleme geben
Wa kommt denn für eine Meldung? Oder öffnet Word einfach nicht?
|
|
|
| Zeige Beiträge 1 bis 15 von 42 Treffern |
Seiten (3): [1] 2 3 nächste » |
|
|
