\section{Intuitiver Berechenbarkeitsbegriff und Church'sche These}
\inhalta{1-7}
\begin{frame}
\only<article>{

 Aus ``Automaten und Formale Sprachen'' ist die Chomsky-Hierarchie der formalen Sprachen bekannt. 
 Dabei wurde angemerkt, dass es zu kontextfreien Grammatiken Fragestellungen gibt, 
 die nicht entscheidbar sind. Um eine derartige negative Aussage zu begründen, 
 muss man zuerst einmal einen präzisen Begriff der \emph{Entscheidbarkeit} haben. 
 Es ist eines der  Ziele dieser Veranstaltung, nachzuweisen, dass es in der Tat einen  
 präzise definierten Begriff der Entscheidbarkeit  für Mengen von natürlichen Zahlen(vektoren) 
 oder für Mengen von Wörtern gibt. Ebenso gibt es einen präzise definierten 
 Begriff der Berechenbarkeit für Funktionen auf natürlichen Zahlen oder auf endlichen Wörtern. 
 Wir werden zuerst auf verschiedene Weise Berechenbarkeit für Funktionen definieren und zeigen, 
 dass ganz verschiedene Ansätze alle zu dem gleichen Begriff führen.
  Anschlie"send werden wir den Entscheidbarkeitsbegriff für Mengen auf den 
  Berechenbarkeitsbegriff für Funktionen zurückführen. 

 Zuerst wollen wir diskutieren, welche Funktionen denn als berechenbar bezeichnet werden sollten. 
 Wir verwenden dabei zunächst eine vereinfachte Sichtweise: der Zeitverbrauch und der 
 Speicherplatzverbrauch interessieren uns jetzt (noch) nicht. Wir wollen nur sehen, ob eine Funktion 
 im Prinzip berechnet werden kann, wenn man annimmt, dass  für die Rechnung hinreichend 
 viel Zeit und Speicherplatz zur Verfügung stehen.

\begin{definition}[Intuitiver Berechenbarkeitsbegriff] 
%  Eine möglicherweise partielle Funktion $f: \nz^k\Partial \nz$
%  hei"st berechenbar, wenn es einen Algorithmus, z.B. ein \texttt{JAVA}-Programm, gibt, 
%  der bei der Eingabe $(n_1,..., n_k)$ entweder nach endlich vielen Schritten
%  $ f(n_1,...,n_k)$ als Ausgabe berechnet und dann anhält 
%  (dann ist $f$ bei der Eingabe $(n_1,..., n_k)$ definiert) oder nie anhält. 
%  Stoppt der Algorithmus bei einer Eingabe  $(n_1,..., n_k$) nicht, so ist $f$
% auf dieser Eingabe nicht definiert.

Die von einem Algorithmus $A$ (z.B. einem \texttt{JAVA}-Programm) berechnete 
Funktion $f_A: \nz^k\Partial \nz$ ist definiert wie folgt:
\[f_A(n_1,..., n_k)=\left\{
%\begin{tabular}{lp[.6\linewidth]}
\begin{tabular}{ll}
$n$,& falls $A$ bei Eingabe von $(n_1,..., n_k)$ das Resultat $n$ \\
& berechnet und dann anhält,\\
undefiniert,& falls $A$ bei Eingabe von $(n_1,..., n_k)$ endlos rechnet. 
\end{tabular}
\right.\]

Eine Funktion $f$ heißt berechenbar, wenn es einen Algorithmus $A$ gibt, der sie berechnet (also $f=f_A$).
Insbesondere hält $A$ damit genau dann bei der Eingabe $(n_1,..., n_k)$ an, wenn
$f(n_1,..., n_k)$ definiert ist.
\end{definition}
}%article
\only<presentation>{
\begin{definition}[Intuitiver Berechenbarkeitsbegriff] 
\begin{itemize}\item 
Die von einem Algorithmus $A$ (z.B. einem \texttt{JAVA}-Programm) berechnete 
Funktion $f_A: \nz^k\Partial \nz$ ist definiert wie folgt:\pause
\[f_A(n_1,..., n_k)=\left\{\pause
%\begin{tabular}{lp[.6\linewidth]}
\begin{tabular}{ll}
$n$,& falls $A$ bei Eingabe von 
\\& $(n_1,..., n_k)$ das Resultat $n$ \\
& berechnet und dann anhält,\\[1ex]
undefiniert,& falls $A$ bei Eingabe von 
\\&$(n_1,..., n_k)$ endlos rechnet. 
\end{tabular}
\right.\]
\pause
\item Eine Funktion $f$ heißt berechenbar, wenn es einen Algorithmus $A$ gibt, der sie berechnet (also $f=f_A$).
\pause
\item
Insbesondere hält $A$ damit genau dann bei der Eingabe $(n_1,..., n_k)$ an, wenn
$f(n_1,..., n_k)$ definiert ist.
\end{itemize}
\end{definition}
}%presentation
\end{frame}

\begin{frame}[fragile]
\begin{example}\label{Berechenbarkeitsbeispiele}
 Berechnung der Summe zweier natürlicher Zahlen $m $ und $n$ \pause\\
als Funktion
 $f:\nz^2\rightarrow\nz$ mit $f(m,n)=n+m$:\pause
{\scriptsize \begin{lstlisting}[escapechar=§]
import java.util.Vector;
import java.math.BigInteger;

public class Addition {
  public static void main( String args[] ){

    BigInteger m = new BigInteger( args[0] );
    BigInteger n = new BigInteger( args[1] );

    while ( n.compareTo(BigInteger.ZERO) > 0 ) {
      n = n.subtract( BigInteger.ONE );
      m = m.add( BigInteger.ONE );
    }
    System.out.println( m.toString() );
  }
}
\end{lstlisting}}
\end{example}
\end{frame}


\begin{frame}[fragile]
\begin{example}
Berechnung einer partiellen Funktion
 $f:\nz\Partial\nz$ durch folgenden Algorithmus: \pause
{\scriptsize \begin{lstlisting}[escapechar=§]
import java.math.BigInteger;

public class Forever {
  public static void main( String args[] ) {
    BigInteger n = BigInteger.ONE;
    while ( n.compareTo(BigInteger.ZERO) > 0 ) {
      n = n.add(BigInteger.ONE);
    }
  }
}
\end{lstlisting}}

\only<article>{ Da die obige Schleife nicht abbricht, 
 berechnet der Algorithmus die partielle Funktion $f$ von  $\nz$
nach $\nz$, die nirgends definiert ist. }
\only<presentation>{ \pause Abbruchbedingung niemals erfüllt! \pause\\
$\Rightarrow$ 
Algorithmus berechnet partielle Funktion $f$ von  $\nz$
nach $\nz$,  \pause\\ die nirgends definiert ist. }
\end{example}
\end{frame}


\begin{frame}
\begin{example}\label{pi}
Berechnung einer totalen Funktion
 $f:\nz\rightarrow\nz$ mit \begin{itemize}
\item $f(n) = 1$, \pause falls die Dezimaldarstellung von $n$
 ein Anfangsabschnitt der Dezimalbruchentwicklung von $\pi=3,1415...$ ist, \pause
\item $f(n)=0$ sonst. 
\end{itemize}

\only<article>{  Die Dezimalbruchentwicklung von $\pi$ kann man mit beliebiger 
Genauigkeit berechnen: $$\pi=4\cdot\lim_{t\rightarrow\infty}(1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\ldots\pm\frac{1}{2t-1})$$
 Man braucht für grö"sere Genauigkeit natürlich mehr Zeit und mehr Speicher, 
 aber darum geht es uns im Moment nicht. Für jede Zahl $n $ kann man $f(n)$ in 
 endlich vielen Schritten ausrechnen. Daher ist diese Funktion $f $ berechenbar. }
\only<presentation>{ 
 \pause z.B.:\vspace{-1ex}
\GLA 
&f(3)=1~~~\pause f(314)=1~~~\pause f(31415)=1~~~ \pause f(31416)=0&\\ 
&\pause f(3141592653589793238462643383279502884197169399)=1&\\ 
&\pause f(3141592653589793238462643383279502884197269399)=0
\GLE
\pause Dezimalbruchentwicklung von $\pi$ kann prinzipiell mit beliebiger Stellenzahl berechnet werden: \pause\\
$$\pi=4\cdot\lim_{t\rightarrow\infty}(1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\ldots\pm\frac{1}{2t-1})$$
 \pause$\Rightarrow$ 
 Für jedes $n $ kann man $f(n)$ in 
 endlich vielen Schritten ausrechnen. \pause\\
$\Rightarrow$  $f$ ist berechenbar. }
\end{example}
\end{frame}


\begin{frame}
\begin{example}
Berechnung einer totalen Funktion
 $g:\nz\rightarrow\nz$ mit \pause \begin{itemize}
\item $g(n) = 1$, falls die Dezimaldarstellung von $n$
 als Teilwort in der Dezimalbruchentwicklung von $\pi=3,1415...$ vorkommt, \pause
\item $g(n) = 0$, sonst. 
\end{itemize}

\only<article>{  Ob diese Funktion berechenbar ist oder nicht, ist nicht bekannt! 

 Dazu wei"s man heute zu wenig über die Zahl $\pi$. 
Tatsächlich gibt es Wissenschaftler, die vermuten, 
 dass jedes aus den Dezimalziffern gebildete Wort 
in der Dezimalbruchentwicklung von $\pi$ vorkommt. 
 Wenn das stimmt, dann ist $g$ die Funktion, die überall den Wert $1$ annimmt.  }
\only<presentation>{\pause Ob $g$  berechenbar ist oder nicht, ist nicht bekannt! \pause\vsp

... zu wenig über die Zahl $\pi$ bekannt...  \pause

... evtl.\ kommt jede Folge von Dezimalziffern bei  $\pi$ vor...  \pause\vsp

 Wenn ja:  $g$ ist die Funktion, die überall den Wert $1$ annimmt.
}
\end{example}
\end{frame}


\begin{frame}
\begin{example}
Berechnung einer totalen Funktion
 $h:\nz\rightarrow\nz$ mit \pause\begin{itemize}
\item $h(n) = 1$, falls die $7$ mindestens $n$
 mal hintereinander in der Dezimalbruchentwicklung von $\pi$ vorkommt,  \pause
\item $h(n)=0$, sonst. 
\end{itemize}

\only<article>{   Diese Funktion ist berechenbar: Entweder kommen beliebig lange Folgen von 
 $7$ in der Dezimalentwicklung von $\pi$ vor. Dann ist $h$
 die konstante Funktion, die überall   den Wert $1$ annimmt. 
Oder es gibt eine Zahl 
 $n_0$, so dass die $7$ zwar  $n_0$-mal in der Dezimalbruchentwicklung von $\pi$ vorkommt 
 (dann natürlich auch $n$-mal für jedes  $n\leq 0$), aber nicht $n_0+1$-mal 
 (dann natürlich auch nicht $n$-mal für jedes $n>n_0$). 
 In diesem Fall gilt $h(n) = 1$ für $n\leq n_0$, $h(n)=0$ für $n> n_0$.
 
 In jedem der Fälle gibt es einen Algorithmus zur Berechnung von $h$. 
 Allerdings wissen wir heute nicht, welches der richtige Algorithmus ist... }
\only<presentation>{\pause $h$  ist berechenbar: \pause
\begin{itemize} \item 
Falls beliebig lange Folgen von 
 $7$ bei $\pi$ vorkommen:\pause\\
 $\Rightarrow$ $h$ ist die konstante Funktion, die überall   den Wert $1$ hat.  \pause
\item Falls $7$ maximal $n_0$-fach hintereinanderbei $\pi$  vorkommt:\pause\\
$\Rightarrow$ In diesem Fall gilt $h(n) = 1$ für $n\leq n_0$, $h(n)=0$ für $n> n_0$.
\end{itemize}
\pause In jedem  Fall gibt es einen Algorithmus zur Berechnung von $h$.\pause\vsp

 Allerdings: Noch unbekannt ist, welches der richtige Algorithmus ist... 
}
\end{example}
\end{frame}


\begin{frame}
\only<article>{
Anmerkung:
 Beispiel \ref{pi} darf nicht darüber hinweg täuschen, dass die analoge Funktion 
 $f_r$ für den Anfangsabschnitt der Länge $n$ der Dezimalbruchentwicklung der reellen Zahl  $r$
 nicht für jede reelle Zahl $r $ berechenbar ist. Es gibt überabzählbar viele reelle Zahlen 
 und auch überabzählbar viele Dezimalbruchentwicklungen , aber nur abzählbar viele 
 zum Beispiel in \texttt{JAVA} formulierbare Algorithmen zur Berechnung von 
 Dezimalbruchentwicklungen. 
 Es gibt daher auch nur abzählbar viele reelle Zahlen, 
 deren Dezimalbruchentwicklungen berechnet werden können. 
 Die Dezimalbruchentwicklungen aller anderen reellen Zahlen 
(das sind immer  noch überabzählbar viele) 
 kann man nicht berechnen.
}%article
\only<presentation>{
Anmerkung: analog zu Beispiel \ref{pi} setze für $r\in\rz$ \pause
\begin{itemize}\item 
$f_r(n)=1$, falls $n$ Anfangsabschnitt der Dezimalbruchentwicklung von $r$ ist,\pause
\item  $f_r(n)=0 $, sonst.
\end{itemize}
\pause Aber: \begin{itemize}
\item Es gibt überabzählbar viele reelle Zahlen...\pause
\item Es gibt nur abzählbar viele (\texttt{JAVA}-)Algorithmen...
\end{itemize}
\pause $\Rightarrow$ Die Dezimalbruchentwicklungen fast aller Zahlen 
 kann man nicht berechnen!\pause

$f_r$ ist i.A. nicht berechenbar!
}%presentation
\end{frame}

\only<article>{\begin{frame}
In den folgenden Abschnitten werden wir Berechenbarkeit für Funktionen auf 
 natürlichen Zahlen(vektoren) bzw. auf endlichen Wörtern auf verschiedene Weise einführen, 
 nämlich über Turingmaschinen, über WHILE-Programme . 
 Wir werden sehen, dass all diese Berechenbarkeitsbegriffe äquivalent sind.

 Es gibt einen schwächeren Berechenbarkeitsbegriff, nämlich die Klasse der 
 über  LOOP-Programme berechenbaren Funktionen. Einen dazu äquivalenten Begriff 
(primitiv-rekursive Funktionen) können wir hier nur erwähnen.

Andere Ansätze wie GOTO-Programme und 
 die  $\mu$-rekursiven (partiell rekursiven) Funktionen führen zu einen Berechbarkeitsdefinition, die ebenfalls zur Turing-Berechenbarkeit äquivalent ist

 Offen ist die Frage, ob es auch eine stärkere, praktisch verwendbare Definition 
 berechenbarer Funktionen gibt. Es ist allerdings bis heute niemandem gelungen, überzeugend zu demonstrieren, dass es  Funktionen auf den natürlichen Zahlen gibt, 
die in einem intuitiven, praktisch realisierbaren Sinne `berechenbar' sind. 
  die aber trotzdem nicht bereits durch Turingmaschinen berechenbar sind.
  Dies hat zu der von den meisten Wissenschaftlern akzeptierten These geführt, 
  die Church bereits 1936 formuliert hat:

 \begin{block}{Church'sche These}
 Die durch Turingmaschinen berechenbaren Funktionen 
 (d.h. genau die durch WHILE-Programme berechenbaren Funktionen) auf natürlichen Zahlen 
 sind genau die im intuitiven Sinn berechenbaren Funktionen auf natürlichen Zahlen. 
\end{block}
\end{frame}}

\only<presentation>{\begin{frame}
Beliebte formale Definitionen von  Berechenbarkeit über \pause
\begin{itemize}
\item Turingmaschinen \pause
\item  WHILE-Programme \pause
\item Kalkül der {$\mu$-rekursiven Funktionen}\pause
\item $\lambda$-Kalkül
\end{itemize}

\pause Jedoch: \Fb{ Alle diese Berechenbarkeitsbegriffe sind äquivalent.} \pause

Zwei schwächere, äquivalente Definitionen:  \pause
\begin{itemize} 
\item LOOP-Programme \pause
\item primitiv-rekursive Funktionen
\end{itemize}

\pause
 \begin{block}{Church'sche These} \pause
 Die durch Turingmaschinen berechenbaren Funktionen \pause\\
 {\em (gleichbedeutend: WHILE-berechenbar, $\mu$-rekursiv, ...)} \pause\\
 sind genau die im intuitiven Sinn berechenbaren Funktionen auf natürlichen Zahlen. 
\end{block}
 
\end{frame}}

\only<article>{\begin{frame}
 Das hei"st, wenn von einer Funktion nachgewiesen ist, dass sie in einem der angegebenen 
 Sinne nicht berechenbar ist, dann ist die (allerdings nicht streng bewiesene) \"Uberzeugung, 
 dass die Funktion gar nicht berechenbar ist. 

 Wir werden zeigen, dass es Funktionen gibt, die nicht berechenbar sind.

 Da wir den Entscheidbarkeitsbegriff für Mengen auf diesen Berechenbarkeitsbegriff 
 begründen werden, haben wir dann auch einen präzise definierten 
Entscheidbarkeitsbegriff für Mengen. 
 Wir werden sehen, dass es Probleme gibt, die nicht entscheidbar sind; 
  zum Beispiel ist das Wortproblem nicht für jede Typ-0-Sprache entscheidbar.
\end{frame}}

\begin{frame}

Wichtige verwendete Schreibweisen\\ (i.W. aus ``Automaten und Formale Sprachen''):
\begin{itemize}
\item $\nz=\{0,1,2,3,\ldots\}$: natürliche Zahlen (inkl. $0$)
\item totale Funktion $f\colon A\to B$
\item partielle Funktion $f\colon A\Partial B$
\item Potenzmenge ${\mathcal {P}}(X):=\{U\mid U\subseteq X\}$ einer Menge $X$
\item Alphabet $\Sigma$: endliche Menge von Zeichen, z.B. $\Sigma=\{a,b\}$
\item Worte/Zeichenketten über $\Sigma$: endliche Folgen von Zeichen aus $\Sigma$ 
(vgl. Java-\texttt{String})
\item $|w|$ Länge des Wortes $w$ (vgl. Java-\texttt{length()})
\item $\#_a w$ gibt an, wie oft das Zeichen $a$ in $w$ vorkommt
\item $\Sigma^k$: Worte der Länge $k\in\nz$,
\item $\varepsilon$: leeres Wort, String mit Länge $0$
\item $\Sigma^*$: Worte beliebiger Länge, $\displaystyle\Sigma^*=\bigcup_{k\in\nz}\Sigma^k$
\end{itemize}
\end{frame}