Theoretische Informatik: Berechenbarkeit
-
Ich weiss, was die einzelnen Begriffe bedeuten, aber der Zusammenhang will sich mir dennoch nicht erschliessen.
-
Bashar schrieb:
Berechenbarkeit ist ein sehr einfacher Begriff, der letztlich nur ein wenig Mengentheorie voraussetzt. Du fährst dagegen ein vergleichsweise riesiges, auf den ersten Blick unzusammenhängendes Framework an Begrifflichkeiten auf, das den simplen Begriff ich sag mal uminterpretiert und das nichtmal vor der Psychologie halt macht. Mal unterstellend, dass das Hand und Fuß hat, tust du das weil 1) die simple Theorie ohne diesen Unterbau nicht denkbar ist oder 2) weil die simple Theorie ohne diese Begriffe nicht angewendet werden kann? Also ist das ein Unter- oder ein Überbau?
Psst, nicht ansprechen!
-
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++
