Programm,Algorithmus und Gödel

Wissenschaft Informatik
#1

Laut verschiedenen Informatik- und Mathe-Spezialisten gibt es eine Zusammenhang zwischen den Tatsachen, dass

a)
kein ALGORITHMUS A existiert, der aus einem Programm (= syntaxkorrektem Quelltext) P einen zu ihm gehörenden Algorithmus Ap erzeugt
und
b)
es wahre Aussagen A(w) in einem entsprechenden System gibt, die nicht mit einem Kalkül auf die dazugehörenden Axiome reduziert und somit auch nicht bewiesen werden können (Gödel-Unvollständigkeitssätze)

Mich würde interessieren, wie dieser Zusammenhang plausibel gemacht werden kann.
Grüße gyx

#2

Nachfrage: Programm vs Algorithmus
Huhu.

Worin besteht denn in Deiner Sichtweise der Unterschied zwischen einem „Programm P“ und einem „zu P gehörenden Algorithmus Ap“ ?

Gruß,
KHK

#3

Guten Tag,

Läuft schematisch so ab : Text → Quellcode → Programm P (kann syntaktisch korrekt sein, aber sinnlos, z.B. nicht anhaltend) → Algorithmus Ap ( der ist also ein „sinnvolles“ Programm, ein syntaktisch und semantisch korrekter Quellcode).

Für den Übergang vom Quellcode zum syntaktisch korrekten Programm P gibt’s den Algorithmus : „Compiler“, der macht den Übergang „Automatisch-Computergesteuert“.

Für den Übergang vom Programm P zum Algorithmus Ap gibt’s sowas nicht, es gibt eben keinen Algorithmus, der ein Programm P auf semantische Korrektheit überprüfen könnte.
Das macht eben das „Gehirn“ - ab einer bestimmten Entwicklungsstufe an :smile: .

Grüße gyx

#4

Hallo,

a)
kein ALGORITHMUS A existiert, der aus einem Programm (=
syntaxkorrektem Quelltext) P einen zu ihm gehörenden
Algorithmus Ap erzeugt
und
b)
es wahre Aussagen A(w) in einem entsprechenden System gibt,
die nicht mit einem Kalkül auf die dazugehörenden Axiome
reduziert und somit auch nicht bewiesen werden können
(Gödel-Unvollständigkeitssätze)

Mich würde interessieren, wie dieser Zusammenhang plausibel
gemacht werden kann.

Das interessante an einem Algorithmus ist, dass er terminieren muss, ein Programm aber nicht. Die in a) beschriebene Aufgabe setzt also voraus, dass man das Halteproblem lösen kann. Kann man aber nicht.

Das ist ein Beispiel für den Unvollständigkeitssatz. Man kann ein Programm immer als natürliche Zahl kodieren, und die Frage, ob diese Programm terminiert ist damit eine unentscheidbare Aussage auf den natürlichen Zahlen.

Grüße,
Moritz

#5

Ja, Moritz,

danke soweit ist das jetzt klar. Das zu noch was :
wenn ein programmierter Algorithmus vorliegt, dann sollte es eine ihm entsprechende mathematische Konstruktion geben, die – wie ich aus verschiedener Literatur glaube herausgelesen zuhaben - „Kalkül“ genant wird. Mit dem Kalkül kann dann folgendes gemacht werden : Kalkül bewiesen ==> bewiesen, dass Programm ein Algorithmus ist.
Nochmals : Ist ein (mathem.) Kalkül bewiesen ==> ihm entsprechendes Programm ist Algorithmus.
Es geht dann darum, dass diese Beweisführung nicht von einem Algorithmus durchgeführt werden kann, sondern von „Gehirnfunktionen“, was immer man sich darunter vorstellen soll…
Deine Meinung dazu ?

Grüße gyx7