Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 1

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Aufgabe

Finde die kleinste Zahl der Form , die keine Primzahl ist, wobei die ersten Primzahlen sind.


Aufgabe

Sei .

a) Finde aufeinander folgende natürliche Zahlen (also ), die alle nicht prim sind.

b) Finde unendlich viele solcher primfreien -„Intervalle“.


Aufgabe

Goldbach-1000.png

Das Schaubild rechts bezieht sich auf die Goldbachsche Vermutung. Was wird dadurch dargestellt?


Aufgabe

Zeige, dass es außer kein weiteres Zahlentripel der Form gibt, in dem alle drei Zahlen Primzahlen sind.


In der folgenden Aufgabe wird ein weiteres offenes Problem formuliert. Man mache sich die Wirkungsweise des beschriebenen Algorithmus für die Zahlen bis klar.

Aufgabe

Für positive ganze Zahlen betrachten wir folgenden Algorithmus.

Wenn gerade ist, so ersetze durch die Hälfte.
Wenn ungerade ist, so multipliziere mit und addiere dann dazu.

Frage (Collatz-Problem): Ist es wahr, dass man bei jeder Startzahl früher oder später bei landet?


Aufgabe

Wir betrachten eine Maschine, die nach und nach sämtliche Texte ausdruckt und damit auch früher oder später jeden Beweis ausgibt. Welche Eigenschaft eines in der Vorlesung 1 beschriebenen universellen Lösungsverfahrens besitzt diese Maschine nicht?


Aufgabe

Führe folgendes Gedankenexperiment durch: Es sei eine Maschine gegeben, die eine Aussage (eine Vermutung) über die natürlichen Zahlen nach und nach überprüft. Wenn sie alle Zahlen überprüft hätte, stünde die Antwort fest, doch da die Maschine Schritt für Schritt arbeitet, hat sie zu jedem Zeitpunkt immer nur eine endliche Teilmenge der natürlichen Zahlen überprüft und kann so, wenn die Aussage wahr ist, keinen Beweis für die Aussage liefern.

Im Allgemeinen braucht die Rechenmaschine für große Zahlen länger. Die Maschine wird jetzt beschleunigt, so dass sie für große Zahlen immer weniger Zeit braucht.

Die Maschine wird so beschleunigt, dass sie für die Überprüfung der ersten Zahl (also ) Sekunden braucht, für die Überprüfung der zweiten Zahl Sekunden, für die Überprüfung der dritten Zahl Sekunden. Für die Überprüfung der -ten Zahl benötigt die Maschine also genau Sekunden. Damit ist die Gesamtlaufzeit der Maschine

Diese Summe ist wohldefiniert, und zwar gleich (im Zweiersystem ist es die Zahl , deren Wert ist). Nach einer Sekunde hat also die Maschine die unendlich vielen Zahlen durchgearbeitet und überprüft, und damit die Aussage bewiesen oder widerlegt.



Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)