% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 4
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die vierte Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Diese Ausgabe} ist den G\"{o}delschen Unvollst\"{a}ndigkeitss\"{a}tzen gewidmet.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{G\"{o}del und die Grenzen der Berechenbarkeit}
\end{center}
\normalsize Kurt G\"{o}del zeigte in der ersten H\"{a}lfte des 20. Jahrhunderts, dass ein formales System (also eine formale Sprache), in dem sich mathematische bzw. logische Aussagen darstellen lassen, entweder unvollst\"{a}ndig oder inkonsistent sein m\"{u}sse (Erster Unvollst\"{a}ndigkeitssatz). Ferner behauptete er, aus der Konsistenz eines formalen Systems folge, dass dieselbe nicht innerhalb dieses formalen Systems beweisbar sei (Zweiter Unvollst\"{a}ndigkeitssatz).
\\
\\ Man kann beide S\"{a}tze leicht mit Hilfe der Berechenbarkeitstheorie (wie in den Artikeln \"{u}ber formale Sprachen in den vergangenen Ausgaben beschrieben) herleiten, wenn man bedenkt, dass Vollst\"{a}ndigkeit im Prinzip bedeutet, dass jede Aussage entscheidbar sein muss, und Konsistenz, dass immer dann, wenn von dem mit dem formalen System assoziierten Mechanismus (zum Beispiel von einer Turing-Maschine) eine Aussage als beweisbar betrachtet wird, diese Aussage logisch betrachtet tats\"{a}chlich beweisbar sein muss, und wenn sie nicht als beweisbar betrachtet wird, dann nicht. Paradoxe Aussagen, bei denen die Annahme, dass sie beweisbar seien, zu der Konklusion f\"{u}hrt, dass sie nicht beweisbar sein k\"{o}nnten, und die umgekehrte Annahme, dass sie nicht beweisbar seien, zu der Konklusion f\"{u}hrt, dass sie beweisbar sein m\"{u}ssten, k\"{o}nnen von einem konsistenten System nicht entschieden werden. Daher sind konsistente Systeme nicht vollst\"{a}ndig, und diese Aussage ist logisch \"{a}quivalent zu der Aussage, dass vollst\"{a}ndige Systeme nicht konsistent sein k\"{o}nnen.
\\
\\ Der Zweite Unvollst\"{a}ndigkeitssatz im Speziellen l\"{a}sst sich zeigen, indem man argumentiert, dass eine formale Sprache in G\"{o}dels Sinne zumindest rekursiv aufz\"{a}hlbar sein muss, aber nicht rekursiv sein darf, wenn sie konsistent sein soll; denn rekursive Sprachen k\"{o}nnen nicht konsistent sein, weil die Zugeh\"{o}rigkeit jeder Aussage entscheidbar sein muss, aber Paradoxien eben nicht entscheidbar sind. Das Problem festzustellen, ob es eine Aussage gibt, deren Zugeh\"{o}rigkeit nicht entscheidbar ist, ist wiederum jedoch selbst nicht entscheidbar.
\\
\\ Interessant ist das vor allem, wenn man sich fragt, wo die Grenzen der Berechenbarkeit durch ein Computersystem liegen. G\"{o}del selbst vertrat die Meinung, der menschliche Geist w\"{a}re viel m\"{a}chtiger als jedes Computersystem, weil er Dinge berechnen k\"{o}nne, die ein Computer nicht berechnen kann. Tats\"{a}chlich ist ein Mensch ja durchaus in der Lage zu erkennen, dass eine Aussage paradox ist, w\"{a}hrend eine Turing-Maschine, die feststellen soll, ob eine Aussage beweisbar ist, entweder ein falsches Ergebnis liefern oder in eine Endlosschleife geraten w\"{u}rde. Die Frage ist jedoch, ob man nicht auch eine Turing-Maschine so programmieren k\"{o}nnte, dass sie in der Lage w\"{a}re festzustellen, ob eine Aussage paradox ist. Wir m\"{u}ssten dann zwei verschiedene Entscheidungsprobleme - also im Prinzip zwei verschiedene formale Sprachen - ber\"{u}cksichtigen: einerseits das Problem, ob eine Aussage paradox ist, und andererseits das Problem, ob eine (nicht-paradoxe) Aussage beweisbar ist. Nat\"{u}rlich ist das allgemeinere Problem, ob eine Aussage entscheidbar ist, selbst nicht entscheidbar, weil es ja gleichbedeutend ist mit dem so genannten Halteproblem, also dem Problem, ob eine Turing-Maschine, wenn sie mit bestimmten Eingabedaten gef\"{u}ttert wird, terminiert oder sich in einer Endlosschleife aufh\"{a}ngt. Das betrifft aber die Entscheidbarkeit allgemein. Paradoxe Aussagen sind eine spezielle Teilmenge der Menge von Aussagen, deren Beweisbarkeit nicht entschieden werden kann. Vielleicht w\"{a}re es zumindest f\"{u}r diese Teilmenge m\"{o}glich, einen Computer entsprechend zu programmieren - ich sehe jedenfalls keinen Grund, warum es nicht m\"{o}glich sein sollte.
\\
\\ Im Studienplan \textit{Computational Intelligence} der TU Wien stand im \"{u}brigen fr\"{u}her: ``Die zugrunde liegende Hypothese dabei ist, dass intelligentes Schlie\ss{}en letztlich nichts anderes als eine Art von Berechnung (Computation) ist.'' Wenn diese Hypothese richtig ist, folgt daraus, dass ein Computer in der Lage w\"{a}re, genauso intelligent zu schlie\ss{}en wie ein Mensch, wenn alles, was das menschliche Gehirn berechnen kann, auch von einem Computer berechnet werden kann. G\"{o}del bezweifelte das - ob er Recht hatte, kann man derzeit noch nicht sagen, und wenn er wirklich Recht haben sollte, wird man es vielleicht auch nie sagen k\"{o}nnen (denn es ist unendlich schwieriger zu beweisen, dass etwas nicht m\"{o}glich ist, als zu beweisen, dass es m\"{o}glich ist - siehe $\P$-$\NP$-Problem).
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Wie geht es weiter?}
\end{center}
\normalsize Ich habe die MathSIG gegr\"{u}ndet, weil ich gerne \"{u}ber mathematische Themen (vor allem solchen, die mit meinem Studium der Theoretischen Informatik zu tun haben; die Theoretische Informatik wird manchmal als Teilbereich der Mathematik betrachtet) schreiben wollte und in der offiziellen Vereinszeitschrift von Mensa \"{O}sterreich, TOPIQ, f\"{u}r diese Themen nur begrenzt Platz vorhanden ist. Nun bin ich bis jetzt alleiniger Autor geblieben, obwohl ich auch andere zum Schreiben eingeladen habe. Vielleicht haben andere Mensaner halt nicht dieses Bed\"{u}rfnis wie ich, \"{u}ber Mathematik zu schreiben. Da aber auch wenige R\"{u}ckmeldungen zu den Artikeln kommen, ist fraglich, ob sie \"{u}berhaupt an den Themen Interesse haben. Es k\"{o}nnte sein, dass f\"{u}r manche Leser das Niveau zu hoch, f\"{u}r andere zu niedrig ist oder die Themen die Leute einfach nicht ansprechen. Wie auch immer, ich schreibe gerne \"{u}ber Dinge, von denen ich Ahnung habe, und sehe keine andere M\"{o}glichkeit als diesen Newsletter MATHEMATIQ, wo ich solche Artikel ver\"{o}ffentlichen k\"{o}nnte. Deshalb wird es wahrscheinlich trotz allem noch weitere Ausgaben von MATHEMATIQ geben. Aber es ist nat\"{u}rlich irgendwie autistisch, wenn jemand der einzige Autor und gleichzeitig offenbar auch der einzige Leser ist.
\\
\\ Ich hatte eigentlich erwartet, dass der IQ stark mit der mathematischen Begabung zusammenh\"{a}ngt und jeder Mensaner mathematisch begabt w\"{a}re. Aber im Lauf der Jahre, in denen ich schon bei Mensa Mitglied bin, hat sich gezeigt, dass dem nicht so ist. Manche Mensaner waren in der Schule in Mathematik schlecht oder sind einfach desinteressiert. Vielleicht ist Mensa auch das falsche Publikum f\"{u}r eine Publikation wie diese. Theoretisch ist diese Publikation aber nicht auf ein Mensa-Publikum beschr\"{a}nkt, weil sie frei im Internet heruntergeladen werden kann. Man m\"{u}sste nur an den richtigen Orten Werbung machen. Darum werde ich mich bem\"{u}hen.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
