Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 15 von 42 Treffern Seiten (3): [1] 2 3 nächste »
Autor Beitrag
Thema: Selbsthalteproblem
donvito

Antworten: 3
Hits: 4.736
17.03.2008 19:30 Forum: Theoretische Informatik


Hmm, ich würde sagen HALTETEST(M') hält, ist aber bissel verzwickt, da sich das ganze ja quais endlos selbst aufruft.
Thema: Selbsthalteproblem
donvito

Antworten: 3
Hits: 4.736
Selbsthalteproblem 17.03.2008 18:12 Forum: Theoretische Informatik


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
donvito

Antworten: 11
Hits: 7.534
15.03.2008 12:43 Forum: Theoretische Informatik


Ja stimmt wohl, mir fehlte da nur irgendwie die Bedingung was passiert wenn w nicht in L ist. großes Grinsen

Also man bräuchte im schlimmsten Fall natürlich n Zeichen.

Jetzt habe ich es verstanden Tanzen

Hoffentlich kommt das dran großes Grinsen
Thema: Kolmogorov-Komplexität
donvito

Antworten: 11
Hits: 7.534
15.03.2008 11:43 Forum: Theoretische Informatik


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
donvito

Antworten: 11
Hits: 7.534
14.03.2008 20:32 Forum: Theoretische Informatik


Aber die Bitlänge weiß ich doch nicht... Kapier das nicht so recht...
Thema: Kolmogorov-Komplexität
donvito

Antworten: 11
Hits: 7.534
14.03.2008 18:44 Forum: Theoretische Informatik


unär ist der Gegensatz zu BINÄR, Bi = zwei (O, 1) und uno = 1 (0 oder 1) Augenzwinkern

Was ist |P(n)|? Die Anzahl der Zeilen des Programms, oder was?
Thema: Kolmogorov-Komplexität
donvito

Antworten: 11
Hits: 7.534
14.03.2008 18:15 Forum: Theoretische Informatik


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
donvito

Antworten: 11
Hits: 7.534
Kolmogorov-Komplexität 14.03.2008 15:50 Forum: Theoretische Informatik


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
donvito

Antworten: 1
Hits: 3.553
Abgeschlossenheit rekursiv aufzählbarer Sprachen 09.03.2008 16:16 Forum: Theoretische Informatik


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
donvito

Antworten: 6
Hits: 5.789
24.02.2008 22:47 Forum: Theoretische Informatik


Ups! Da werde ich wohl nicht mehr ganz bei der Sache gewesen sein! smile
Thema: DFA in NFA umwandeln
donvito

Antworten: 6
Hits: 5.789
24.02.2008 21:36 Forum: Theoretische Informatik


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
donvito

Antworten: 6
Hits: 5.789
24.02.2008 14:44 Forum: Theoretische Informatik


und welche Übergänge hat der DFA von z0 und z1?
Thema: DFA in NFA umwandeln
donvito

Antworten: 6
Hits: 5.789
DFA in NFA umwandeln 24.02.2008 13:09 Forum: Theoretische Informatik


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
donvito

Antworten: 2
Hits: 3.934
03.02.2008 23:49 Forum: Informatik in der Schule


Wenn es piept stimmt etwas nicht. Entweder hast du den RAM beschädigt beim Ausbauen oder du hast ihn irgendwie schief eingesetzt.
Thema: Word
donvito

Antworten: 4
Hits: 4.722
03.02.2008 23:42 Forum: Praktische Informatik


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 »