Theoretische Informatik: Berechenbarkeit
-
knivil schrieb:
Ich weiss, was die einzelnen Begriffe bedeuten, aber der Zusammenhang will sich mir dennoch nicht erschliessen.
Was hast Du nicht verstanden? Wo willst Du mehr Info?
-
Prof84 schrieb:
Psst, nicht ansprechen!
Das Kind ist doch schon im Brunnen.
-
Hallo zusammen,
vielen Dank für die Diskussion. Das war sehr interessant. Da ich das Thema in der Schule habe, kann ich mit einigen Begriffen nichs anfangen. ICh habe aber nochmal nachgefragt:
Eine Funktion ist genau dann berechenbar, wenn ein Algorithmus exisitiert, der für jedes j in J in endlicher Zeit terminiert und f(j) zurückgibt.
Und jetzt das wichtige:
Falls j nicht in J ist, dann muss der Algorithmus nicht in endlicher Zeit terminieren.
Daher ist while(true) berechenbar.
Vielen Dank
lg, freakC++
-
Noch eine andere Frage: Wikipedia sagt, dass Pi und e berechenbare Zahlen seien. Warum? Es gibt keinen Algorithmus, der pi in endlicher zeit bestimmen kann! Also dürfe die zahl auch nicht berechenbar sein.
Viele Dank
lg, freakC++
-
freakC++ schrieb:
Eine Funktion ist genau dann berechenbar, wenn ein Algorithmus exisitiert, der für jedes j in J in endlicher Zeit terminiert und f(j) zurückgibt.
Daher ist while(true) berechenbar.
Wieso, ist while(true) eine Funktion?
Noch eine andere Frage: Wikipedia sagt, dass Pi und e berechenbare Zahlen seien. Warum? Es gibt keinen Algorithmus, der pi in endlicher zeit bestimmen kann! Also dürfe die zahl auch nicht berechenbar sein.
pi und e sind auch keine Funktionen. Der Begriff "berechenbare Zahl" hat eine eigene Definition: http://de.wikipedia.org/wiki/Berechenbare_Zahl
-
while(true) ist eine mögliche Implementierung der nirgends definierten Funktion. Daher ist es berechenbar.
-
freakC++ schrieb:
while(true) ist eine mögliche Implementierung der nirgends definierten Funktion. Daher ist es berechenbar.
Nein. Daher ist die nirgends definierte Funktion berechenbar. Aber while(true) ist nicht die nirgends definierte Funktion.
-
aber die implementierung. sie liefert für jedes d aus D f(d). !
-
freakC++ schrieb:
while(true) ist eine mögliche Implementierung der nirgends definierten Funktion. Daher ist es berechenbar.
Ich dachte den Unterschied zwischen Algorithmus und Funktion sei klar ... falsch gedacht. Bei Berechenbarkeit fragt man, ob gegebene Funktionen berechenbar sind. Die Antwort im positiven Fall ist der Algorithmus. Also Algorithmus oder Implementation ist die Antwort, nicht die Frage ...
Wenn du also nach while{true} im Sinne von Berechenbarkeit fragst, ist es keine Frage, sondern schon die Antwort.
-
Alles klar. Danke für euer Hilfe! Ihr habt mir sehr geholfen.
Bis bald
lg, freakC++
