Theoretische Informatik: Berechenbarkeit
-
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++
-
Ich sehe da keine Funktion, sondern eine Implementierung. Die Frage nach der Berechenbarkeit einer Implementierung macht keinen Sinn.
-
das hängt sehr von der definition von Berechenbarkeit ab denke ich mal.
nach der Definition: "Es gibt eine deterministische 1-Band-Turingmschine ..." würde ich sagen nein, weil die TM halten muss wenn du ihr dieses Prog vorwirfst, und das wird sie sicherlich nicht xD
Aber sicher bin ich mir nicht.
-
ich frage mich, ob so etwas berechenbar ist:
Die Frage macht so keinen Sinn. Was willst du denn berechnen?
wenn du ihr dieses Prog vorwirfst, und das wird sie sicherlich nicht
Wenn die zu berechnende Funktion einfach nur das Zaehlen der Zeichen ist, dann wird sie bei der angegebenen Eingabe sicherlich halten.
-
Naja, die Frage macht schon Sinn.
Mit Angabe einer Implementierung hat man aber die Berechenbarkeit schon direkt gezeigt.
In dem Fall geht es um die überall undefinierte Funktion und die ist WHILE-berechenbar, nicht aber etwa LOOP-berechenbar.
-
Wir hatten dieses Beispiel im Unterricht und es hieß, dass es berechenbar sei. Für mich ist ein Problem berechenbar, wenn es eine Turingmaschine gibt bzw. wenn ein Algorithmus dafür existiert.
Danach müsste "Ertunken im Threadpool" ja recht haben, denn eine Implementierung zeigt eigentlich eine Art Algorithmus. Daher ist das Beispiel berechenbar, oder?
Vielen Dank
lg, freakC++
-
Funktionen sind berechenbar, nicht Algorithmen. Man kann sich den Berechenbarkeitsbegriff vielleicht so hinbiegen, wie "Ertrunken im Threadpool" das getan hat, aber damit tut man sich keinen Gefallen, weil das nur triviale Folgerungen zulässt ("Alle Algorithmen sind berechenbar.") und damit den Begriff verwässert.
-
\small{f(x) = \bot} berechenbar? Ja, weil ... siehe Post 1. Oder einfacher:
while(true){}
-
Bashar schrieb:
Funktionen sind berechenbar, nicht Algorithmen. Man kann sich den Berechenbarkeitsbegriff vielleicht so hinbiegen, wie "Ertrunken im Threadpool" das getan hat, aber damit tut man sich keinen Gefallen, weil das nur triviale Folgerungen zulässt ("Alle Algorithmen sind berechenbar.") und damit den Begriff verwässert.
Was bitte habe ich hingebogen? Was wird da verwässert? Ist doch quatsch.
knivil hat nochmal deutlich gemacht was ich sagen wollte. War das so unverständlich?
-
Threadpool schrieb:
Bashar schrieb:
Funktionen sind berechenbar, nicht Algorithmen. Man kann sich den Berechenbarkeitsbegriff vielleicht so hinbiegen, wie "Ertrunken im Threadpool" das getan hat, aber damit tut man sich keinen Gefallen, weil das nur triviale Folgerungen zulässt ("Alle Algorithmen sind berechenbar.") und damit den Begriff verwässert.
Was bitte habe ich hingebogen? Was wird da verwässert? Ist doch quatsch.
Gefragt war, ob ein konkretes Programm berechenbar ist. Berechenbarkeit ist aber keine Eigenschaft eines Programms, sondern einer Funktion. Du hast gesagt, die Frage sei sinnvoll, und du hast sie beantwortet, indem du die überall undefinierte Funktion, die knivil danach nochmal formal hingeschrieben hat, auf Berechenbarkeit untersuchst. Damit hast du den Berechenbarkeitsbegriff erweitert.
knivil hat nochmal deutlich gemacht was ich sagen wollte. War das so unverständlich?
knivil hat nicht gesagt, dass der Algorithmus berechenbar ist.
-
Ich habe nichts erweitert, mich höchstens undeutlich ausgedrückt. Ist jetzt auch egal.
-
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.
Im weiteren Sinne muss dieses Ergebnis auch noch Anforderungen befriedigen. (Validierung).
-
Falsch! Es geht hier um den Berechenbarkeitsbegriff aus der theoretischen Informatik. Siehe Threadtitel.
-
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?
