\documentclass[twoside,12pt,fleqn]{report}
\parindent0em
\parskip1ex
\pagestyle{headings} \markboth{chapter}{section} \addtolength{\skip\footins}{4mm}
\renewcommand{\footnoterule}{\rule{200pt}{0.5pt}\vspace{3mm}}

%fleqn, damit abgestzte formeln nicht zentriert werden
\usepackage{latexsym}
%\usepackage{ngerman}
\usepackage{a4}
\usepackage{amsmath,amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage[ansinew]{inputenc} % für Windows
% damit kann man ä,ö,ü,ß direkt in den Text schreiben

\usepackage[dvips]{graphicx}    % Grafiken einbinden
%\usepackage{graphics}
\usepackage{epsfig}             % Grafiken einbinden
\usepackage[german]{babel}

%\usepackage{changebar}
%
%\usepackage[cp850]{inputenc}
%\usepackage{latexsym}

%---------------Umgebungen--------------------------------------------------------------------

\newtheorem{definition}{Definition}[chapter]
\newtheorem{satz}{Satz}[chapter]
\newtheorem{fsatz}{Versuch eines Satzes}[chapter]
\newtheorem{hilfssatz}{Hilfssatz}[chapter]
\newtheorem{bemerkung}{Bemerkung}[chapter]
\newenvironment{beweis} {\noindent  {\bf Beweis:} }

%-----------------------------------------------------------------------------

% Makros

% Schreibhilfen
% \def \_ {\mbox{ }}
\def \ex {\exists \:}
\def \fa {\forall \:}
% Abkürzungen
\def \piv {pivot}
% math. Symbole
\def \bw {\mbox{{\bf \emph {Beweis}}}}
\def \epsilon {\varepsilon}
\def \limes {\lim\limits}
\def \nn {\rm{I}\!\rm{N}}
\def \rree {\rm{R}\!\rm{E}}
\def \rreecc {\rm{R}\!\rm{E}\!\rm{C}}
\def \rr {\rm{I}\!\rm{R}}
\newcommand \pot[1] {\mathfrak{P}(#1)}
\def \powerset {\pot}
\def \nnu {{\mathbb{N}_0}^U}
% Schreibweisen
\def \pos {\mathop{\mbox{\rm pos}}\mbox{}}
\def \fvec {\mathop{\mbox{\rm vec}}\mbox{}}
\def \rep {\mathop{\mbox{\rm rep}}\mbox{}}
\def \repinv {\rep^{inv}}

% Ben:
\newcommand{\qq}[1]{'#1'}
\newcommand{\halt}{\mbox{h\"{a}lt}}
\newcommand{\nohalt}{\mbox{h\"{a}lt nicht}}
\newcommand{\dm}[1]{\[ #1 \]\noindent}
\newcommand{\gdw}{\Leftrightarrow}
\newcommand{\kr}{\circ}
\newcommand{\mal}{\cdot}
\newcommand{\BBN}{\mathbb{N}}
\newcommand{\BBC}{\mathbb{C}}
\newcommand{\BBR}{\mathbb{R}}
\newcommand{\BBZ}{\mathbb{Z}}
\newcommand{\BBQ}{\mathbb{Q}}
\newcommand{\defeq}{=_{\text{\tiny{def}}}}
\newcommand{\Lim}[2]{\textrm{lim}}
\newcommand{\ptm}{\mathcal{P}}
\newcommand{\fixme}{{\ifpdf\OrangeRed\fi\Huge FixMe!}\ifpdf\Black\fi}
\newcommand{\skizze}{{\Huge Skizze}}
\newcommand{\tr}{\;|\;}



\newcommand{\stz}[3]{\begin{satz}{\bf (#1)}

#2\end{satz}

\begin{beweis}{\it #3}\hfill$\Box$\end{beweis}

\par\bigskip}



\newcommand{\fstz}[2]{\begin{fsatz}{\hspace{0.0cm}}

#1\end{fsatz}

\begin{beweis}{\it #2}\end{beweis}

\par\bigskip}


\newcommand{\defi}[2]{\begin{definition}{\bf (#1)}

#2\end{definition}

\par\medskip}


\newcommand{\Mat}{\textrm{Mat}}
\newcommand{\dom}{\operatorname {Dom}}
\newcommand{\Def}{\operatorname {def}}
\newcommand{\trans}{\operatorname {trans}}
\newcommand{\letter}{\operatorname {letter}}
\newcommand{\el}{\operatorname {l}}
\newcommand{\en}{\operatorname {n}}
\newcommand{\pr}{\operatorname {Pr}}
\newfont{\titelfont}{cmr10 scaled 1728}
\newfont{\titelbffont}{cmbx10 scaled 2074}
\newfont{\titelbigfont}{cmr10 scaled 2488}

% Tips:
%       \, \: \; \quad \qquad   ... Abstandshalter in Formeln
%       \! \negmedspace \negthickspace  ... entfernt Abstand
%       "-      ... macht einen Silbentrennungsvorschlag
%       \-      ... schreibt die Stelle der Silbentrennung vor
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%---------------------Deckblatt-------------------------------------------------------------

\begin{titlepage}
\begin{center}
  \Large \textbf{Friedrich-Schiller-Universität Jena}\\
  \Large Fakultät für Mathematik und Informatik\\
  \vspace{4cm}
  \Large
  \sffamily \textbf{Berechenbarkeit des Denkens?}\\
  \large
  \vspace{3,5cm}

  Examensarbeit\\
  zur Erlangung des akademischen Grades \\


  \vspace{0.1cm} \textbf{Bakkalaureus der Mathematik} \vspace{3cm}


vorgelegt von: \ {\bf Lars Mäurer}\\
geboren am: \ {\bf 11. September 1976}\\
Geburtsort: \ {\bf Jena}\\
Betreuer: \ {\bf Prof. Dr. G. Wechsung}\\
Tag der Einreichung: \ {\bf 22. August 2003}

\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{

\newpage

\thispagestyle{empty} \cleardoublepage \thispagestyle{empty}

{\Large \noindent

\par\bigskip

\hspace{0.5cm}

\par\bigskip

\textbf{Zusammenfassung} } \vspace*{0.5cm}

%\large
\noindent

Die Idee einer denkenden Maschine übt eine besondere Faszination auf uns aus, macht sie doch
eine Fähigkeit, die uns als Menschen definiert, zum Kopierbaren, zum Programm.

Die Fortschritte der Computertechnik in den letzten Jahrzehnten scheinen uns die Möglichkeit
immer näher zu bringen, menschliches Denken künstlich zu erzeugen. Geschwindigkeit,
Speicherkapazität und logisches Design werden sicherlich in den nächsten Jahren auch weiteren
Fortschritten unterworfen. Doch ist künstliche Intelligenz wirklich nur ein Problem
schnellerer Computer, größeren Speichers und ausgefeilterer Algorithmen?

{\sc Roger Penrose}, Rouse-Ball-Professor an der Universität Oxford, führt in seinem Buch
"`Schatten des Geistes"' \cite{sg} starke (und schwache) Argumente gegen zuviel Optimismus
ins Feld. Dieses vielfach kontrovers diskutierte Werk enthält einen faszinierend einfachen,
aber bedeutenden Gedanken, der die Berechenbarkeit des menschlichen Denkens in Frage stellt.
Diesen Gedanken einschließend soll diese Thematik in dieser Arbeit in gebührendem Maße
beleuchtet werden.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------Inhaltsverzeichnis------------------------------
\newpage
\thispagestyle{empty}
\cleardoublepage

\thispagestyle{empty}
\tableofcontents

\par\bigskip

\par\bigskip

{\bf Abkürzungen / mathematische Symbole \hfill \pageref{abkuerzungen}}

{\bf Literaturverzeichnis \hfill \pageref{biblio}}

{\bf Danksagung \hfill \pageref{danke}}

{\bf Erklärung \hfill \pageref{erklaer}}

\end{titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\thispagestyle{empty}
\cleardoublepage
\thispagestyle{empty}

\chapter{Einleitung / Vorbetrachtungen}

In den Jahren 1900 und 1928 formulierte {\sc David Hilbert}\footnote{{\sc David Hilbert}
(1862-1943), deutscher Mathematiker.} das sogenannte {\it Entscheidungsproblem}. Er forderte
ein allgemeines algorithmisches Verfahren zum Lösen mathematischer Probleme bzw. eine Antwort
auf die Frage, ob ein solches Verfahren überhaupt existieren kann.

Um über die Leistungsfähigkeit von solchen algorithmischen Verfahren zu urteilen, ist es
notwendig, eine formale Beschreibung dafür zu finden. Hier bieten sich die Arbeiten von {\sc
Alan Turing}\footnote{{\sc Alan Mathison Turing} (1912-1954), britischer Mathematiker. {\sc
Turing} gilt heute als einer der einflußreichsten Theoretiker der Berechenbarkeitstheorie und
der frühen Computerentwicklung.} aus den Jahren 1935/36 an. {\sc Turing} versuchte, die
Funktionsweise solcher Verfahren mit elementaren mathematischen Ausdrücken zu beschreiben.

Dabei spielen die Begriffe Algorithmus und {\sc Turing}-Maschine eine wichtige Rolle, die wir
in den nächsten Abschnitten vorstellen wollen.

\section{Algorithmen}

Ein Algorithmus ist ein systematisches Verfahren, mit Hilfe dessen eine bestimmte (sagen wir
mathematische) Fragestellung gelöst werden kann.

Beispiele für Algorithmen finden sich schon lange vor Beginn unserer Zeitrechnung in der
griechischen Antike. Einer der bekanntesten ist der {\it {\sc Euklid}ische
Algorithmus}\footnote{nach {\sc Euklid}, Eukleides von Alexandreia (ca. 300 v.u.Z.),
griechischer Naturwissenschaftler. Das Verfahren zur Bestimmung des größten gemeinsamen
Teilers wurde im 7. Buch seiner {\sc Elemente} erstmals vorgestellt.}.

Dieser Algorithmus beschreibt eine Verfahrensweise, für zwei natürliche Zahlen beliebiger
Größe nach einer gewissen Zeit deren größten gemeinsamen Teiler zu bestimmen. Für größere
Zahlen wird das Verfahren sicher länger brauchen, als bei sehr kleinen Zahlen, aber in jedem
Einzelfall wird es schließlich nach {\it endlich} vielen Schritten abbrechen und das korrekte
Ergebnis liefern. Dabei gibt das Verfahren {\it absolut exakt} an, was bei jedem einzelnen
Schritt der Rechnung zu tun ist. Außerdem ist das Verfahren durch {\it endlich} viele
Ausdrücke beschreibbar, zum Beispiel durch ein (endliches) Flußdiagramm, welches den
logischen Ablauf des Verfahrens beschreibt.

Dies sind genau die Anforderungen, die wir ganz allgemein an einen Algorithmus stellen
wollen: Algorithmen sind also systematische Verfahren, die uns exakt beschreiben, wie zu
jedem Zeitpunkt vorgegangen werden soll, die nach endlicher Zeit zum Stillstand (und damit
einem Ergebnis) gelangen, und die mit endlich vielen Ausdrücken beschrieben werden können.

In den dreißiger Jahren entstanden mehrere präzise Beschreibungen des Begriffes Algorithmus.
Der überzeugendste und auch historisch wichtigste Ansatz dieser Art wurde von dem
bahnbrechenden Informatiker {\sc Alan Turing} hervorgebracht und verwendet den Gedanken der
{\it {\sc Turing}-Maschine}.

%Um die Wichtigkeit dieser Gedanken zu verdeutlichen, soll hier eine wichtige Folgerung, die
%sich in den kommenden Jahrzehnten ergab, schon einmal aufgegriffen werden:

%Alle bis heute existierenden Computerarchitekturen sind beweisbar bestenfalls genauso mächtig
%wie eine {\sc Turing}-Maschine, alles, was ein Computer berechnen kann, kann prinzipiell auch von
%einer {\sc Turing}-Maschine berechnet werden.

\section{{\sc Turing}-Maschinen}

Wir stellen uns ein Band vor, welches sich nach links und rechts frei und unendlich weit
entfaltet und gleichmäßig in (wieder-)beschreibbare Felder unterteilt ist. In jedes Feld paßt
genau ein Zeichen aus einem vorher definierten Alphabet.

Unser Alphabet sei $\{0,1,\_\}$, wobei "`$\_$"' als Leerzeichen verstanden werden soll,
welches sich auf allen Feldern befindet, die nicht durch die {\em (echten)} Zeichen "`$0$"'
und "`$1$"' beschrieben sind. Wir werden später sehen, daß die Beschränkung auf dieses recht
kleine Alphabet keine echte Einschränkung der prinzipiellen Leistungsfähigkeiten von {\sc
Turing}-Maschinen darstellt.

In {\sc Turing}s Vorstellung besteht das "`Band"' aus einer linearen, in beide Richtungen
unendlichen Folge von Quadraten.

Eine {\it {\sc Turing}-Maschine} ist nun ein Apparat, der sich von Feld zu Feld auf diesem
Band hin- und herbewegen kann. Dieser Apparat kann das Zeichen, über dem er sich befindet,
lesen und durch ein anderes ersetzen. Außerdem befindet sich der Apparat in einem internen
Zustand, den er selbst verändern kann. Dies alles wird gesteuert durch ein Programm.

Dieses Programm gibt für jeden Zeittakt (abhängig vom momentanen Zustand und dem gelesenen
Zeichen) genau an, durch welches Zeichen das gelesene Zeichen ersetzt werden soll, in welche
Richtung sich der Apparat bewegen soll (die Maschine bewegt sich immer nur genau ein Feld
nach rechts oder links) und in welchen internen Zustand er übergehen soll.

Diese einfache Beschreibung einer Maschine folgt bei genauer Betrachtung exakt der
Handlungsweise eines Algorithmus in elementarer Form:

Man bekommt einen Input (in diesem Falle das Zeichen, welches die Maschine auf dem Band
vorfindet), gibt einen Output aus (das Zeichen, welches sie auf dem Band hinterläßt) und
begibt sich in einen anderen Zustand. Die Bewegungsfähigkeit der Maschine sichert, daß sie
sich auch anderen Inputs zuwenden kann, ebenso wie selbst niedergeschriebenen
Zwischenergebnissen.

Die Maschine beendet ihre Berechnungen (sie hält an), wenn sie den besonderen Zustand {\sf
STOP}, den sogenannten End-Zustand, erreicht.

An dieser Stelle ist ein kleines Beispiel nötig:

\par\bigskip

{\em Die Eingabe für die {\sc Turing}-Maschine (nennen wir sie $\rm{N}\!\rm{F}$, wie
"`Nachfolger"') besteht aus einer endlichen Folge von Nullen und Einsen, die als
Bi\-när\-zahl aufgefaßt wird. $\rm{N}\!\rm{F}$ soll zu dieser Binärzahl 1 addieren.

Sie startet im Zustand $z_1$ und steht an einer beliebigen Stelle der Eingabe, also der auf
das Band geschriebenen Binärzahl.

Hier zunächst einmal das Programm:

\par\bigskip

{\em \begin{center} \begin{tabular}{|c|ccc|}\hline $\rm{N}\!\rm{F}$&$0$&$1$&\_ \\ \hline
$z_1$& $0\rightarrow z_1$& $1\rightarrow z_1$& $\_\leftarrow z_2$\\
$z_2$& $1\leftarrow z_3$& $0\leftarrow z_2$& $1\leftarrow z_3$\\
$z_3$& $0\leftarrow z_3$& $1\leftarrow z_3$& {\sf STOP}\\
\hline
\end{tabular}\\
\end{center}}

\par\bigskip

Hierbei stehen in den Zeilen der Tabelle die Zustände, in denen sich die Maschine befinden
kann. In den Spalten findet man für jedes Zeichen, das gelesen wird, die Anweisungen, wie
sich die Maschine verhalten soll. Man findet also für jedes gelesene Zeichen und jeden
internen Zustand einen genauen Eintrag, wie die Maschine arbeitet.

Das erste Zeichen jedes Eintrages gibt an, wodurch das gelesene Zeichen ersetzt werden soll.
Der Pfeil zeigt die Bewegungsrichtung der Maschine an, und zuletzt wird der Zustand
angegeben, den der Apparat einzunehmen hat.

Beobachten wir, wie die Maschine auf eine Eingabe reagiert:

Im Zustand $z_1$ läuft $\rm{N}\!\rm{F}$ solange nach rechts, bis sie das erste "`$\_$"'
erreicht. Dies wird erreicht, indem alle Zeichen, die sich von "`$\_$"' unterscheiden,
ignoriert werden und weiter nach rechts gelaufen wird. Findet die Maschine ein "`$\_$"', geht
sie einen Schritt nach links und wechselt zum Zustand $z_2$. Sie befindet sich nun auf der
letzten Stelle der Binärzahl.

\newpage

Im Zustand $z_2$ geht das eigentliche Addieren der 1 vor sich. Die Maschine ersetzt nach
links gehend solange Einsen durch Nullen, bis sie zum ersten Mal auf "`$0$"' oder "`$\_$"'
trifft. Dieses ersetzt $\rm{N}\!\rm{F}$ durch "`$1$"', geht einen Schritt nach links und
wechselt zum Zustand $z_3$. In diesem Zustand läuft $\rm{N}\!\rm{F}$ bis zum nächsten
"`$\_$"' nach links und hält dann an. Die Maschine steht nun auf dem Leerzeichen direkt vor
der ersten Ziffer der Binärzahl.

Man kann sich leicht davon überzeugen, daß die angegeben Maschine tat\-sächlich zu jeder
beliebigen Binärzahl 1 addiert.}

\par\medskip

{\sc Turing}-Maschinen sind, damit sie exakt arbeiten, auf gewisse Vereinbarungen angewiesen.

Auch die hier beschriebene Maschine $\rm{N}\!\rm{F}$ arbeitet nicht korrekt, wenn sie am
Anfang nicht auf einer Ziffer einer Binärzahl (endlich!) steht:\\
Besteht das Band anfangs ausschließlich aus Leerzeichen, stoppt die Maschine, nachdem sie
eine 1 auf das Band geschrieben hat.\\
Eine unendlich große Eingabe aus Nullen und Einsen läßt die Maschine scheitern (sie hält dann
nicht an), da sie das Ende der Zahl niemals erreichen kann.

Deshalb legt man für {\sc Turing}-Maschinen gewisse sinnvolle Vereinbarungen fest.

In jedem einzelnen Fall muß der Input {\em endlich} sein. Wir verstehen als Input die von
Leerzeichen verschiedenen Zeichen (also Nullen und Einsen), und zusätzlich einzelne
(Trennungs-)Leerzeichen, die sich zwischen Nullen und Einsen befinden. Demnach enthält das
Band, obwohl es laut Annahme unendlich groß ist, zu jedem Berechnungsschritt jeweils nur
endlich viele von Leerzeichen verschiedene Zeichen. In beiden Richtungen kann das Band also
jenseits eines gewissen Feldes (abhängig von den bis dahin vollführten "`Berechnungen"') nur
noch Leerzeichen enthalten. Es ist außerdem sinnvoll, die Maschine am Anfang direkt auf dem
am weitesten links stehenden Zeichen der Eingabe starten zu lassen.

Die allgemeine Forderung der endlichen Beschreibbarkeit, die wir auch an einen Algorithmus
stellen wollen, stellt sich im Falle der {\sc Turing}-Maschinen wie folgt dar:

Jede {\sc Turing}-Maschine besteht nur aus endlich vielen internen Zuständen.

{\sc Turing}-Maschinen dürfen prinzipiell beliebig lange laufen, um zu einem Ergebnis zu
gelangen. Wenn eine {\sc Turing}-Maschine allerdings niemals anhält, ist das Ergebnis nicht
definiert. Schließlich können wir erst dann den Inhalt des Bandes als endgültigen Output
interpretieren, wenn die Maschine ihre Berechnung beendet hat.

Mit diesen Vereinbarungen kann man die Leistungsfähigkeit von {\sc Tu\-ring}-\-Ma\-schi\-nen
folgendermaßen umschreiben:

Eine {\sc Turing}-Maschine findet auf dem Band eine Eingabe vor und läßt (sofern sie nach
endlicher Zeit stoppt) auf dem Band eine Ausgabe zurück. Um eine absolut deterministische
Verhaltensweise der {\sc Turing}-Maschine zu garantieren, vereinbaren wir nun, daß sich die
Maschine am Anfang der Berechnung immer auf dem ersten (am weitesten links stehenden) Zeichen
des Inputs befinden soll.

Die oben beschriebene Maschine $\rm{N}\!\rm{F}$ errechnet somit in der Tat den Nachfolger
einer auf dem Band befindlichen Binärzahl.

\par\medskip

Es ist prinzipiell nicht schwer, {\sc Turing}-Maschinen auch schwierigere Aufgaben ausführen
zu lassen, zum Beispiel das Addieren von beliebig großen Zahlen, auch das Multiplizieren der
Eingabe mit festen Faktoren, ebenso das Addieren oder Multiplizieren von mehreren Eingaben,
die sich, durch Leerzeichen getrennt, hintereinander auf dem Eingabeband befinden.

Auch weitaus kompliziertere Rechnungen stellen kein prinzipielles Problem dar, sondern sind
allenfalls mit einer beträchtlichen Erhöhung der Zustandsanzahl verbunden, so zum Beispiel
die Berechung einer bestimmten Ziffer von $\pi$.

\par\medskip

{\sc Turing}s Überlegungen zeigten, daß die Beschränkung auf ein bestimmtes endliches
Alphabet (wir hatten uns weiter oben auf das Alphabet $\{0,1,\_\}$ beschränkt) nichts an den
prinzipiellen Fähigkeiten von {\sc Turing}-Maschinen ändert, die lediglich dieses sehr kleine
Alphabet verwenden dürfen:

Für jede {\sc Turing}-Maschine, die ein anderes Alphabet verwendet, läßt sich eine neue {\sc
Turing}-Maschine finden, die lediglich das Alphabet $\{0,1,\_\}$ benutzt, aber prinzipiell
das gleiche leistet.

Gegebenenfalls müssen dabei auch Input und Output in das neue Alphabet übersetzt werden. Die
neue Maschine wird eventuell länger als die alte Maschine brauchen, aber immer, wenn die alte
Maschine zu einem bestimmten Ergebnis gelangt ist, wird die neue Maschine zum gleichen
Ergebnis kommen.

\par\medskip

Wir wollen uns deshalb im Rahmen dieser Arbeit auf das obige Alphabet $\{0,1,\_\}$
beschränken.

Wo allerdings stößt man auf die Grenzen der Berechenbarkeit durch {\sc Turing}-Maschinen? Ist
jede mathematische Rechnung, die wir intuitiv als "`berechenbar"' auf"|fassen würden, auch
durch {\sc Turing}-Maschinen berechenbar?

\newpage

\section{{\sc Turing}-Berechenbarkeit}

Eine der wichtigsten Erkenntnisse über {\sc Turing}-Maschinen ist die Überlegung, daß wir
jede beliebige {\sc Turing}-Maschine $M$ als eine spezielle einstellige Funktion $f_M$
interpretieren können, die bestimmte natürliche Zahlen auf natürliche Zahlen abbildet.

Unsere Vereinbarung, nur endlich große Inputs auf dem Band zuzulassen, gestattet uns folgende
Vorgehensweise:

(a)\\
Wir codieren den kompletten {\em (endlichen!)} Input, welcher sich zu Beginn der Berechnung
auf dem Band befindet, durch eine natürliche Zahl. Auch bei mehreren Binärzahlen, die sich
(durch Leerzeichen getrennt) als Eingabe auf dem Band befinden, ist dies problemlos möglich.

(b)\\
Ebenso codieren wir den kompletten Output der Maschine, falls sie den End-Zustand erreicht
hat, durch eine natürliche Zahl.

(c)\\
Die Funktion $f_M$ bildet nun natürliche Zahlen folgendermaßen auf natürliche Zahlen ab:

Falls die Maschine $M$ bei Eingabe (Input) von $i$ den End-Zustand mit dem Output $j$
erreicht, gilt $f_M(i)=j$.

Hält eine {\sc Turing}-Maschine $M$ bei Eingabe einer bestimmten natürlichen Zahl nicht an,
so gehört diese Zahl nicht zum Definitionsbereich der entsprechenden Funktion $f_M$. Jede
{\sc Turing}-Maschine bildet also eine Teilmenge der natürlichen Zahlen ${\nn}$ in die
natürlichen Zahlen ab.

\par\bigskip

\defi{{\sc Turing}-Berechenbarkeit}
{Eine Funktion \hspace{0.1cm} $f : {\nn}\to{\nn}$ \hspace{0.1cm} heißt {\bf {\sc
Turing}-berechenbar}, wenn es eine {\sc Turing}-Maschine gibt, die für alle Eingaben aus dem
Definitionsbereich der Funktion den Funktionswert berechnet und bei allen anderen Eingaben
nicht an\-hält.}

Eine weitere entscheidende Eigenschaft von {\sc Turing}-Maschinen ist, daß man {\sc
Turing}-Maschinen "`{\sc gödel}isieren"'\footnote{nach {\sc Kurt Gödel} (1906-1978),
österreichischer Mathematiker und Logiker. {\sc Gödel} wird von vielen als der bedeutendste
Logiker des 20. Jahrhunderts angesehen.} kann. Damit ist die Möglichkeit gemeint, eine
eineindeutige Funktion anzugeben, die jeder {\sc Turing}-Maschine eine natürliche Zahl
zuordnet.

{\sc Turing}-Maschinen sind durch ihr (endliches) Programm eindeutig beschrieben. Es stellt
kein besonders schwieriges Problem dar, diese Programme eineindeutig durch natürliche Zahlen
zu codieren.

Natürlich werden dabei jede Menge "`Blindgänger"' entstehen -- Programme, die überhaupt
nichts berechnen und bei keiner einzigen Eingabe anhalten. So werden z.B. verschiedene {\sc
Turing}-Maschinen ungeachtet dessen, was sie auf dem Band vorfinden, stur in eine Richtung
laufen; andere können nicht zu einem Ende kommen, weil niemals in den End-Zustand {\sf STOP}
gewechselt wird.

Das alles stellt aber kein Problem dar, weil wir ja ausdrücklich auch Teilmengen der
natürlichen Zahlen (also auch die leere Menge $\emptyset$) als Definitionsbereiche der zu den
{\sc Turing}-Maschinen gehörenden Funktionen erlaubt haben.

Unsere Beschränkung auf {\sc Turing}-Maschinen, die mit dem sehr kleinen Alphabet
$\{0,1,\_\}$ arbeiten, vereinfacht natürlich die Codierung der Programme.

Jede {\sc Turing}-Maschine wird also durch eine spezielle natürliche Zahl eindeutig
beschrieben. Ebenso gehört zu jeder natürlichen Zahl eindeutig eine bestimmte {\sc
Turing}-Maschine.

\par\medskip

Da jede {\sc Turing}-Maschine $M$ außerdem als eine gewisse Funktion $f_M$ interpretierbar
ist, gelangen wir zu folgender Definition:

\defi{\boldmath$M_i$\unboldmath, \boldmath$D_i$\unboldmath}
{Die eindeutig bestimmte Funktion, die von der $i$-ten {\sc Turing}-Maschine berechnet wird,
bezeichnen wir mit $M_i$, deren Definitionsbereich mit $D_i$, also:

$M_i : D_i\to{\nn}$ mit $(i \in {\nn},~D_i\subseteq{\nn})$.}

Die Schreibweise $M_i(j)$ umschreibt also den Funktionswert der Funktion $M_i$ an der Stelle
$j$, d.h. den Output der $i$-ten Maschine, wenn sie den Input $j$ erhält. Man spricht hier
auch von der Berechnung $M_i(j)$.

Nehmen wir also einmal an, die oben beschriebene Maschine $\rm{N}\!\rm{F}$ habe die Nummer
110976, dann können wir schreiben:

$M_{110976}(x)=x+1$ für alle $x\in{\nn}$

Obwohl wir die Bezeichnung $M_i$ für die Funktion verwenden, die durch die $i$-te {\sc
Turing}-Maschine berechnet wird, ist es üblich, auch die Maschine selbst mit $M_i$ zu
bezeichnen. Eine Begriffsvertauschung ist normalweise durch den Kontext nicht möglich, zumal
{\sc Turing}-Maschinen und die jeweiligen Funktionen, die sie berechnen, sich ohnehin
entsprechen.

\par\medskip

Fassen wir noch einmal zusammen:

Ohne die prinzipielle Funktionalität beliebiger {\sc Turing}-Maschinen ein\-zu\-schrän\-ken,
können wir uns auf die Betrachtung spezieller {\sc Turing}-Maschinen be\-schrän\-ken, die mit
dem Alphabet $\{0,1,\_\}$ arbeiten und die zu Beginn der Berechnung auf dem am weitesten
links stehenden Zeichen des Inputs stehen. Jede solche {\sc Turing}-Maschine kann als
Funktion aufgefaßt werden, die natürliche Zahlen (den Input) aus ihrem Definitionsbereich auf
natürliche Zahlen (den Output) abbildet. Außerdem können wir jeder dieser Maschinen bzw.
Funktionen in eindeutiger Art und Weise eine natürliche Zahl zuordnen.

Die {\sc Turing}-berechenbaren Funktionen sind also genau die Funktionen\\
$M_0, M_1, M_2, M_3, ...$, denen exakt sämliche {\sc Turing}-Maschinen entsprechen.

Wir definieren nun eine Menge, die in unseren weiteren Untersuchungen eine wichtige Rolle
spielen wird:

\defi{\boldmath$\rree$\unboldmath\label{rree}}
{$\rree$ $:=\{D_i:i\in{\nn}\}$}

Was bedeutet diese Definition?

In der Menge $\rree$ befinden sich die Definitionsbereiche aller {\sc
Tu\-ring}-\-be\-re\-chen\-ba\-ren Funktionen, gewissermaßen die Definitionsbereiche aller
{\sc Turing}-Maschinen. Zu jeder dieser Mengen gibt es also eine {\sc Turing}-Maschine, die
bei Eingabe von Elementen der Menge anhält (also den {\sf STOP}-Zustand erreicht) und bei
allen restlichen Eingaben nicht anhält. Da jedes $D_i$ eine Teilmenge der natürlichen Zahlen
ist, handelt sich also um eine Teilmenge der Potenzmenge von ${\nn}$.

Die Elemente von $\rree$ (engl. $R$ecursively $E$numerable) nennen wir {\em aufzählbare}
Mengen.

Gebräuchlich ist auch folgende Sprechweise: Die {\sc Turing}-Maschine $M_i$ zählt die Menge
$D_i$ auf.

\par\bigskip

Gibt es überhaupt Teilmengen von ${\nn}$, die nicht Elemente von $\rree$ sind? Der folgende
Satz wird uns bei der Beantwortung dieser Frage helfen:

\stz{Die Kardinalität von \boldmath$\rree$\unboldmath \label{kard(rree)}}{$\rree$ und ${\nn}$
sind gleichmächtig\footnote{Zwei Mengen sind gleichmächtig, wenn ihre Kardinalität (oder
Mächtigkeit) übereinstimmt. Es gibt dann eine eineindeutige Abbildung der einen Menge auf die
andere.}.}{

Die Definition von $\rree$ zeigt sofort, daß die Kardinalität von $\rree$ nicht größer als
die Kardinalität der natürlichen Zahlen ist.

Jeder einzelne Definitionsbereich geh\-ört zu vielen verschiedenen {\sc
Tu\-ring}-\-Ma\-schi\-nen. Zum Beispiel kann man für eine bestimmte {\sc Turing}-Maschine den
{\sf STOP}-Zustand durch einen weiteren Zustand ersetzen, der den Output unverändert läßt und
in jedem Fall als nächstes in den {\sf STOP}-Zustand wechselt. Diese neue {\sc
Turing}-Maschine hat natürlich den gleichen Defintionsbereich wie die alte, hat aber eine
andere ({\it vermutlich größere}) Nummer.

Deshalb ist es nötig zu zeigen, daß die Kardinalität von $\rree$ nicht kleiner als die
Kardinalität von ${\nn}$ ist.

Für Mengen der Form $\{n\}$ (also Mengen, die nur eine einzige natürliche Zahl enthalten)
kann man trivial {\sc Turing}-Maschinen angeben, deren Definitionsbereich $\{n\}$ ist:

Die {\sc Turing}-Maschinen werden einfach in eine unendlich lang laufende Schleife gelenkt,
es sei denn, die Zahl $n$ liegt als Input vor. Dann lassen wir die Maschine in den {\sf
STOP}-Zustand übergehen. Die Menge $\{n\}$ ist also für jedes $n\in{\nn}$
aufzählbar.\footnote{Auf ähnliche Art kann man leicht zeigen, daß {\em jede} endliche Menge
aufzählbar ist.}

Auf diese Art und Weise erhalten wir so viele {\it echt verschiedene} Definitionsbereiche,
wie es natürliche Zahlen gibt.

Somit sind $\rree$ und ${\nn}$ gleichmächtig.}

Gemäß der mächtigen und schönen Theorie der transfiniten Zahlen, die gegen Ende des 19.
Jahrhunderts von {\sc Georg Cantor}\footnote{{\sc Georg Cantor} (1845-1918), deutscher
Mathematiker. {\sc Cantor} gilt als Begründer der Mengenlehre und lieferte wichtige Beiträge
zur modernen Mathematik.} entwickelt wurde, ist die Kardinalität von ${\nn}$ gleich der
transfiniten Zahl mit der Bezeichnung $\aleph_0$ ("`Aleph null"'). Man sagt in diesem
Zusammenhang auch: ${\nn}$ ist eine {\it abzählbar unendliche} Menge.

Außerdem ergibt sich, daß die Kardinalität der Menge aller Teilmengen der natürlichen Zahlen,
also der {\it Potenzmenge} von ${\nn}$, echt größer als die Kardinalität von ${\nn}$
ist\footnote{Es gilt sogar ganz allgemein, daß die Kardinalität der Potenzmenge einer Menge
echt größer ist als die Kardinalität der Menge selbst.}. Mathematiker bezeichnen diese
transfinite Zahl mit $\aleph_1$. Es gilt also $\aleph_0<\aleph_1$.

Hat eine Menge die Kardinalität $\aleph_1$, spricht man von einer {\it überabzählbar
unendlichen} Menge. Andere überabzählbar unendliche Mengen sind z.B. die {\it reellen Zahlen}
oder auch die {\it reellen Zahlen zwischen $0$ und $1$}.

Die Menge der aufzählbaren Mengen $\rree$ ist also eine {\it abzählbar unendliche} Menge; die
Potenzmenge von ${\nn}$ ist dagegen eine {\it überabzählbar unendliche} Menge.

Indem wir jetzt auf unsere ursprüngliche Frage zurückkommen, ob es überhaupt
nicht-aufzählbare Teilmengen von ${\nn}$ gibt, stellen wir fest, daß die aufzählbaren Mengen
nur eine abzählbar unendliche Teilmenge der Potenzmenge von ${\nn}$ bilden.

\section{Das Halteproblem}

Wir wollen nun eine spezielle nicht aufzählbare Menge direkt angeben. Dazu führen wir
zunächst eine wichtige verkürzende Schreibweise ein, die in der gesamten vorliegenden Arbeit
Verwendung finden wird:

\par\bigskip

\fbox{\parbox{10.8cm}{\boldmath$M_i(j)=\bot$\unboldmath \hspace{0.2cm} soll bedeuten:\\
die $i$-te {\sc Turing}-Maschine {\em hält} bei Eingabe von $j$ {\em nicht an},

\boldmath$M_i(j)\neq\bot$\unboldmath \hspace{0.2cm} bedeutet:\\
die $i$-te {\sc Turing}-Maschine {\em hält} bei Eingabe von $j$ {\em an}.}}

\par\bigskip

Betrachten wir nun die folgende Menge:

\defi{Halteproblem\label{kaa}}
{$\overline{K}:=\{n\in{\nn}:M_n(n)=\bot\}$}

$\overline{K}$ enthält die Nummern aller {\sc Turing}-Maschinen, die bei Eingabe ihrer
eigenen Nummer nicht anhalten.

Diese Menge ist nicht aufzählbar, wie der folgende Satz zeigt:

\stz{Nichtaufzählbarkeit des Halteproblems\label{halteproblem}}{$\overline{K}\notin\rree$}
{(indirekt)

Nehmen wir $\overline{K}\in\rree$ an. Demnach ist $\overline{K}$ der Definitionsbereich einer
{\sc Turing}-Maschine, sagen wir $M_k$ (die Maschine habe also die Nummer $k$):

$\overline{K}=D_k$

Es gilt also für beliebige $n\in{\nn}$:

$n\in \overline{K} \Leftrightarrow M_k(n)\neq\bot$, d.h. für $n \in \overline{K}$ hält die
Berechnung $M_k(n)$ an.

Außerdem gilt $n\in \overline{K} \Leftrightarrow M_n(n)=\bot$ für alle $n \in {\nn}$ nach der
Definition von $\overline{K}$. Daraus folgt für beliebige $n\in{\nn}$:

$M_k(n)\neq\bot \Leftrightarrow M_n(n)=\bot$

Setzen wir $n=k$:

$M_k(k)\neq\bot \Leftrightarrow M_k(k)=\bot$

Das ist ein Widerspruch. Daraus folgt: $\overline{K}\notin\rree$}

\section{{\sc Church}-{\sc Turing}-These}

Wie wir schon festgestellt haben, können {\sc Turing}-Maschinen auch sehr schwierige
mathematische Algorithmen ausführen. Je länger man sich mit den Fähigkeiten von {\sc
Turing}-Maschinen auseinandersetzt, desto überzeugender erscheint die Vermutung, daß
derartige Maschinen im Prinzip {\it jede beliebige algorithmische Operation} ausführen
können. Solange ein bestimmtes algorithmisches Rechenverfahren genügend klar umrissen ist,
kann man vernünftigerweise annehmen, daß sich zu seiner Ausführung eine {\sc Turing}-Maschine
konstruieren läßt.

Im Zuge des von {\sc David Hilbert} formulierten "`Entscheidungsproblems"'
be\-schäf\-tig\-ten sich außer {\sc Turing} auch andere Wissenschaftler mit dem Versuch, den
Begriff der Berechenbarkeit auf eine theoretische Basis zu stellen. Dabei entstanden
vielfältige Modelle algorithmischen Arbeitens (Lambda-Kalkül, {\sc
Mar\-kov}-\-Al\-go\-rith\-men\footnote{nach {\sc Andrei Markov} (1903-1979), russischer
Mathematiker und Logiker.}, partiell rekursive Funktionen etc.).

Verblüffenderweise gelangt man zu der Erkenntnis, daß die Mengen der Funktionen, die nach
diesen Modellen jeweils berechenbar sind, sich präzise gleichen. Die verschiedenen Modelle
zur Beschreibung von Algorithmen erweisen sich als vollkommen äquivalent.

Dadurch ist man allgemein zu der durchaus naheliegenden Ansicht gelangt, daß unsere intuitive
Vorstellung von einem algorithmischen (oder mechanischen, effektiven oder rekursiven)
Verfahren sich exakt durch den Begriff der {\sc Turing}-Maschine definieren läßt. Dieser
Standpunkt wurde als {\sc Church}-{\sc Turing}-These\footnote{{\sc Alonzo Church}
(1903-1995), amerikanischer Mathematiker, einer der Begründer der theoretischen Informatik.}
bekannt. {\sc Alonzo Church} hatte unabhängig von {\sc Alan Turing} die Theorie des
sogenannten Lambda-Kalküls entwickelt.

Heute, im Zeitalter immer schnellerer Computer mit immer größeren Spei\-cher\-ein\-hei\-ten,
wird kaum jemand diese These anzweifeln.

Unter Verwendung der {\sc Church}-{\sc Turing}-These werden wir uns nun endgültig der Lösung
des ursprünglichen {\sc Hilbert}schen Entscheidungsproblems nähern.

\section {Das {\sc Hilbert}sche Entscheidungsproblem}

{\sc Turing}s Ideen waren ursprünglich zu dem Zweck entwickelt worden, das {\sc Hilbert}sche
"`Entscheidungsproblem"' zu lösen. Zur Erinnerung:

Nicht weniger als ein allgemeines algorithmisches Verfahren zum Lösen mathematischer Probleme
war gesucht.

{\sc Turing} entwickelte die folgende Version der ursprünglichen Frage: Können wir jemals ein
algorithmisches Verfahren vorlegen, welches für jede natürliche Zahl $n$ entscheidet, ob die
$n$-te {\sc Turing}-Maschine bei Eingabe von $n$ anhält? Die Antwort, die uns {\sc Turing}
geben konnte, lautet: Nein.

\par\bigskip

Versuchen wir zu verstehen, wie er zu diesem Ergebnis gekommen war:

Nehmen wir dazu an, es gebe das gesuchte Verfahren. Die {\sc Church}-{\sc Turing}-These sagt
aus, daß jedes algorithmische Verfahren durch eine {\sc Turing}-Maschine beschreibbar ist. Es
ist nun nicht mehr schwer einzusehen, daß es also eine {\sc Turing}-Maschine geben muß, die
entscheidet, ob die $n$-te {\sc Turing}-Maschine bei Eingabe von $n$ anhält. Wir wollen diese
Maschine $H$ nennen.

Es muß sich bei der Maschine $H$ um eine sogenannte {\it uni\-ver\-sel\-le {\sc
Tu\-ring}-\-Ma\-schi\-ne} handeln. Damit sind {\sc Turing}-Maschinen gemeint, die imstande
sind, andere {\sc Turing}-Maschinen zu simulieren (imitieren).

Wir können nun annehmen, $H$ liefert (bei Eingabe von $n$) auf dem Band die Zahl $1$, wenn
die $n$-te {\sc Turing}-Maschine anhält, anderenfalls die Zahl $0$.

Es gilt dann für alle $n\in{\nn}$:
\[ H(n)=\left\{ \begin{array}{ll}

    \mbox{0} & \mbox{falls $M_n(n)=\bot$}\\

    \mbox{1} & \mbox{falls $M_n(n)\neq\bot$}
  \end{array}\right.\]

Es ist leicht, nun eine {\sc Turing}-Maschine $H^*$ zu konstruieren, die für alle $n\in{\nn}$
folgendermaßen arbeitet:
\[ H^*(n)=\left\{ \begin{array}{ll}

    \mbox{0} & \mbox{falls $M_n(n)=\bot$}\\

    \mbox{$M_n(n)+1$} & \mbox{falls $M_n(n)\neq\bot$}
  \end{array}\right.\]

Dies ist möglich, weil wir im Falle von $M_n(n)\neq\bot$ einfach die Rechnung $M_n(n)$ von
$H^*$ imitieren lassen können, bevor wir zum Schluß noch $1$ addieren.

Wie wir wissen, besitzt jede {\sc Turing}-Maschine eine Nummer. Die Nummer von $H^*$ sei k
(wobei natürlich $k\in{\nn}$). $H^*$ ist also genau die Maschine $M_k$.

Wir setzen speziell $n=k$, es gilt nun:
\[ H^*(n)=M_k(k)=\left\{ \begin{array}{ll}

    \mbox{0} & \mbox{falls $M_k(k)=\bot$}\\

    \mbox{$M_k(k)+1$} & \mbox{falls $M_k(k)\neq\bot$}
  \end{array}\right.\]

Der erste Fall ($M_k(k)=\bot$) kann allerdings nie erfüllt sein, weil dann $M_k(k)=0$ wäre,
obwohl $M_k(k)=\bot$ gilt, was bedeutet, daß $M_k(k)$ niemals anhält. Aber auch der zweite
Fall ($M_k(k)\neq\bot$) ist ausgeschlossen, weil dann $M_k(k)=M_k(k)+1$ gelten würde.

Also kann es das Verfahren, dessen Existens wir zunächst angenommen haben, nicht geben. Kein
algorithmisches Verfahren ist fähig zu entscheiden, ob die $n$-te {\sc Turing}-Maschine bei
Eingabe von $n$ anhält oder nicht. Es existiert also kein allgemeines algorithmisches
Verfahren zum Lösen mathematischer Probleme. {\sc Hilbert}s Fragestellung ist gelöst.

\newpage

\chapter{Berechenbarkeit des Denkens?}

Die Tatsache, daß die im Abschnitt über das Halteproblem beschriebene Menge

\begin{center}$\overline{K}:=\{n\in{\nn}:M_n(n)=\bot\}$\end{center}

nicht aufzählbar ist, konnte das {\sc Hilbert}sche Entscheidungsproblem lösen. Das
Halteproblem wird uns in leicht abgewandelter Form auch weiterhin beschäftigen.

Wir wollen versuchen, eine Leistung des menschlichen Denkens zu beschreiben, zu der kein
Algorithmus (also keine {\sc Turing}-Maschine) fähig ist.

Insbesondere wird uns die menschliche Fähigkeit zum korrekten mathematischen Schlußfolgern
interessieren.

\section{Ein paar Vorbereitungen}

Zunächst definieren wir noch eine weitere wichtige Menge.

\defi{\boldmath$\rreecc$\unboldmath\label{rreecc}}
{$\rreecc:=\{M\subseteq{\nn} : M\in\rree \wedge \overline{M}\in\rree\}$}

Dabei bezeichnet $\overline{M}$ das Komplement von $M$, also ${\nn} \backslash M$. Sie
enthält diejenigen natürlichen Zahlen, die nicht in $M$ enthalten sind.

Die Elemente von $\rreecc$ werden {\em entscheidbare} Mengen genannt. Die Bezeichnung ist
durchaus suggestiv gewählt.

Der Unterschied zu den Elementen von $\rree$, den aufzählbaren Mengen, besteht in folgendem:

Eine Menge $M\in\rreecc$ muß zwei Eigenschaften erfüllen:

\begin{enumerate}

\item[(1)] $M\in\rree$, d.h. es gibt eine {\sc Turing}-Maschine, sagen wir $M_i$, die $M$
aufzählt, es gilt also für beliebige $n\in{\nn}$:

$M_i(n)\neq\bot \Leftrightarrow n\in M$

\item[(2)] $\overline{M}\in\rree$, d.h. es gibt eine andere {\sc Turing}-Maschine, sagen wir
$M_j$, die $\overline{M}$ aufzählt. Hier gilt für alle $n\in{\nn}$:

$M_j(n)\neq\bot \Leftrightarrow n\notin M$

\end{enumerate}

Man kann nun eine dritte {\sc Turing}-Maschine, sagen wir $M_k$, konstruieren, die für jede
beliebige Eingabe $n$ abwechselnd jeweils einen Berechnungsschritt von $M_i$ und $M_j$
simuliert. Die Maschine soll die Simulation beenden, wenn eine der beiden Maschinen anhält.
Bevor sie endgültig anhält, soll sie nun noch eine Ausgabe nach folgendem Muster produzieren:
\[ M_k(n)=\left\{ \begin{array}{ll}

    \mbox{1} & \mbox{falls $n\in M$}\\

    \mbox{0} & \mbox{falls $n\notin M$}
  \end{array}\right.\]

Die Ausgabe der Maschine bei einer Eingabe von $n$ teilt uns also mit, ob $n\in M$ oder
$n\notin M$ gilt. In diesem Sinne ist die Bezeichnung {\em entscheidbare} Menge zu verstehen.
Man spricht auch davon, daß die Maschine $M_k$ die Menge $M$ {\em entscheidet}.

Daß es aufzählbare, aber nicht entscheidbare Mengen gibt, zeigt folgender Hilfssatz:

\begin{hilfssatz}

$\rreecc\subset\rree$

\end{hilfssatz}

\begin{beweis}

{\it $\rreecc\subseteq\rree$ folgt sofort aus der Definition von $\rreecc$.

Es genügt eine aufzählbare, nicht entscheidbare Menge anzugeben:

$K:=\{n\in{\nn}:M_n(n)\neq\bot\}$

Diese Menge ist das Komplement zur Menge $\overline{K}$ (siehe Seite \pageref{kaa}) und
enthält die Nummern aller {\sc Turing}-Maschinen, die bei Eingabe ihrer eigenen Nummer
anhalten. Zum Beweis von $K\in\rree$ konstruieren wir trivial eine {\sc Turing}-Maschine, die
bei Eingabe von $n$ exakt $M_n(n)$ simuliert. Diese Maschine hält genau dann an, wenn
$M_n(n)$ anhält.

Da $\overline{K}$ nicht aufzählbar ist (siehe Satz \ref{halteproblem} auf Seite
\pageref{halteproblem}), ist $K$ nicht entscheidbar.}\hfill$\Box$

\end{beweis}

\par\bigskip

Auch die Menge $\rreecc$ ist eine unendliche Menge, da die im Beweis von Satz
\ref{kard(rree)} erwähnten endlichen Mengen, die nur eine einzige natürliche Zahl enthalten,
entscheidbare Mengen sind. Wegen $\rreecc\subset\rree$ sind $\rreecc$ und $\rree$ somit
gleichmächtig.

\section{Menschliches Denken}

In der Definition \ref{kaa} (Seite \pageref{kaa}) wurde die Menge $\overline{K}$
(Halteproblem) beschrieben. Die Menge $\overline{K}$ enthält die Nummern aller Maschinen, die
bei Eingabe ihrer eigenen Nummer nicht anhalten. Diese Menge ist nicht aufzählbar. Dennoch
kann man für viele natürliche Zahlen schlüssig und korrekt nachweisen, daß sie zur Menge
$\overline{K}$ gehören.

Zum Beispiel gibt es viele Maschinen, die bei keiner einzigen Eingabe anhalten, weil ihr
gesamter Befehlsaufbau keine vernünftige Berechnung zuläßt.\footnote{Diese sogenannten
Blindgänger können unter anderem entstehen, wenn in keinem der Programmschritte in den {\sf
STOP}-Zustand gewechselt wird oder wenn das Programm insgesamt unvollständig ist.} Ebenso
kann man sicher bei vielen Maschinen leicht zeigen, daß sie unabhängig von der Eingabe nach
einer gewissen Zeit in eine unendliche Schleife geraten:

{\em \begin{center} \begin{tabular}{|c|ccc|}\hline $S$&$0$&$1$&\_ \\ \hline
$z_1$& $0\rightarrow z_2$& $1\rightarrow z_2$& $\_\rightarrow z_2$\\
$z_2$& $0\leftarrow z_1$& $1\leftarrow z_1$& $\_\leftarrow z_1$\\
$z_3$& {\sf STOP}& {\sf STOP}& {\sf STOP}\\
\hline
\end{tabular}\\
\end{center}}

Diese Maschine $S$ läuft im ersten Zustand (unabhängig von der Eingabe) immer einen Schritt
nach rechts, um dann in den zweiten Zustand zu wechseln. Dort läuft sie einen Schritt nach
links und wechselt wieder in den ersten Zustand.

Diese Liste kann man beliebig fortsetzen.

Man könnte sogar meinen, wenn man eine vorgegebene Maschine hinreichend lange untersucht,
wird man immer verstehen, wie sie genau arbeitet, und dementsprechend beweisen können, wenn
sie tatsächlich bei Eingabe ihrer eigenen Nummer nicht anhält.

Diese Behauptung ist nicht haltbar, da man relativ leicht {\sc Turing}-Maschinen angeben
kann, die ein bestimmtes mathematisches (sagen wir zahlentheoretisches) Problem lösen. So
kann man z.B. recht einfach eine Maschine konstruieren, die ({\em unabhängig} von der
Eingabe) genau dann anhält, wenn die {\sc Goldbach}sche\footnote{{\sc Christian Goldbach}
(1690-1764), deutscher Mathematiker.} Vermutung\footnote{Die {\sc Goldbach}sche Vermutung ist
eine der ältesten offenen Fragen der Zahlentheorie und der Mathematik überhaupt: {\em Jede
gerade Zahl größer oder gleich 4 ist als Summe zweier Primzahlen darstellbar.} Die {\sc
Goldbach}sche Vermutung ist bisher weder bewiesen noch widerlegt worden. Die meisten
Mathematiker halten die Vermutung aus statistischen Gründen für wahr.} falsch ist. Könnte man
nun beweisen oder wiederlegen, daß diese Maschine bei Eingabe ihrer eigenen Nummer anhält,
hätte man damit einen Gegenbeweis oder Beweis der {\sc Goldbach}schen Vermutung. Es ist also
nicht in jedem Falle möglich zu entscheiden, ob eine natürliche Zahl zur Menge $\rree$
gehört.

Wichtig soll hier erst einmal nur sein, daß man für bestimmte {\sc Turing}-Maschinen beweisen
kann, daß sie bei Eingabe ihrer eigenen Nummer nicht anhalten. Wir können also für bestimmte
natürliche Zahlen zeigen, daß sie zur Menge $\overline{K}$ gehören. Wir wollen versuchen, all
diese Zahlen in einer Menge zusammenzufassen.

Zunächst wollen wir definieren, was wir unter der Beweisbarkeit von mathematischen Aussagen
verstehen wollen.

Sei $\mathbb{A}$ die Menge der mathematischen Aussagen\footnote{Die Menge der mathematischen
Aussagen ist natürlich nicht hinreichend definiert. Wichtig ist in diesem Zusammenhang jedoch
nur, daß jede dieser mathematischen Aussagen einen Wahrheitswert (wahr oder falsch) hat, auch
wenn wir diesen Wahrheitswert unter Umständen nicht kennen.}. Wir führen nun folgende
Funktion $\bw:\mathbb{A}\to\{wahr,falsch\}$ ein:

\defi{menschliche Beweise\label{beweis}}
{\[ \bw(A):=\left\{ \begin{array}{lll}

    \mbox{wahr},
    & \mbox{$A$ ist wahr und menschliche Mathematiker sind}\\
    & \mbox{prinzipiell in der Lage, dies zu beweisen}\\

    \mbox{falsch},  & \mbox{sonst.}
  \end{array}\right. \]}

\par\medskip

Die Beschränkung auf menschliche {\em Mathematiker} ist nicht als echte Beschränkung zu
verstehen, ebensogut sind Beweise von Nicht-Mathematikern zugelassen, die prinzipiell von
Mathematikern verstanden werden können.

Die Formulierung "`...menschliche Mathematiker sind {\em prinzipiell} in der Lage, ..."' soll
bedeuten, daß ein korrekter (menschlicher) Beweis existiert oder nach endlicher Zeit gefunden
wird.

Man kann sich $\bw(A)$ einfach vorstellen als:\\
{\it "`Es existiert ein Beweis für $A$, der durch korrektes menschliches Schlußfolgern
gefunden werden kann."'}

Sicher ist die Definition keine mathematische Definition im strengen Sinne. Wir wollen für
die weiteren Betrachtungen aber davon ausgehen, daß sie in dieser Form sinnvoll ist, d.h.
eine exakte Definition für eine bestimmte Funktion\\
$\bw:\mathbb{A}\to\{wahr,falsch\}$ liefert, die mathematischen Aussagen den Wert "`wahr"'
oder "`falsch"' zuordnet, je nachdem, ob die entsprechende Aussage von menschlichen
Mathematikern prinzipiell bewiesen werden kann oder nicht.\footnote{Wenn man die prinzipielle
Existenz korrekter mathematischer Beweise nicht in Frage stellt, wird man sicher auch nicht
an der Korrektheit der Definition zweifeln. Im Grunde werden alle wahren Aussagen $A$, zu
denen ein korrekter mathematischer Beweis existiert oder in der Zukunft gefunden wird,
aufgesammelt und es gilt dann $\bw(A)=\mbox{wahr}$.}

\newpage

Es bleibt zu erwähnen, daß der Wahrheitswert $\bw(A)$ von mathematischen Aussagen $A$ zwar
immer existiert, aber nicht in jedem Fall von menschlichen Mathematikern angegeben werden
kann.

Falls die Aussage $A$ falsch ist, gilt natürlich $\bw(A)=\mbox{falsch}$, falls es einen {\em
menschlichen} Beweis für $A$ gibt, gilt $\bw(A)=\mbox{wahr}$. In anderen Fällen ist der
Wahrheitswert von $\bw(A)$ unter Umständen unbekannt\footnote{{\sc Kurt Gödel} bewies im
sogenannten {\sc Gödel}schen Unvollständigkeitssatz: In jeder denkbaren Theorie der
natürlichen Zahlen bleiben wahre arithmetische Aussagen übrig, für die man weder beweisen
kann, ob sie wahr sind, noch, ob sie falsch sind. Durch diesen erstaunlichen Satz ist der
Mathematik eine prinzipielle Grenze gesetzt: Nicht für jedes mathematische Problem gibt es
auch eine mathematische Lösung!}\label{goedelfussnote}. Zum Beispiel könnte die oben
beschriebene {\sc Goldbach}sche Vermutung wahr sein, aber wir können es nicht beweisen.

\par\bigskip

Zwei einfache Schlußfolgerungen aus der Definition sind:

\par\medskip

\noindent
$\bw(A) \Rightarrow A$\hfill$(1)$\label{eins}\\
$[\bw(A) \wedge \bw(A \Rightarrow B)] \Rightarrow \bw(B)$\hfill$(2)$\label{zwei}

\par\medskip

In der Aussage $(1)$ verstehen wir $A$ als "`Die Aussage $A$ ist wahr."' Damit gilt die
Aussage $(1)$ trivial, weil eine Aussage natürlich wahr sein muß, wenn ein Beweis für sie
existiert.

Die Aussage $(2)$ gilt, weil man an den Beweis für $A$ einfach den Beweis für $A \Rightarrow
B$ anhängen kann und somit einen Beweis für $B$ erhält.

Wir definieren eine Menge, die uns im weiteren ständig beschäftigen wird:

\defi{\boldmath$D$\unboldmath}
{$D:=\{n\in{\nn}:\bw(M_n(n)=\bot)\}$\label{dee}}

\begin{quote}
In {\sc Roger Penrose}'s Buch "`Schatten des Geistes"' \cite{sg} wird diese Menge in
ähnlicher Form definiert. Dort heißt es:

"`($\ldots$) Nehmen wir also an, wir hätten ein Rechenverfahren $A$, das uns dann, wenn es
erfolgreich zum Ende kommt, beweist, daß eine Berechnung wie $C(n)$ in der Tat niemals
aufhört. Wir versuchen uns vorzustellen, daß $A$ alle Verfahren enthält, mit deren Hilfe
menschliche Mathematiker überzeugend beweisen können, daß Berechnungen nicht anhalten. Wenn
$A$ in einem bestimmten Fall je zu einem Ende kommt, hätten wir also einen Beweis dafür, daß
diejenige Berechung, auf die $A$ sich bezieht, niemals anhält. ($\ldots$)"'

Dabei ist mit $C(n)$ nicht die Berechnung $M_n(n)$ gemeint, sondern noch etwas allgemeiner
irgendeine Berechnung $C$ mit Eingabe $n$. Alle Berechnungen $C$ werden später durchnumeriert
und entsprechen dann (mit einer etwas anderen Codierung) den {\sc Turing}-Maschinen $M_i$,
die in dieser Arbeit betrachtet werden.

Penrose schreibt weiter:

"`($\ldots$) Das Verfahren $A$ kann man sich jetzt als eine Berechnung vorstellen, die dann,
wenn ihr das Zahlenpaar $q,n$ vorgelegt wird, versucht zu zeigen, daß die Berechnung $C_q(n)$
niemals aufhören wird. Wenn die Berechnung $A$ also {\em aufhört}, ist damit bewiesen, daß
$C_q(n)$ {\em nicht anhält}. Für unsere Zwecke werden wir uns in Kürze vorzustellen
versuchen, daß $A$ eine Formalisierung {\em aller} Verfahren ist, mit denen menschliche
Mathematiker gültig zu entscheiden vermögen, daß Berechnungen niemals aufhören. ($\ldots$)
Die Berechnung, die $A$ durchführt, läßt sich, da sie von den beiden Zahlen $q$ und $n$
abhängt, als $A(q,n)$ schreiben, und wir haben:

Wenn $A(q,n)$ anhält, hält $C_q(n)$ nicht an.

Betrachten wir jetzt speziell die Aussagen, für die $q$ gleich $n$ gesetzt wird. ($\ldots$)"'

Das Rechenverfahren $A$ kann dann als die oben definierte Menge $D$ verstanden werden, wenn
man den Definitionsbereich von $A$ betrachtet und zusätzlich nur diejenigen Berechnungen
betrachtet, in denen $n=q$ gilt.

\end{quote}

Trivial gilt die Inklusionsbeziehung

$D \subseteq \overline{K}$,

wobei $\overline{K}$ die in Definition \ref{kaa} (Seite \pageref{kaa}) definierte Menge ist.
Wegen der Eigenschaft ($1$) auf Seite \pageref{eins} muß jedes Element von $D$ auch Element
von $\overline{K}$ sein.

\par\medskip

Diese Menge ist, etwas locker formuliert, in einem {\em menschlichen} Sinne aufzählbar. Das
soll bedeuten:

Für alle $n\in D$ wird die Tatsache "`$n$ gehört zur Menge $D$"' nach endlicher Zeit von
menschlichen Mathematikern festgestellt (bewiesen) werden.

Begründung:\\ Denn für alle $n\in D$ gilt (nach Definition \ref{beweis}): Menschliche
Mathematiker sind prinzipiell in der Lage, $n\in \overline{K}$ zu beweisen. Das heißt, ein
Beweis für $n\in \overline{K}$ existiert bereits oder wird nach endlicher Zeit gefunden.

Für gewisse $n\notin D$ kann auch die Tatsache "`n gehört nicht zur Menge $D$"' nach
endlicher Zeit festgestellt werden. Wenn die Berechnung $M_n(n)$ anhält, gilt natürlich
$n\notin D$. Dies kann in endlicher Zeit bewiesen werden, indem man einfach die Berechnung
$M_n(n)$ ablaufen läßt.

Übrig bleiben die Fälle, in denen menschliche Mathematiker nach endlicher Zeit keinen Beweis
für $n\in \overline{K}$ finden können, die Berechnung $M_n(n)$ aber auch nicht anhält.

\section{Aufzählbarkeit von $D$}

Im Satz \ref{halteproblem} (Seite \pageref{halteproblem}) wurde $\overline{K}\notin\rree$
gezeigt. Wenn man nun $D\notin\rree$ zeigen könnte, hätte man eine Leistung des menschliches
Denkens gefunden, die von keiner {\sc Turing}-Maschine nachvollzogen werden kann. Dabei
beziehen wir uns auf die oben erwähnte Eigenschaft, die Menge $D$ sei {\em menschlich}
aufzählbar, während $D\notin\rree$ bedeuten würde, daß $D$ nicht {\sc Turing}-aufzählbar ist.
Wir werden später sehen, daß die doch recht lockere Interpretation durchaus echten
wissenschaftlichen Gehalt hat.

Leider kann $D\notin\rree$ nicht in dieser allgemeinen Form bewiesen werden\footnote{Ein
zunächst vielversprechender, aber erfolgloser Versuch, $D\notin\rree$ zu beweisen, wird im
Versuch eines Satzes \ref{scharf} (Seite \pageref{scharf}) besprochen.}, allerdings führt ein
etwas schwächerer Ansatz zu folgendem Satz:

\stz{Aufzählbarkeit von \boldmath$D$\unboldmath?\label{AufzD}} {Für kein $k \in {\nn}$ gilt
$\bw(D_k=D)$\footnote{Die Behauptung des Satzes kann wie folgt umformuliert werden:\\$\{
k\in{\nn}:\bw(D_k=D) \} = \emptyset$}}{(indirekt)

Zunächst eine kurze, aber durchaus wichtige Vorbemerkung:

Hierbei ergibt die Aussage $\bw(D_k=D)$ natürlich nur einen Sinn, wenn uns (d.h. uns als
menschlichen Mathematikern) die Zahl $k \in {\nn}$ direkt bekannt ist, also gewissermaßen
eine spezielle natürliche Zahl ist.

Es ist in der Tat so, daß

$\bw(D_k=D)$

eine wesentlich stärkere Aussage als

$\bw(\exists k \in {\nn} (D_k=D))$

darstellt. Die Aussage $\bw(\exists k \in {\nn} (D_k=D))$ würde bedeuten, daß wir einen
Beweis dafür haben, daß eine {\em beliebige} (uns unter Umständen völlig unbekannte) Zahl die
Aussage $D_k=D$ erfüllt.

Die Zahl $k$ aus der Behauptung des Satzes steht also tatsächlich nur als Platzhalter für die
(unendlich vielen) verschiedenen Sätze\\
$\bw(D_0=D)=falsch$,\\
$\bw(D_1=D)=falsch$,\\
$\bw(D_2=D)=falsch$,\\
$\vdots$

\par\bigskip

Nehmen wir also an, es gelte $\bw(D_k=D)$ für ein spezielles $k$. Damit gilt:

$\bw( \forall n \in {\nn} (n \in D_k \Leftrightarrow n \in D))$.

Wir setzen $n=k$, damit gilt

$\bw( k \in D_k \Leftrightarrow k \in D)$.

Weil $k \in D_k$ äquivalent zu $M_k(k)\neq\bot$ ist, folgt:

(a) $\bw( M_k(k)\neq\bot \Leftrightarrow k \in D )$

Weil außerdem $k \in D$ äquivalent zu $\bw (M_k(k)=\bot)$ gilt:

(b) $\bw( M_k(k)\neq\bot \Leftrightarrow \bw (M_k(k)=\bot) )$

Aus (a) folgt (unter Verwendung von Schlußfolgerung (1), Seite \pageref{eins})

$M_k(k)\neq\bot \Leftrightarrow k \in D$\hfill$(*)$

Aus (b) folgt (ebenfalls unter Verwendung von Schlußfolgerung (1), Seite \pageref{eins})

$\bw( M_k(k)\neq\bot \Rightarrow M_k(k)=\bot )$

und damit

$\bw( M_k(k)=\bot )$\footnote{Dies folgt aus der einfachen logischen Tautologie $(A
\Rightarrow \neg A) \Rightarrow \neg A$.}.

Hieraus lassen sich zwei Aussagen ableiten:

(c) (mit der Definition von $D$): $k \in D$,

(d) (mit Schlußfolgerung (1), Seite \pageref{eins}): $M_k(k)=\bot$\hfill$(**)$

Aus (c) und (*) folgt $M_k(k)\neq\bot$, im Widerspruch zu (**).

Damit ist der Satz bewiesen.}

\begin{quote}
In {\sc Roger Penrose}'s Buch \cite{sg} wird dieser Beweis in einer ganz ähnlichen Form
geführt. Dabei muß allerdings angemerkt werden, daß der {\sc Penrose}sche Beweis in einer
sehr prosaischen Form dargeboten wird und zudem einer wohlwollenden Auslegung bedarf, da
verschiedene wichtige Beweisbestandteile nicht explizit erwähnt worden sind. So wird zum
Beipiel in der oben aufgeführten "`Definition"' des Verfahrens $A_q(n)$ davon ausgegangen,
daß uns menschlichen Mathematikern die Nummer eines solchen Verfahrens (nachdem $q$ gleich
$n$ gesetzt wurde) direkt vorliegt. Außerdem verlangt {\sc Penrose} von seinem
Rechenverfahren nicht nur die Eigenschaft:

"`Wenn $A(q,n)$ anhält, so hält $C_q(n)$ nicht an"',

sondern in der Interpretation des Prosaischen "`Beweises"' auch deren Umkehrung

"`Wenn $C_q(n)$ nicht anhält, so hält $A(q,n)$ an"',

obwohl dies an keiner einzigen Stelle vorher erwähnt worden ist.

So gelangt {\sc Penrose} schließlich zu folgendem Schluß:

"`($\ldots$) Wenn wir $A$ und seine Korrektheit kennen, läßt sich eine Berechnung $C_k(k)$
konstruieren, von der wir sehen können, daß sie niemals aufhört; deshalb kann $A$ keine
Formalisierung der Beweisverfahren sein, die Mathematikern zur Verfügung stehen, um
\hspace{0.1cm}--- unabhängig von der Beschaffenheit von $A$ ---\hspace{0.1cm} zu beweisen,
daß Berechnungen nicht aufhören. Es gilt also:

Menschliche Mathematiker verwenden zum Nachweis mathematischer Wahrheit keinen nachweislich
korrekten Algorithmus. ($\ldots$)"'

Dabei ist mit der Korrektheit von $A$ die Eigenschaft von $A$ gemeint, daß, wenn $A(q,n)$
anhält, damit ein Beweis für "`$C_q(n)$ hält nicht an."' vorliegt. Außerdem steckt in dem
kleinen Wort "`nachweislich"' bei {\sc Penrose} nicht nur die Eigenschaft, daß die
Korrektheit von $A$ bewiesen worden ist, sondern auch die genaue Kenntnis der Nummer eines
solchen Verfahrens (also Algorithmus) $A$.

\end{quote}

Alles in allem stellt der obige Satz \ref{AufzD} eine ziemlich genaue, aber mathematisch
wesentlich strengere Formulierung der {\sc Penrose}schen Gedanken dar.

Die Ausführungen von {\sc Penrose} in der Version seines Buches \cite{sg} würden einer
strengen mathematischen Prüfung nicht standhalten.

\newpage

\section{Was haben wir erreicht?}\label{erreichtes}

Versuchen wir uns klarzumachen, was wir überhaupt bewiesen haben.

Wir haben zunächst die Menge $D$ definiert. Diese Menge beschreibt {\em menschliche}
Fähigkeiten, gewisse mathematische Beweise (diese Beweise betreffen {\sc Turing}-Maschinen)
zu führen. Sie soll in einem gewissen Sinne {\em menschlich} aufzählbar verstanden werden.

Dann haben wir \hspace{0cm} $\{ k\in{\nn}:\bw(D_k=D) \} = \emptyset$ \hspace{0cm} bewiesen,
d.h. daß für kein spezielles $k \in {\nn}$ die Aussage

$\bw(D_k=D)$

gilt. Ein Beweis für \hspace{0cm} $D_k=D$ \hspace{0cm} kann von menschlichen Mathematikern
für kein spezielles $k \in {\nn}$ geführt werden.

Dafür kann es mehrere Gründe geben:

\par\medskip

(1)\\
Das kann zum Beispiel daran liegen, daß ganz allgemein $D \notin \rree$ gilt.\\
Das würde bedeuten, es gibt tatsächlich keine Maschine, die $D$ aufzählt. Die Behauptung von
Satz \ref{AufzD} gilt dann trivial: Man kann $D_k=D$ natürlich für kein $k \in {\nn}$ zeigen,
denn dann würde ja $D \in \rree$ gelten.

Menschliche Beweise für $M_k(k)=\bot$ wären dann nicht komplett von Computern
nachvollziehbar. Der Glaube an diese Variante läßt vermuten, daß man geneigt ist, die
mensch\-li\-chen Denk\-fä\-hig\-kei\-ten grundsätzlichen über die (Denk-)Fähig\-kei\-ten von
Maschinen zu stellen.

\par\medskip

(2)\\
Im Gegensatz dazu kann aber durchaus $D \in \rree$ gelten.\\
Es gibt dann eine Maschine $M_k$, die $D$ aufzählt, nur sind menschliche Mathematiker nach
obigem Beweis nicht imstande, für dieses $k \in {\nn}$ einen Beweis für $D_k=D$ anzugeben.

Im Grunde läßt sich diese Tatsache auch mit gesundem Menschenverstand gut vereinbaren. Hätten
wir einen Beweis, daß eine ganz bestimmte {\em (uns bekannte)} natürliche Zahl $k$ die
Eigenschaft $D_k=D$ erfüllt, dann hätten wir eine exakte mathematische Beschreibung der Menge
$D$ gefunden. Dies ist wirklich schwer vorstellbar, da wir dann eine exakte mathematische
Beschreibung der {\em prinzipiellen} menschlichen Fähigkeit haben, gewisse mathematische
Beweise zu führen. Wir hätten also die Möglichkeit, alle natürlichen Zahlen $k$ gewissermaßen
im Voraus zu kennen, zu denen irgendwann menschlichen Beweise für $M_k(k)=\bot$ gefunden
werden.
\par\medskip

Welche der beiden Varianten (1) oder (2) man favorisiert, bleibt natürlich jedem selbst
überlassen.

\section{Ein wenig Philosophie}\label{philo}

Auf weitere interessante Tatsachen soll hier noch einmal speziell hingewiesen werden:

\par\medskip

(a)\\
$D \in \rree$ bedeutet nicht sofort, daß wir eines Tages mit {\em menschlich denkenden}
Maschinen konkurrieren müssen.

Zum einen zeigt Satz \ref{AufzD}, daß Menschen grundsätzlich nicht in der Lage sind, ein $k
\in {\nn}$ und einen Beweis für $D_k=D$ anzugeben. Wir könnten die entsprechende Maschine
$M_k$ also nur {\em sozusagen zufällig} finden, ohne einen Beweis für $D_k=D$ zu haben.

Zum anderen bedeutet selbst das Vorhandensein der entsprechenden Maschine $M_k$ mit $D_k=D$
nicht automatisch, daß diese Maschine unser menschliches Denken perfekt simulieren kann. Wir
haben uns ja bisher nur auf einen sehr kleinen Teil unserer menschlichen Denkfähigkeiten
beschränkt, nämlich auf die Fähigkeit, Beweise für ganz bestimmte mathematische Sachverhalte
anzugeben. Alle anderen menschlichen Denkleistungen bleiben von diesen Überlegungen
unberührt.

Allein die Versuche, die menschliche Fähigkeit zur sprachlichen Äußerung (und seien es auch
nur sprachliche Äußerungen in schriftlicher Form) mit Computern nachzuvollziehen, sind bisher
von sehr geringem Erfolg gekennzeichnet. Es gibt sehr gute Algorithmen der Spracherkennung,
wenn es darum geht, aus einem akustischen Signal die entsprechenden Wörter zu erkennen, es
gibt auch ganz brauchbare Algorithmen, um diesen Sequenzen eine grammatische Struktur
zuzuordnen. Aber aus diesen Strukturen dann die logisch transparente Bedeutungsrepräsentation
abzuleiten, ist bisher kaum gelungen; ganz zu schweigen von verschiedenen anderen
kommunikativen und sozialen {\em menschlichen} Fähigkeiten.

\par\medskip

(b)\\
Im Gegensatz dazu schließt $D \notin \rree$ natürlich nicht aus, daß es eines Tages Maschinen
gibt, die menschliches Denken nahezu perfekt simulieren können.

Die Tatsache, daß menschliche Mathematiker unter Kenntnis der Nummer $k$ der Maschine und mit
Hilfe des Beweises für $D_k=D$ eine ganz bestimmte mathematische Aussage beweisen können
(nämlich $\bw(M_k(k)=\bot)$), die die Maschine nicht nachvollziehen kann, stellt eine {\em
zutiefst theoretische} Aussage dar. Sie gibt kaum Auskunft darüber, in welcher Art und Weise
mögliche zukünftige Maschinen menschliches Denken simulieren könnten.

\par\medskip

(c)\\
Die weiter oben erwähnte lockere Formulierung "`Die Menge $D$ ist {\em menschlich}
aufzählbar"', während die Menge $D$ nur dann {\em im klassischen Sinne} aufzählbar ist, wenn
menschliche Mathematiker für kein $k \in{\nn}$ die Eigenschaft $D_k=D$ beweisen können,
findet im Beweis von Satz \ref{AufzD} eine stärkere, eher {\em wissenschaftliche} Bedeutung.

Falls nämlich $\bw(D_k=D)$ für ein spezielles $k \in {\nn}$ gilt, so folgt mit Hilfe des
Beweises $\bw(M_k(k)=\bot)$. Wir {\em (d.h. wir Menschen)} hätten dann also einen Beweis für
$M_k(k)=\bot$; während, wie der weitere Verlauf des Beweises zeigt, die Maschine $M_k$ diesen
Beweis nicht führen kann. Wir sind also in Bezug auf die Aufzählbarkeit der Menge $D$ jeder
Maschine $M_k$ überlegen, deren Nummer $k$ wir kennen. In abgeschwächter Form könnte man also
folgende Interpretation wagen:

{\bf Menschliches Denken ist nicht durch von Menschen gebaute Maschinen berechenbar.}

{\em (Denn wir können die Nummer jeder von Menschen gebauten Maschine angeben.)}

\par\medskip

(d)\\
Der Satz \ref{AufzD} behauptet nicht, daß ganz allgemein niemals $D \notin \rree$ oder $D \in
\rree$ gezeigt werden kann.

Wie oben bereits formuliert, kann natürlich $D \notin \rree$ gelten, und auch ein {\em
menschlicher} Beweis dafür ist nicht auszuschließen.

Ebenso könnte auch für $D \in \rree$ ein Beweis gefunden werden! Es ist allerdings unmöglich,
daß dieser Beweis die Möglichkeit beinhaltet, konstruktiv eines der $k \in {\nn}$ anzugeben,
für das $D_k=D$ gilt.

{\em Populärwissenschaftlich formuliert:\\
Die Maschine $M_k$, die $D$ aufzählt (das heißt $D_k=D$), könnte vor uns stehen, aber wir
wissen es nicht oder können es nicht beweisen.}

\par\medskip

(e)\\
Wir sprechen hier nach wie vor natürlich nur von Computerprogrammen, die {\sc
Turing}-berechenbare Funktionen berechnen. Dies schließt nicht aus, daß eines Tages ein
Computer entwickelt wird, der in seinen Fähigkeiten über die einer {\sc Turing}-Maschine
hinausgeht. Für solche Computer sind die obigen Über\-le\-gungen unter Um\-stän\-den nicht
mehr anwendbar.

Eine solche Entwicklung ist im Moment allerdings noch nicht abzusehen.

\newpage

\section{Der Versuch eines schärferen Beweises}

Wenn man sich den Satz \ref{AufzD} (Seite \pageref{AufzD}) und den dazugehörigen Beweis genau
anschaut, könnte man auch den nun folgenden Versuch eines schärferen Beweises wagen. Wir
wollen zeigen, an welcher Stelle der schärfere Beweis scheitert:

\fstz{

$D \notin \rree$\label{scharf}}{(indirekt)

Nehmen wir also an, es gelte $D \in \rree$.

Dann existiert ein $k \in {\nn}$ derart, daß für alle $n \in {\nn}$

$M_k(n)\neq\bot \Leftrightarrow n \in D$\hfill$(*)$

gilt. Mit $n=k$ gilt

$M_k(k)\neq\bot \Leftrightarrow k \in D$

Nach der Definition für $D$ gilt weiter: $k \in D \Rightarrow M_k(k)=\bot$, also:

$M_k(k)\neq\bot \Rightarrow M_k(k)=\bot$, woraus

$M_k(k)=\bot$\hfill$(**)$

folgt\footnote{Dies folgt wieder aus $(A \Rightarrow \neg A) \Rightarrow \neg A$.}.

Da diese Tatsache soeben durch menschliche Mathematiker (wir selbst und der verstehende
Leser) herausgefunden wurde, liegt also offensichtlich ein Beweis für $M_k(k)=\bot$ vor, also
gilt $\bw(M_k(k)=\bot)$, und damit

$k \in D$\hfill$(F)$

Mit $(*)$ folgt $M_k(k)\neq\bot$, im Widerspruch zu $(**)$.}

\par\medskip

Es ist in der Tat nicht einfach, den Fehler im Beweis zu finden. Er findet sich in der
Begründung, mit deren Hilfe der Schritt von $(*)$ nach $(F)$ vollzogen wird.

Üblicherweise werden in Beweisen gewisse Beweisschritte verkürzend formuliert, um die
Übersichtlichkeit zu erhöhen. In diesem Fall führt uns echte mathematische Exaktheit den
Fehler im Beweis vor Augen. Exakt betrachtet wurde bis zum Schritt $(**)$ Folgendes gezeigt:

$D \in \rree \Rightarrow \exists k \in {\nn} (M_k(k)=\bot)$\hfill$(**')$

Wenn wir nun daraus

$D \in \rree \Rightarrow \exists k \in {\nn} (\bw(M_k(k)=\bot))$\hfill$(F')$

folgern könnten, hätten wir

$D \in \rree \Rightarrow \exists k \in {\nn} (k \in D)$

und mit $(*)$\footnote{Exakt betrachtet steht $(*)$ für die Aussage:\\
$D \in \rree \Rightarrow \exists k \in {\nn}$ $\forall n \in {\nn}$ $(M_k(n)\neq\bot
\Leftrightarrow
n \in D)$, daraus folgt dann:\\
$D \in \rree \Rightarrow \exists k \in {\nn}$ $(M_k(k)\neq\bot \Leftrightarrow k \in D)$}
auch

$D \in \rree \Rightarrow M_k(k)\neq\bot$.

Zusammen mit $(**')$ würde dann wie gewünscht $D \notin \rree$ folgen.

\par\medskip

Von $(**')$ nach $(F')$ tritt nun folgender Fehler auf:

Es ist schlicht falsch, daß uns im Beweisschritt $(**')$ die Tatsache

$\exists k \in {\nn} (M_k(k)=\bot)$

direkt vorliegt. Wir wissen nur, daß dies aus unserer Annahme $D \in \rree$ folgen würde. Um
nun $(F')$ zu folgern\footnote{Dies ist die schwächste Aussage, die uns zum Ziel führt.},
müßte man mindestens

$\exists k \in {\nn} (M_k(k)=\bot) \Rightarrow \exists k \in {\nn} (\bw(M_k(k)=\bot))$

zeigen.

\par\medskip

Diese Tatsache ist nicht schwer zu verifizieren. Führen wir hierzu vereinfachende
Bezeichnungen ein:

$A$ \hspace{0.5cm} sei die Aussage \hspace{0.5cm} $D \in \rree$,

$B$ \hspace{0.5cm} sei die Aussage \hspace{0.5cm} $\exists k \in {\nn} (M_k(k)=\bot)$,

$C$ \hspace{0.5cm} sei die Aussage \hspace{0.5cm} $\exists k \in {\nn} (\bw(M_k(k)=\bot))$.

Wir wissen $A \Rightarrow B$ und wollen $A \Rightarrow C$ schlußfolgern. Das ist
gleichbedeutend mit einem Beweis für $(A \Rightarrow B) \Rightarrow (A \Rightarrow C)$.
Dieser Term kann wie folgt umgeformt werden:

$(A \Rightarrow B) \Rightarrow (A \Rightarrow C)$

$\Leftrightarrow$\hspace{1cm}$\neg(\neg A \vee B) \vee (\neg A \vee C)$

$\Leftrightarrow$\hspace{1cm}$(A \wedge \neg B) \vee \neg A \vee C$

$\Leftrightarrow$\hspace{1cm}$(A \vee \neg A) \wedge (\neg B \vee \neg A) \vee C$

$\Leftrightarrow$\hspace{1cm}$\neg B \vee \neg A \vee C$

$\Leftrightarrow$\hspace{1cm}$\neg A \vee (B \Rightarrow C)$

$\Leftrightarrow$\hspace{1cm}$A \Rightarrow (B \Rightarrow C)$

Ohne an dieser Stelle einen Beweis für die Aussage $B \Rightarrow C$ (also $\exists k \in
{\nn} (M_k(k)=\bot) \Rightarrow \exists k \in {\nn} (\bw(M_k(k)=\bot))$) anzugeben, kann der
Beweisschritt $(F')$ also nicht vollzogen werden, da über den Wahrheitswert der Aussage $A$
(also $D \in \rree$) an dieser Stelle nichts ausgesagt werden kann.

\par\medskip

Natürlich ist es unmöglich, aus

$B$\hspace{1cm}$\Leftrightarrow$\hspace{1cm}$\exists k \in {\nn} (M_k(k)=\bot)$

den Schluß

$C$\hspace{1cm}$\Leftrightarrow$\hspace{1cm}$\exists k \in {\nn}(\bw(M_k(k)=\bot))$

zu ziehen.

Hierzu sollte man sich klarmachen, was die verschiedenen Aussagen eigentlich exakt bedeuten.

$\exists k \in {\nn} (M_k(k)=\bot)$ bedeutet:\\
Es gibt ein (uns unter Umständen völlig unbekanntes) $k \in {\nn}$, welches die Aussage
$M_k(k)=\bot$ erfüllt. Man kann die Aussage auch wie folgt umformulieren:

$\exists k \in {\nn} (M_k(k)=\bot)$\hspace{1cm}$\Leftrightarrow$\hspace{1cm}$\overline{K}
\neq \emptyset$

Dabei ist $\overline{K}$ die in Definition \ref{kaa} (Seite \pageref{kaa}) eingeführte Menge,
die das Halteproblem beschreibt.

\par\medskip

$\exists k \in {\nn}(\bw(M_k(k)=\bot))$ bedeutet:\\
Es gibt ein $k \in {\nn}$, welches die Aussage $\bw(M_k(k)=\bot)$ erfüllt. Wie bereits weiter
oben beschrieben, impliziert die Formulierung $\bw(M_k(k)=\bot)$, daß wir das spezielle $k
\in {\nn}$, für das $M_k(k)=\bot$ gilt, auch tatsächlich direkt kennen.

Es genügt also nicht, von der prinzipiellen Existenz eines $k \in {\nn}$ mit $M_k(k)=\bot$ zu
wissen, um den Beweis von $M_k(k)=\bot$ für ein spezielles {\em (sozusagen vorgegebenes)} $k
\in {\nn}$ zu führen. Stellen wir uns dazu vor, jemand legt uns eine bestimmte natürliche
Zahl $n$ vor, mit der Aufgabe, $M_n(n)=\bot$ zu entscheiden. Das Wissen um irgendeine (uns
natürlich völlig unbekannte) Zahl $k\in{\nn}$ mit $M_k(k)=\bot$ trägt zu der Entscheidung von
$M_n(n)=\bot$ überhaupt nicht bei. Mit Hilfe dieses Wissens kann also kein Beweis für
$M_n(n)=\bot$ gefunden werden. Dies gilt für jede beliebige natürliche Zahl $n$. Für {\em
keine} einzige natürliche Zahl $n$ kann ein Beweis für $M_k(k)=\bot$ auf diese Art und Weise
gefunden werden.

\par\medskip

Ein weiterer Aspekt der fehlerhaften Beweisführung besteht in folgendem:

Aus

$D \in \rree \Rightarrow \exists k \in {\nn} (M_k(k)=\bot)$\hfill$(**')$

kann noch nicht einmal die Aussage

$D \in \rree \Rightarrow \bw(\exists k \in {\nn} (M_k(k)=\bot))$\hfill$(f)$

hergeleitet werden.

\newpage

Wie oben bereits angedeutet, wurde die Aussage $\exists k \in {\nn} (M_k(k)=\bot)$ nicht
bewiesen. Wir wissen nur, daß sie aus der Aussage $D \in \rree$ folgt. Man kann für $(**')$
auch schreiben:

$(D \notin \rree) \vee (\exists k \in {\nn} (M_k(k)=\bot))$

Da der Wahrheitswert von $D \notin \rree$ (die Behauptung des Satzes) an dieser Stelle
natürlich nicht bekannt ist, kann auch über den Wahrheitswert von $\exists k \in {\nn}
(M_k(k)=\bot)$ nichts ausgesagt werden. Es liegt also nach wie vor kein Beweis der Aussage
$\exists k \in {\nn} (M_k(k)=\bot)$ vor, damit kann auch nicht $\bw(\exists k \in {\nn}
(M_k(k)=\bot))$ geschlußfolgert werden.

Die Aussage $(f)$ ist schwächer als die benötigte Aussage

$D \in \rree \Rightarrow \exists k \in {\nn} (\bw(M_k(k)=\bot))$\hfill$(F')$

und würde im weiteren Verlauf des Beweises auch nicht zum Ziel führen. Trotzdem zeigt dies
eine weiteren Fehler des Beweises. Im nächsten Abschnitt soll noch einmal auf einfache Art
gezeigt werden, welche Folgen Beweise hätten, die diesen fehlerhaften Beweisschritt
verwenden.



\section{Ein weiterer Beweisversuch}

Es wird nun ein Beweis angegeben, der das gleiche Beweisprinzip wie Satz \ref{scharf} (Seite
\pageref{scharf}) verwendet, aber eine eindeutig falsche Aussage beweist:

\par\medskip

\fstz{

\label{falsch}Für jede beliebige mathematische Aussage $A$ gilt:

$\bw(A) \vee \bw(\neg A)$}{Für den Beweis der Aussage beweisen wir für beliebige Aussagen $A$
die Hilfsaussage $(*)$:

$(*)$\hspace{2cm}$A \vee \bw(\neg A)$

Beweis: (indirekt)\\
Annahme: $\neg A \wedge \neg \bw(\neg A)$

$\Rightarrow$\hspace{1cm}$\neg A$\hfill$(1)$

$\Rightarrow$\hspace{1cm}$\neg \bw(\neg A)$\hfill$(2)$

Da die Tatsache $(1)$ soeben durch menschliche Mathematiker (wir selbst und der verstehende
Leser) herausgefunden wurde, liegt also offensichtlich ein Beweis für $\neg A$
vor\footnote{Hier wird bewußt der gleiche Wortlaut wie im oben aufgeführten Beweis für Satz
\ref{scharf} (Seite \pageref{scharf}) verwendet.}, damit gilt $\bw(\neg A)$, im Widerspruch
zu $(2)$.\hfill$\Box$

Da $(*)$ für beliebige Aussagen $A$ bewiesen wurde, gilt außerdem (für $\neg A$):

$(**)$\hspace{1cm}$\neg A \vee \bw(A)$.

Jede mathematische Aussage $A$ hat einen eindeutigen Wahrheitswert, damit entstehen hier also
2 Fälle:

1.\hspace{0.5cm}$A = \mbox{wahr}$

mit $(**)$ folgt $\bw(A)$.

2.\hspace{0.5cm}$A = \mbox{falsch}$

mit $(*)$ folgt $\bw(\neg A)$.

Daraus folgt die Behauptung $\bw(A) \vee \bw(\neg A)$}

Es muß wohl nicht näher erläutert werden, warum der Satz offensichtlich eine falsche Aussage
beweist\footnote{Auch hier sei noch einmal auf den bahnbrechenden Satz von {\sc Kurt Gödel}
hingewiesen, der besagt, daß es in genügend komplizierten mathematischen Systemen Aussagen
$A$ gibt, für die weder $\bw(A)$ noch $\bw(\neg A)$ gilt.}, die Auf"|lösung des Problems
liegt also im verwendeten (falschen) Beweis.

\section{Abschlußbemerkungen}

Obwohl interpretierende Aspekte der vorliegenden Arbeit schon im Abschnitt \ref{erreichtes}
(Seite \pageref{erreichtes}) und im philosophischen Abschnitt \ref{philo} (Seite
\pageref{philo}) angeschnitten wurden, soll hier noch einmal eine kurze Zusammenfassung des
Erreichten erfolgen.

Wir haben einen Teil der menschlichen Denkens, speziell die Fähigkeit zum korrekten
mathematischen Schlußfolgern in der Menge $D$ beschrieben, welche die natürlichen Zahlen $n$
enthält, für die \hspace{0cm} $\bw(M_n(n)=\bot)$ \hspace{0cm} gilt.

Es konnte erfolgreich der Satz \ref{AufzD} (Seite \pageref{AufzD}) gezeigt werden.

Dieser Satz sagt sinngemäß aus, daß kein \hspace{0cm} $i \in {\nn}$ \hspace{0cm} gefunden
werden kann, für das ein mathematisch korrekter Beweis für \hspace{0cm} $D_i=D$ \hspace{0cm}
angegeben werden kann, also daß für keine bekannte {\sc Turing}-Maschine bewiesen werden
kann, daß sie $D$ aufzählt.

Ein Beweis \ref{scharf} (Seite \pageref{scharf}) der wesentlich schärferen Behauptung
\hspace{0cm} $D \notin \rree$ \hspace{0cm} gelang nicht. Es wurden allerdings genauere
Untersuchungen von Fehlern in einem speziellen Beweisversuch dieser Behauptung vorgenommen.

\par\bigskip

Eine lohnenswerte Aufgabe für die Zukunft könnte darin bestehen, einen Beweis für
\hspace{0cm} $D \in \rree$ \hspace{0cm} oder \hspace{0cm} $D \notin \rree$ \hspace{0cm} zu
finden. Beide Möglichkeiten stehen nach wie vor offen (siehe Abschnitt \ref{philo}, Seite
\pageref{philo}), wobei nach Meinung des Autors wohl eher der Variante \hspace{0cm} $D \notin
\rree$ \hspace{0cm} in Frage kommt.

Zum Abschluß soll noch einmal {\sc Kurt Gödel} zu Wort kommen, der sich passend zum Thema der
Arbeit äußerte\footnote{Zitiert nach {\sc Hao Wang}, {\em From Mathematics to Philosophy}
(New York: Humanities Press, 1974) Seite 324. {\sc Wang} entnahm das Zitat dem
unveröffentlichten Text einer Vorlesung, die {\sc Gödel} in Providence am 26. Dezember 1951
gehalten hat.}:

\par\bigskip

"`Der menschliche Verstand ist nicht fähig, alle seine mathematischen Intuitionen zu
formulieren (oder zu mechanisieren). Gelingt es ihm, einige davon zu formulieren, so liefert
diese Tatsache neues intuitives Wissen, zum Beispiel die Konsistenz des Formalismus.

Diesen Sachverhalt könnte man die "`Unvollendbarkeit"' der Mathematik nennen.

Andererseits bleibt es auf Basis des bislang Bewiesenen möglich, daß es eine
Theorem-Beweismaschine geben könnte (die möglicherweise sogar empirisch nicht zu entdecken
ist), welche tatsächlich der mathematischen Intuition gleichwertig ist. Das kann aber nicht
bewiesen werden, ebensowenig wie bewiesen werden kann, daß diese Maschine in der
Zahlentheorie nur korrekte Sätze liefert."'

%\cleardoublepage \thispagestyle{empty} \hspace{0.5cm}

%\thispagestyle{empty} \hspace{0.5cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%---------------------------------Abkürzungen---------------------------

\newpage

\pagestyle{plain}

{\bf\Large Abkürzungen / mathematische Symbole\label{abkuerzungen}}

\par\medskip

\hspace{1cm}

\par\medskip

\hspace{1cm}

\par\medskip

\begin{description}

\item [\boldmath${\nn}$\unboldmath]  Die natürlichen Zahlen (selbstverständlich inklusive
"`Null"'):

${\nn}=\{0, 1, 2, 3, 4, 5, 6, 7, \ldots\}$

\item [\boldmath$\rree$\unboldmath]  Die Menge der aufzählbaren Mengen (siehe Definition
\ref{rree}, Seite \pageref{rree})

\item [\boldmath$\rreecc$\unboldmath]  Die Menge der entscheidbaren Mengen (siehe Definition
\ref{rreecc}, Seite \pageref{rreecc})

\item [\boldmath$\emptyset$\unboldmath]  Die leere Menge, auch $\{\}$.

\item [Alphabet]  Der Begriff wird im übertragenen Sinne für eine endliche nichtleere Mengen
benutzt. Meist bestehen Alphabete aus bestimmten Symbolen: Buchstaben, Zahlen, auch
Sonderzeichen. So ist z.B. $\{0,1,A,\_\}$ ein Alphabet, bestehend aus den vier Zeichen $0$,
$1$, $A$ und "`$\_$"'.

\item [Binärzahl] (auch Dualzahl) Natürliche Zahlen, die im Dualsystem (Zweiersystem)
dargestellt werden, bezeichnet man als Binärzahlen. Solche Zahlen bestehen lediglich aus
Nullen und Einsen und zwar mit folgender Vereinbarung:

$n=\sum_{k=0}^m z_k 2^k$

Dabei ist $z_k$ die $k$-te Ziffer der Zahlendarstellung von rechts (begonnen wird mit $0$)
nach links. Mit der zusätzlichen Vereinbarung, daß jede von Null verschiedene Binärzahl mit
einer $1$ beginnen muß, ist $m$ die Stellenanzahl der Zahl minus $1$. Die natürlichen Zahlen
stellen sich als Binärzahlen also wie folgt dar:

${\nn}=\{0, 1, 10, 11, 100, 101, 110, 111, 1000, \ldots\}$

\item [Definitionsbereich]  Der Definitionsbereich einer Funktion ist die Menge aller Werte,
für die die Funktion definiert ist, also die Menge der Urbilder bzw. die Menge der
Argumentwerte der Funktion. Für Funktionen $f : A \to B$ ist $A$ der Definitionsbereich, $B$
der Wertebereich der Funktion.

\item [deterministisch]  Eine deterministische (="`vorbestimmte"', ="`nicht zufällige"')
Maschine hat zu keinem Zeitpunkt ihres Programmablaufs irgendwelche Wahlmöglichkeiten. Bei
gleicher Eingabe gelangt sie immer über einen exakt gleichen Ablauf zum gleichen Ergebnis. Im
Gegensatz dazu kann man auch nichtdeterministische Maschinen betrachten, die an gewissen
Stellen im Programmablauf zwischen mehreren Möglichkeiten der Programmabarbeitung zufällig
wählen.

\item [eindeutig]  Eindeutige Relation:

$R \subseteq X \times Y$ ist eindeutig, wenn für beliebige $a \in X$ und $b,c \in Y$ gilt:

Aus \hspace{0.2cm}$(a,b) \in R$\hspace{0.2cm} und \hspace{0.2cm}$(a,c) \in R$\hspace{0.2cm}
folgt \hspace{0.2cm}$b=c$.

Funktionen sind eindeutige Relationen.

\item [eineindeutig]  Eineindeutige Abbildung, Funktion:

Eine Funktion $f : A \to B$ ist eineindeutig, wenn für beliebige $a,b \in A$ und $c \in B$
gilt:

Aus \hspace{0.2cm}$f(a)=c$\hspace{0.2cm} und \hspace{0.2cm}$f(b)=c$\hspace{0.2cm} folgt
\hspace{0.2cm}$a=b$.

\item [gleichmächtig]  Zwei Mengen $A$ und $B$ sind gleichmächtig, wenn ihre Mächtigkeit
übereinstimmt. Es gibt dann eine eineindeutige Funktion $f : A \to B$ von $A$ auf $B$.

\item [Input]  Eingabe

\item [Komplement]  Das Komplement einer Menge $A$, die Teilmenge einer Menge $M$ ist,
besteht aus den Elementen von $M$, die nicht zu $A$ gehören, und wird mit $\overline{A}$
bezeichnet:

$\overline{A}=M \setminus A$

\item [Mächtigkeit] (auch Kardinalität) Die Mächtigkeit einer endlichen Menge entspricht der
Anzahl der Elemente. die Mäch\-tig\-keit von ${\nn}$ ist $\aleph_0$, die Mäch\-tig\-keit von
$\rr$ ist $\aleph_1$. Die Mächtigkeit einer Menge $A$ wird mit $|A|$ bezeichnet.

\item [Output]  Ausgabe

\item [Potenzmenge]  Die Potenzmenge einer Menge $M$ ist die Menge aller Teilmengen von $M$.
Sie enthält z.B. die leere Menge $\emptyset$ und die Menge $M$ selbst. Als verkürzende
Bezeichnung ist auch $2^M$ gebräuchlich. Enthält die Menge $M$ endlich viele, sagen wir $m$,
Elemente, so gilt: $|2^M|=2^m$.

\end{description}

\newpage
\thispagestyle{empty} \hspace{0.5cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%---------------------------------Bibliographie---------------------------

\cleardoublepage

\begin{thebibliography}{4}

\bibitem{wurzel} L. Mäurer\label{biblio}, B. Schlingelhof; Berechenbarkeit des
  Denkens?\\
  \textit{Wurzel, Bd. 01/00}, 2000.

\bibitem{cd} R. Penrose; Computerdenken -- Des Kaisers neue Kleider
  oder Die Debatte um Künstliche Intelligenz, Bewußtsein und die
  Gesetze der Physik.\\
  \textit{Spektrum Heidelberg}, 1991.

\bibitem{sg} R. Penrose; Schatten des Geistes -- Wege zu einer
  neuen Physik des Bewusstseins.\\
  \textit{Spektrum Heidelberg}, 1995.

\bibitem{rucker} R. Rucker; Die Ufer der Unendlichkeit.\\
  \textit{Wolfgang Krüger Verlag}, 1989.

\bibitem{wechsung} G. Wechsung; C. Beckstein; Berechenbarkeit des
  Denkens? (Material zum Seminar).\\
  FSU Jena, 1999.


\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%---------------------------------Danksagung---------------------------

{

\newpage
\thispagestyle{empty} \hspace{0.5cm}

\cleardoublepage \Large \noindent

{\bf Danksagung\label{danke}}

\vspace*{0.5cm}

\large \noindent

Zuallererst danke ich meinem Betreuer Prof. Dr. G. Wechsung für die vielen Anregungen, die am
Ende zu diesem Ar\-beits\-the\-ma ge\-führt haben. Ohne ihn hätte diese Arbeit nicht
stattgefunden.

Weiterhin gilt mein Dank Ina Mäurer, Andreas Zollmann, Karsten Krüger und Ben Schlingelhof
für die ausschweifenden Diskussionen zum Thema.

Frank Mäurer, Nadja Großbach, Johannes Haschke, Ina Mäurer, André Große und Thomas Schneider
haben Kommentare und Korrekturen zu früheren Versionen der Arbeit geliefert und mir sehr
geholfen.

Konrad Schöbel hat mir über Jahre(!) das Buch "`Schatten des Geistes"' von {\sc R. Penrose}
geliehen. Dafür ein ganz besonderer Dank.

Zu guter Letzt sei allen direkten und indirekten Familienmitgliedern und vielen Freunden Dank
für ihre Aufmunterungen gesagt.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------Erklaerung--------------------------

\newpage
\thispagestyle{empty} \cleardoublepage \thispagestyle{plain}

{\Large \noindent {\bf Erklärung}\label{erklaer} }

\vspace*{0.5cm} { \large \noindent Hiermit erkläre ich, daß ich die am heutigen Tage
eingereichte Arbeit zum Thema "`Berechenbarkeit des Denkens?"' selbständig erarbeitet,
verfasst und Zitate kenntlich gemacht habe. Andere als die angegebenen Hilfsmittel wurden
nicht verwendet.

\vspace*{2cm}

\noindent
Datum \hspace{5cm} Unterschrift
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
