0 Daumen
546 Aufrufe

Ist die Sprache USEFUL auf das Rucksackproblem reduzierbar?

Mein Ansatz:

Könnte man so argumentieren?

Wenn L2 entscheidbar/rekursive aufzählbar ist ⇒ L1 ist entscheidbar/rekursiv aufzählbar?

Führt dann zum Widerspruch

Avatar von

Was bitte ist die Sprache USEFUL?

Die Sprache USEFUL ist folgendermaßen definiert

USEFUL := {(<M>q) | M ist DTM mit Zustand q und es gibt eine Eingabe w, so dass M gestartet mit w in den Zustand q gerät)

Ich habe angenommen die Sprache ist bekannt, mein Fehler.

Und wo ist L1 und L2 definiert? Ich verstehe deine Frage nicht so ganz.

Du willst wissen, ob eine DTM mit einem Zustand q bei einer bestimmten Eingabe w terminiert?

Nein, ich will wissen, ob USEFUL auf RSent reduzierbar ist.

L′ heißt reduzierbar auf L , falls es eine Funktion f:0,1∗→0,1∗ gibt mit
1.Für alle w  aus 0,1∗ gilt: w ist in L′ genau dann, wenn in f(w) in L
2.Funktion f  ist berechenbar, d.h., es gibt eine DTM Mf, die die Funktion f  berechnet.
f heißt Reduktion von L′ auf L, geschrieben L′ ≤ L.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community