%ss19 Blatt 4 freiburglehre/ss19/rekursionstheorie
\documentclass[a4paper, 11pt]{article}
\parindent=0pt
\usepackage[hmargin=2cm,tmargin=2cm, bmargin=3cm]{geometry}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{latexsym, amsthm, mathrsfs}

\usepackage{amsmath,amssymb}
\usepackage[ngerman]{babel}
\usepackage[all]{xy}
\renewcommand{\mathcal}{\mathscr}
\newcommand{\nc}{\newcommand}
\nc{\N}{\mathbb N}
\newcommand{\equals}{\dot{=}}

%Godel Number command
\newbox\gnBoxA
\newdimen\gnCornerHgt
\setbox\gnBoxA=\hbox{$\ulcorner$}
\global\gnCornerHgt=\ht\gnBoxA
\newdimen\gnArgHgt
\def\Godelnum #1{%
\setbox\gnBoxA=\hbox{$#1$}%
\gnArgHgt=\ht\gnBoxA%
\ifnum     \gnArgHgt<\gnCornerHgt \gnArgHgt=0pt%
\else \advance \gnArgHgt by -\gnCornerHgt%
\fi \raise\gnArgHgt\hbox{$\ulcorner$} \box\gnBoxA %
\raise\gnArgHgt\hbox{$\urcorner$}}

\newcommand{\pagehead}[1]
{
\newpage
\textbf{Abteilung f\"ur Mathematische Logik}\\
\text{Prof. Dr. Heike Mildenberger}\\
\text{\"Ubungen: Dr. Giorgio Laguzzi}

\vspace{1cm}

\Large
\centerline{\textbf{Rekursionstheorie}}
\centerline{Sommersemester 2019}
\normalsize

\centerline{#1}
\vspace{.5cm}
}


\begin{document}

%-------------------------------------Anwesenheitsaufgaben-----------------------------------------
\pagehead{Blatt 4, 27.05.2019}


\begin{enumerate} 

\item  (4 Punkte) 
\begin{enumerate}
\item Gibt es eine partielle rekursive Funktion  $\varphi$ mit folgenden Eigenschaften:
\[
(\forall e)(W_e \neq \emptyset \Rightarrow \varphi(e) \downarrow \;\land\; \varphi(e) \in W_e)?
\]
(Wir nennen $\varphi$ eine Auswahlfunktion.)
\item Gibt es sogar eine rekursive
  Auswahlfunktion?
\end{enumerate}
      
   
\item (4 Punkte)
Gibt es eine partielle rekursive Funktion $\varphi$, so dass:
\[(\forall e,i)\bigl(
W_i = W_e \neq \emptyset \Rightarrow (\varphi(e)\downarrow \;\land \; \varphi(i)\downarrow \;\land \; \varphi(e)=\varphi(i))\bigr)?
\]


\item (4 Punkte) Gibt es eine partielle rekursive Funktion $\varphi$, die keine
  totale rekursive Fortsetzung hat?



\item (4 Punkte)
  Seien $A,B$ disjunkte Mengen, so dass $\mathbb{N}\smallsetminus A, \mathbb{N}\smallsetminus B$  r.e.\ Mengen sind. Sind $A$ und $B$ rekursiv trennbar?
  D.h., gibt es rekursive Mengen $C_A$ und $C_B$, so dass
\[C_A \supseteq A \;\wedge\; C_B \supseteq B \;\wedge\; C_A \cap C_B = \emptyset?\]


\end{enumerate}



\end{document}