\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Reduktion-Turingmaschine},
  Thematik = {Reduktion-Turingmaschine},
  Referenz = THEO.Komplexitaet.Reduktion-Turingmaschine,
  RelativerPfad = Module/70_THEO/40_Komplexitaet/Aufgabe_Reduktion-Turingmaschine.tex,
  ZitatSchluessel = theo:ab:4,
  ZitatBeschreibung = {Aufgabe 10},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Polynomialzeitreduktion},
}

\begin{description}

%%
% (a)
%%

\item Betrachten Sie das folgende Entscheidungsproblem:
\index{Polynomialzeitreduktion}
\footcite[Aufgabe 10]{theo:ab:4}

Eingabe: eine geeignete codierte Turingmaschine M
Ausgabe: entscheiden, ob die Turingmaschine M auf jedes Eingabewort nach
höchstens 42 Schritten hält.
Ist dieses Problem entscheidbar? Beweisen Sie Ihre Antwort.

\begin{bAntwort}
M sei TM. M liest in jedem Schritt höchstens ein Zeichen der Eingabe.
⇒Eingabe hat höchstens 42 Zeichen.
⇒Menge der zu entscheidenden Wörter ist endlich.
⇒Wir können alle Wörter der Sprache aufzählen und damit das Problem lösen.
\end{bAntwort}

%%
% (b)
%%

\item Beweisen Sie mit Hilfe eines Reduktionsbeweises, dass das folgende
Problem nicht entscheidbar ist:

Eingabe: zwei (geeignetes codierte) Turingmaschinen M 1 und M 2 sowie ein Ein-
gabewort ω
Ausgabe: entscheiden, ob M 1 auf Eingabewort ω hält und M 2 auf ω nicht hält.

\begin{bAntwort}
Das beschriebene Problem sei H N .
Die TM M N , die zu H N gehört, sei wie folgt definiert:
• Wir wählen eine zu ω passende TM M 0 aus dem Halteproblem H 0 aus, so dass
M = (ω) hält.
• Wir definieren eine TM M ⊥ , die zu keiner Eingabe hält.
Dann ist für M N M 0 (w)\#M ⊥ (w) eine Möglichkeit für das Problem H N . Da aber H 0 nicht
entscheidbar, so ist auch H N nicht entscheidbar.
\end{bAntwort}

\end{description}
\end{document}