Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Wäre die Diagonalsprache auch ein korrektes Beispiel für die Antwort im b Teil der Aufgabe?

+1 Punkt
26 Aufrufe
Hallo zusammen,

die Sprache L NA ist also ein Bsp für die Komplexitätsklasse P ohne L0: Wäre die Diagonalsprache auch ein korrektes Beispiel für die Antwort im b Teil der Aufgabe? ( Ihre Wörter können ja ebenso von keiner Touringmaschine erkannt werden)

Vielen Dank im Voraus
Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

Hallo,

bitte verwechseln Sie die Komplexitätsklasse \( P\) nicht mit der Menge aller Sprachen \( p(E^\star)\)! Letzteres ist im klassischen Sinn keine Komplexitätsklasse, bzw. ist diese Bezeichnung nicht besonders sinnvoll, da darin alle Sprachen bzw. Probleme enthalten sind, unabhängig von Komplexität oder Berechenbarkeit. Wenn Ihnen solche Unterschiede nicht klar sind, sollten Sie sich das dringend nochmal anschauen!

Die Antwort auf Ihre Frage ist aber ja, denn \( L_{NA} \) ist die Diagonalsprache :-)

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...