%blatt13
\documentclass[A4,11pt]{article}

\usepackage{lmodern}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{multicol}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\pagestyle{empty}

\usepackage{fancyhdr}

\pagestyle{fancy}
\fancyhf{}
\theoremstyle{definition}
\newtheorem{ubung}{Aufgabe}
\newtheorem{uebung}{Aufgabe}

\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\fA}{\mathfrak{A}}
\newcommand{\fB}{\mathfrak{B}}
\newcommand{\fN}{\mathfrak{N}}
\newcommand{\lra}{\leftrightarrow}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\such}{\; : \;}



\begin{document}

\lhead{Logik f\"ur Studierende der Informatik\\
WS 2022/23
}

\rhead{Dozentin: Prof. Dr. Heike Mildenberger\\\
Assistent: M.Sc. Christian Br\"auninger}


$\,$\\
\\
\\
\cfoot{Abgabe per Ilias bis Mittwoch 1.2.2023, 10 Uhr.}



\begin{center}
 \textbf{BLATT 13}\\
 (25.1.2023)
\end{center}

Alle Punkte auf diesem Blatt z\"ahlen als Bonuspunkte.

\begin{ubung}[4 Punkte]~\\
Es sei $M=(Q,\Sigma, \Gamma,\delta, q_0,q_{ak},q_{ab})$ die Turingmaschine gegeben durch:
\begin{itemize}
\item
\( Q = \{ q_0, q_1, q_{ak}, q_{ab} \} \), in der Reihenfolge $q_0$, $q_1$, $q_2$, $q_3$ wie in der Menge aufgelistet, 
\item
\( \Sigma = \{ 1 \} \),
\item
\( \Gamma = \{ b,1 \} \), in der Reihenfolge $x_0$, $x_1$,
\item
\( \delta(q_0,1) = ( q_1, 1, R) \),  \quad
\( \delta(q_0,b) = ( q_{ak}, b, R) \),\quad
\( \delta(q_1,1) = ( q_0, 1, R) \), \; \( \delta(q_1,b) = ( q_{ab}, b, L) \). Die Zeilen der Tafel sind in dieser Reihenfolge gedacht.
\end{itemize}
Bestimmen Sie eine/die G\"odelnummer $\#(M)$ von $M$. 
\end{ubung}

\begin{ubung}[4 Punkte]~\\
Eine Abbildung $f:\bN^k\to \bN$ hei{\ss}t (analog zu Definition 2.14) \emph{berechenbar}, wenn es eine Turingmaschine gibt, die aus dem Input $(n_0,n_1,\dots,n_{k-1})$ den Output $f(n_0,\dots,n_{k-1})$ liefert.~\\
Es sei $f:\bN^k\to \bN$ solch eine berechenbare Abbildung. Ist dann auch der Graph
$$\Gamma_f = \{(n_0,n_1,\dots,n_k)\such f(n_0,\dots,n_{k-1})=n_k\}\subseteq \bN^{k+1}$$
von $f$ berechenbar? Das hei\ss t, jetzt ist zu entscheiden, ob der Graph die Akzeptierungsmenge einer auf jede Eingabe 
nach endlicher Zeit stoppenden Turingmaschine ist. Gibt es umgekehrt eine nicht berechenbare Abbildung von $\bN^k$ nach $\bN$, deren Graph berechenbar ist?
\end{ubung}

\begin{ubung}[4 Punkte]~\\
Wir betrachten die Definition der G\"odelnummern von Zeichenfolgen f\"ur eine beliebige h\"ochstens abz\"ahlbare Zeichenmenge $\tau$ am Anfang von Kapitel 6.3. Insbesondere betrachten wir die beiden Abbildungen $\ulcorner \cdot \urcorner: \cL(\tau)^\ast \to \bN$ und $\la \la \cdot\ra\ra: \bN^{<\infty} \to \bN$, wobei $\bN^{<\infty}$ die Menge der endlichen Tupel von nat\"urlichen Zahlen ist, also
$$\bN^{<\infty}=\{(n_0,\dots,n_k) \such k\in \bN \text{ und } n_0,\dots,n_k \in \bN\}$$
\begin{itemize}
\item[a)] Ist die Funktion $\la \la \cdot\ra\ra: \bN^{<\infty} \to \bN$ injektiv?
\item[b)] Ist die Funktion $\la \la \cdot\ra\ra: \bN^{<\infty} \to \bN$ surjektiv?
\item[c)] Ist $\ulcorner \cdot \urcorner: \cL(\tau)^\ast \to \bN$ injektiv? H\"angt die Antwort darauf von $\tau$ ab?
\item[d)] Ist $\ulcorner \cdot \urcorner: \cL(\tau)^\ast \to \bN$ surjektiv? H\"angt die Antwort darauf von $\tau$ ab?
\end{itemize}
\end{ubung}


\begin{ubung}[4 Punkte]~\\
Ist das diagonale Halteproblem
$$DH=\{(\#(M),\#(M))\in \Sigma_U^\ast \such M \text{ ist eine TM und } M \text{ akzeptiert } \#(M)\}.$$
entscheidbar?
\end{ubung}

\end{document}