Theoretische Informatik: Berechenbarkeit
-
Psst, nicht ansprechen!
-
Prof84 schrieb:
freakC++ schrieb:
Hallo zusammen,
ich nehme gerade in der Schule "Berechenbarkeit" durch und ich frage mich, ob so etwas berechenbar ist:
int i = 1; while (i == 1) {}Könnt ihr mir da weiterhelfen?
Vielen Dank
lg, freakC++Berechnbarkeit ist eine Entscheidung, ob ein (mathematischer/numerischer) Prozess zu einem Ergebnis führt. (Qualitative Aussage) - j/n.
Ich vermisse im Code das Ergebnis.
Dass ein Ergebnis erforderlich ist, ist Unsinn. Man betrachtet partielle Funktionen in der theoretischen Informatik. Im Gegensatz zu den Funktionen der Mathematik muss eine partielle nicht auf dem gesammten Definitionsbereich tatsächlich definiert sein. Exakt so modelliert man nicht terminierende Algorithmen für bestimmte oder alle Eingaben, wenn man später dazu übergeht den Funktionsbegriff mit anderen Berechnungsmethoden (TM, Registermaschinen, While-Programme, ...) zu vergleichen.
-
Skonto schrieb:
Dass ein Ergebnis erforderlich ist, ist Unsinn. Man betrachtet partielle Funktionen in der theoretischen Informatik. Im Gegensatz zu den Funktionen der Mathematik muss eine partielle nicht auf dem gesammten Definitionsbereich tatsächlich definiert sein. Exakt so modelliert man nicht terminierende Algorithmen für bestimmte oder alle Eingaben, wenn man später dazu übergeht den Funktionsbegriff mit anderen Berechnungsmethoden (TM, Registermaschinen, While-Programme, ...) zu vergleichen.
Interessanter Zufall:
Haste einen kürzlich Vortrag von mir gehört und einfach den Unterscheid zwischen Assessmentergebnis und Systemergebnis nicht verstanden?Wenn ja nochmals erklärt:
Beim Systemergebnis kannste in der Tat in partiellen Funktionen keine oder mehrere Ergebnisse erhalten, weil es keinen durchgehenden Gültigkeitsbereich gibt, wie Du ja gesagt hast, wie zum Bleistift bei Hyergraphen oder simplen Relationen. Wenn Du die (fehlenden) Ergebnisse jetzt mit dem Beurteilungssystem koppeln willst, haste eine System-2-System-Beziehung und brauchst eine funktionale Darstellung. Die erhälst über die Zustandssummen der einzelen Solution Constraints, mit der Du die Baselines der Zustansachse bilden kannst (constraint network). Dafür brauchst Du aber ein Ordnungsprinzip das von Assessment Concept geleifert werden muss. Um den PKI zu erhalten gehst Du einfach über die Zustandssummen, die praktisch z.B. mit FFT gebildet werden können o.ä. Diese Signale werden dann im Wahrnehmungskonzept mit einem Ausdruck assoziert und diese werden dann validiert (funktional). Und diese Resultate bezeichne ich hier als Ergebnis.freakC++ möchte scheinbar das in Code das Beurteilungssystem nicht formulieren, sondern es intuitiv im Kopf machen. Was auch ein funktionales System ist aber nicht in seinem Scope. Und deshalb funzt das nicht hier.
Das lernen die theoretischen Informatiker derzeit ganz, ganz fleißig von mir.
-
@Prof84: Hast du weiterfuehrende Literatur oder Links parat?
-
Prof84 schrieb:
[...]Buzz[...]
-
knivil schrieb:
@Prof84: Hast du weiterfuehrende Literatur oder Links parat?
@Skonto: Sorry, Missverständnis. Aber wegen Deinen partiellen Funktionen war ich so sicher.
Ok, meine Originalfolien werde ich nicht hier hereinstellen, mit Firmen-, Veranstaltungs- und Personendaten. Aber ein bisschen was kann ich ja ausmalen:
Abkürzungen:
PKI := performance key indikator
http://scholar.google.de/scholar?hl=de&q=Performance+key+indicator&btnG=Suche&lr=&as_ylo=&as_vis=1FFT := http://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation
Dazu sollte man kennen
Entscheidungstheory:
http://en.wikipedia.org/wiki/Decision_theoryHypergraph:
http://en.wikipedia.org/wiki/HypergraphZustandssummen:
http://en.wikipedia.org/wiki/Transition_state_theory
http://de.wikipedia.org/wiki/ZustandssummeEvoltionärer Algorithmus:
http://de.wikipedia.org/wiki/Evolutionärer_Algorithmus
http://de.wikipedia.org/wiki/Zelluläre_AutomatenConstraints:
http://en.wikipedia.org/wiki/Constraint_satisfaction
http://en.wikipedia.org/wiki/Constraint_optimization
http://en.wikipedia.org/wiki/Constraint_satisfaction_problemBaseline:
http://en.wikipedia.org/wiki/Baseline_(configuration_management)Das mit dem Wahrnehmungskonzept ist eigene R & D. Rahmenstudium für freizugängliche Literatur:
http://en.wikipedia.org/wiki/Self-concept
http://de.wikipedia.org/wiki/BDI_Agenten
http://de.wikipedia.org/wiki/PersönlichkeitspsychologieKomplexitätstheorie:
http://de.wikipedia.org/wiki/KomplexitätstheorieHeuristik:
http://de.wikipedia.org/wiki/Heuristik</wikibuzz>
Im Prinzip beschreibt unser Ansatz eine Möglichkeit in komplexen Systemen erst mal einen evolutionären Ansatz zu fahren und dann wenn die Eigenwerte der zellären Automaten ein bestimmtes Niveau erreicht haben, einen konkreten Algorithmus im Sinne der Komplexitätstheorie zu durchlaufen, weil dieser dann den heuristischen Weg darstellt die Ziele zu erreichen. Womit ich in den lezten Jahren viel Zeit verloren habe. ist ein System zu entwickeln, wie man Entscheigungsmodelle unterschiedlicher Wahrnehmungskonzepte mit dem PKI (Signal) des Systems koppelt und sowohl über den Aufbau als auch der Systemfunktion selbst eine Entscheidung trifft.
-
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?
-
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++
