Probleme aufeinander reduzieren [Theoretische Informatik]

27.02.2015, 21:29	baxbear	Auf diesen Beitrag antworten »
Probleme aufeinander reduzieren [Theoretische Informatik] Hi, ich versuche mich gerade in das Reduzieren von Problemen einzuarbeiten und wollte fragen wie man z.B. eine der folgenden Aufgaben löst: $\begin{eqnarray} H_1=\{u\|u \end{eqnarray}$ ist der Code einer TM und $\begin{eqnarray} M_u(u) \end{eqnarray}$ stoppt $\begin{eqnarray} \} \end{eqnarray}$ zeigen Sie, dass folgende Sprachen nicht entscheidbar sind, in dem Sie sie auf $\begin{eqnarray} H_1 \end{eqnarray}$ reduzieren: $\begin{eqnarray} L_1=\{v\|v \end{eqnarray}$ ist der Code einer TM und $\begin{eqnarray} M_v(010) \end{eqnarray}$ stoppt $\begin{eqnarray} \} \end{eqnarray}$ zu zeigen: $\begin{eqnarray} H_1\leq_m L_1 \end{eqnarray}$ Ich gebe erstmal nur die erste Aufgabe an, da ich vielleicht die anderen lösen kann wenn ich hier verstehe wie man vorgeht. Andernfalls, erweitere ich den Thread vielleicht noch um weitere Aufgaben. Danke im Voraus für die Hilfe. MfG baxbear

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »