A Computational Challenge
-
http://www.cs.queensu.ca/home/akl/CHALLENGE/A_Computational_Challenge.htm
ich bin mir nicht sicher, ob die aufgabe richtig verstehe.
For an arbitrary number of clocks N, it is required to compute the average of the N times displayed at a given moment T
es soll der durchschnitt aller angezeigten uhrzeiten zu einem gegebenen zeitpunkt berechnet werden.
man würde also beispielsweise die uhrzeiten als minuten seit 0:00 uhr addieren, durch N teilen und das ergebnis als uhrzeit darstellen? oder wie ist "durchschnitt von N uhrzeiten" zu verstehen?das problem liegt wohl darin, dass N zum zeitpunkt der konstruktion des computers nicht bekannt ist, die leistung des computers aber bereits bei seiner konstruktion festgelegt wird. ist das korrekt?
wenn meine annahmen richtig sind, bin ich der meinung, dass die aufgabe nicht lösbar ist, denn N kann ja beliebig groß werden, während die anzahl der lesevorgänge pro tick begrenzt ist.
-
a challenger schrieb:
http://www.cs.queensu.ca/home/akl/CHALLENGE/A_Computational_Challenge.htm
ich bin mir nicht sicher, ob die aufgabe richtig verstehe.
For an arbitrary number of clocks N, it is required to compute the average of the N times displayed at a given moment T
es soll der durchschnitt aller angezeigten uhrzeiten zu einem gegebenen zeitpunkt berechnet werden.
man würde also beispielsweise die uhrzeiten als minuten seit 0:00 uhr addieren, durch N teilen und das ergebnis als uhrzeit darstellen? oder wie ist "durchschnitt von N uhrzeiten" zu verstehen?Ja, das ist aber auch gar nicht der Punkt hierbei.
das problem liegt wohl darin, dass N zum zeitpunkt der konstruktion des computers nicht bekannt ist, die leistung des computers aber bereits bei seiner konstruktion festgelegt wird. ist das korrekt?
Ja, das geht in die Richtung. Er meint, dass der Durchschnitt zu einem Zeitpunkt T eine berechenbare Funktion ist. Da aber die Eingabe nur eine bestimmte Zeit zur Verfügung steht, kann es keinen Universalcomputer geben, der diese für jedes N berechnen kann.
wenn meine annahmen richtig sind, bin ich der meinung, dass die aufgabe nicht lösbar ist, denn N kann ja beliebig groß werden, während die anzahl der lesevorgänge pro tick begrenzt ist.
Ja, das will er damit ja aussagen. Ob das wirklich die Church-Turing-These widerlegt, darüber mag man vielleicht geteilter Meinung sein.
-
da über wand, uhren und ablesetechnik nichts genaues vorgegeben ist, treffe ich einfach mal folgende annahmen:
- die wand mit den uhren steht auf der erde
- die uhren hängen nebeneinander
- die uhren zeigen die zeit z. b. in brailleschrift an, die pins sind mit farbe bedeckt (wie ein stempel)da die wand auf der erde steht und die erdoberfläche endlich ist, hat sie eine maximale länge, die sich ausrechnen lässt.
ich nehme nun ein stück papier dieser länge und spanne es vor die uhren. sobald der zeitpunkt t gekommen ist, drücke ich das papier gegen die pins und erhalten so einen abdruck aller angezeigten uhrzeiten zu diesem zeitpunkt.die rolle scanne ich dann ein und berechne den durchschnitt.
-
Über die Voraussetzungen ist immerhin soviel gesagt, dass deine erste Annahme nicht gültig ist: Die Wand, an der die Uhren hängen, hat keine von vornherein beschränkte Länge.
-
Mir ist überhaupt nicht klar wie er zu der Aussage kommt, dass das berechenbar sei. Welchen Berechenbarkeitsbegriff legt er da zugrunde? Die Definitionen von berechenbarkeit die ich kenne lassen keine sich ändernden werte als eingaben zu, zumindest keine funktionen, die sich nach einer gewissen zeit nicht mehr auswerten lassen.
-
Berechenbarkeit ist eine Eigenschaft einer Funktion, es gibt da also überhaupt keinen Zeitbegriff, also auch keine sich ändernden Eingaben oder ähnliches. Der Durchschnitt aller (endlich vieler) Uhrzeiten ist definitiv eine berechenbare Funktion.
-
Eben. Nur dass er offensichtlich nicht die Uhrzeiten als Eingabe gibt (sonst könnte ich die ja in aller Ruhe auslesen ohne Zeitconstraint) sondern eben die Uhren selbst. Deswegen frage ich nach seinem Berechenbarkeitsbegriff dafür.
-
meine "lösung" war selbstverständlich nicht ernst gemeint.
Bashar schrieb:
Die Wand, an der die Uhren hängen, hat keine von vornherein beschränkte Länge.
na gut. aber wenn er eine unendlich lange wand zur verfügung hat, wird sich doch sicher irgendwo eine unendlich lange rolle klopapier auftreiben lassen
ich finde die aufgabe ausgesprochen dämlich. eine unnötig komplizierte und wenig originelle verpackung für die triviale aussage man kann nicht unendlich viele werte in endlicher zeit verarbeiten. dass die leistung von computern begrenzt ist, weiß sogar mein fünfjähriger bruder.
-
a challenger schrieb:
na gut. aber wenn er eine unendlich lange wand zur verfügung hat, wird sich doch sicher irgendwo eine unendlich lange rolle klopapier auftreiben lassen
ich finde die aufgabe ausgesprochen dämlich[...]
Von unendlicher Länge ist nirgends die Rede.
-
Bashar schrieb:
Von unendlicher Länge ist nirgends die Rede.
...
The limestone wall is long at will, allowing N to be big at will.
läuft das nicht auf das gleiche hinaus?
-
a challenger schrieb:
The limestone wall is long at will, allowing N to be big at will.
läuft das nicht auf das gleiche hinaus?
nein, das ist ein unterschied. eine beliebige natürliche Zahl besitzt beispielsweise immer noch einen nachfolger, das heißt eine andere natürliche Zahl, die echt größer ist.
es ist auch problemlos möglich beliebig viele zahlen aufzuaddieren... unendlich viele machen dagegen probleme, da ist nichtmal klar was das eigentlich bedeuten soll.
-
eine beliebige natürliche Zahl besitzt beispielsweise immer noch einen nachfolger, das heißt eine andere natürliche Zahl, die echt größer ist.
das heißt ich kann meine papierrolle bis in alle ewigkeit verlängern, es wird immer unabzählbar viele wandlängen geben, die länger sind. wo liegt nun der praktische unterschied zur unendlichkeit?
statt über mein begrenztes wissen übre mathematische begriffe zu diskutieren würde ich lieber eure meinung zu der aufgabe wissen. ich sage, es wird eine triviale aussage in eine unnötig komplizierte und schlecht konstruierte aufgabenstellung verpackt. ich komme mir dabei ein bisschen veralbert vor.
aber was haltet ihr von der aufgabe?
-
a challenger schrieb:
eine beliebige natürliche Zahl besitzt beispielsweise immer noch einen nachfolger, das heißt eine andere natürliche Zahl, die echt größer ist.
das heißt ich kann meine papierrolle bis in alle ewigkeit verlängern, es wird immer unabzählbar viele wandlängen geben, die länger sind. wo liegt nun der praktische unterschied zur unendlichkeit?
du kannst durch N teilen, durch unendlich nicht wirklich.
die formel lautet in etwa
Sum(rand(0:0,23:59),0,N)/N
Theoretisch kannst du also, wie bei der herleitung der ableitung, auch Lim N->unendlich (was aber nicht unendlich selbst ist) rechnen. bei mir kommt dann raus dass durchschnitt der zeiten 11:59 ist.
das waere jedenfalls meine idee
statt über mein begrenztes wissen übre mathematische begriffe zu diskutieren würde ich lieber eure meinung zu der aufgabe wissen. ich sage, es wird eine triviale aussage in eine unnötig komplizierte und schlecht konstruierte aufgabenstellung verpackt. ich komme mir dabei ein bisschen veralbert vor.
nicht jeder ist faehig etwas kompliziertes simpel auszudruecken, dass es auch jeder versteht.
aber was haltet ihr von der aufgabe?
naja, da find ich die RSA challenge oder sowas besser. Dieses hier drivtet von mathematik zu philosophie ab, weil man sich streiten kann was das ergebniss ist.
-
a challenger schrieb:
eine beliebige natürliche Zahl besitzt beispielsweise immer noch einen nachfolger, das heißt eine andere natürliche Zahl, die echt größer ist.
das heißt ich kann meine papierrolle bis in alle ewigkeit verlängern, es wird immer unabzählbar viele wandlängen geben, die länger sind. wo liegt nun der praktische unterschied zur unendlichkeit?
was meinst du mit unabzählbar? wenn wir uns mal auf ganzzahlige Wandlängen beschränken bleibt's sogar abzählbar. und im kontext von berechenbarkeit betrachtet man meist ganze Zahlen oder eben Bruchzahlen, reelle Zahlen machen da gewisse Schwierigkeiten.
und was heißt schon praktischer Unterschied? In der Praxis kannst Du wohl meistens alles ab 10^10 als unendlich ansehen...
aber es gibt eben von theoretischer Seite her bedeutende Unterschiede zwischen unendlich und beliebig groß. Nimm einfach mal einen int und schreibe ne endlosschleife, die immer 1 dazu addiert. Wie oft wird der int jetzt den Wert 0 haben? -- Beliebig oft, Du kannst das Programm ja beliebig lange laufen lassen. Es gibt für jedes n>0 einen Zeitpunkt zu dem der int den Wert 0 mindestens n mal angenommen hat (nach endlicher Zeit!). Um aber unendlich oft den Wert 0 anzunehmen wäre auch unendlich viel Zeit nötig.
-
Jester schrieb:
was meinst du mit unabzählbar?
umgangssprachlich unendlich viele.
ich kann meinen computer für beliebig viele uhren auslegen, es gibt immer unendlich viele gültige N die größer sind.
oder anders gesagt: nur mit einem computer, der unendlich viele leseoperationen pro tick ausführen kann, wäre die aufgabe für alle möglichen N zu lösen.oder liege ich da falsch?
weil man sich streiten kann was das ergebniss ist.
kann man das wirklich? die aufgabe, auf einen satz reduziert, lautet: baue einen computer, der maximal N leseoperationen pro tick ausführen kann und lies damit innerhalb eines ticks [zwischen 1 und] N+x werte ein. ich sehe da kein streitpotenzial.
-
a challenger schrieb:
Jester schrieb:
was meinst du mit unabzählbar?
umgangssprachlich unendlich viele.
Ich meine "unabzählbar" ist kein umgangssprachliches Wort. "abzählbar" und "nicht abzählbar" sind dagegen mengentheoretische Fachbegriffe. Deshalb musst du dich nicht wundern, wenn das nicht so verstanden wird, wie du es meintest. Sag doch unendlich, wenn du unendlich meinst.
weil man sich streiten kann was das ergebniss ist.
kann man das wirklich? die aufgabe, auf einen satz reduziert, lautet: baue einen computer, der maximal N leseoperationen pro tick ausführen kann und lies damit innerhalb eines ticks [zwischen 1 und] N+x werte ein. ich sehe da kein streitpotenzial.
Das Streitpotenzial liegt auch gar nicht in der Lösbarkeit oder Unlösbarkeit der gestellten Aufgabe, sondern darin, ob die Unlösbarkeit eine Widerlegung der Church-Turing-These darstellt.
-
Bashar schrieb:
Das Streitpotenzial liegt auch gar nicht in der Lösbarkeit oder Unlösbarkeit der gestellten Aufgabe, sondern darin, ob die Unlösbarkeit eine Widerlegung der Church-Turing-These darstellt.
jetzt schäme ich mich ein bisschen. ich bin mit stumbleupon auf die seite gekommen und habe es versäumt, dem link am ende der seite zu folgen. deshalb habe ich die ganzen erläuterungen dazu erst jetzt gesehen.
ich finde aber trotzdem, dass er es sich zu einfach macht. die problemstellung verlangt, dass ein physikalisch unmögliches problem (beliebig lange mauer) von einem computer gelöst werden soll, der sich gefälligst an die physik zu halten hat.
-
eigentlich geht es nicht wirklich um was physikalisches, sondern eher um was theoretisches. der computer hat ne feste lesegeschwindigkeit, die kann groß sein, ist aber nach der konstruktion des rechners fest. die eingabe hingegen ist variabel und darf auch so groß sein wie sie mag. wir können sogar annehmen, dass der rechner superschnell rechnen kann und unendlich großen speicherplatz hat.
das beispiel mit der wand hat er nur, um's anschaulich zu machen.