\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {TURING-berechenbar},
  Thematik = {TURING-berechenbar},
  Referenz = THEO.Berechenbarkeit.TURING-berechenbar,
  RelativerPfad = Module/70_THEO/20_Berechenbarkeit/Aufgabe_TURING-berechenbar.tex,
  ZitatSchluessel = theo:ab:4,
  ZitatBeschreibung = {Aufgabe 3},
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {TURING-berechenbar},
}

TURING-berechenbar\index{TURING-berechenbar}
\footcite[Aufgabe 3]{theo:ab:4}

% Ist die Funktion
% 1, falls w∈L(n,1)
% f : N × Σ * → {0, 1} mit f (n, w) = { 0, falls w ∈L(n,1)
% /
% mit folgendem Sinn:
% Angesetzt auf das Wort 1 n \#w (mit n ∈ N, w ∈ Σ * und Trennzeichen \#) hält T nach
% ”
% endlicher Zeit in einer Konfiguration an, in der f (n, w) als Ergebnis auf dem Arbeitsfeld
% steht. ,
% ”
% turing-berechenbar?
\begin{bAntwort}
Ja, denn folgende TM führt die Berechnung aus. T liest eine links vom
Trennzeichen stehende 1, ersetzt sie durch eine Null und fährt im
Zustand Z 1 so lange nach rechts bis eine 0 erscheint. Diese wird
gelöscht und dann im Zustand Z 2 nach links gewandert, um die dort am
Anfang der Einserkette stehende 0 zu löschen. Nach Abarbeiten der n
Einsen dürfte dann rechts des Trennzeichens nur noch eine 1 stehen. Dies
wird nun mit Hilfe der restlichen Zustände überprüft. Steht nun noch
eine 1 auf dem Band (also rechts daneben \#), so macht T einen Schritt
nach links und bleibt unter der 1 stehen. Findet T noch eine NUll, so
bleibt sie bei dieser stehen.\footcite[Seite 44, Aufgabe 8]{kiesmueller}
\bFussnoteUrl{https://flaci.com/Aputs940c}
\end{bAntwort}
\end{document}
