Diskussion:Berechenbarkeit

Englisch<->Deutsch

Ich bin etwas unsicher mit der Übersetzung. Die Amerikaner unterscheiden zwischen Computation (Berechnungen) und Computability (Berechenbarkeit). Das erste geht so mehr in Richtung technische Informatik, bis hin zur Berechenbarkeit, während das zweite ganz klar die Theorie der Berechenbarkeit ist. --Marc van Woerkom 00:52, 24. Okt 2004 (CEST)

Berechenbarkeit

Eine Kuriosität ist, dass ein spezielles Problem, also ein Problem mit nur einer Instanz, immer berechenbar ist. Man könnte auch sagen, dass es für jede Funktion die keine Parameter hat, einen Algorithmus gibt, der diese Funktion berechnet. Das klingt verwirrend, ist aber trivial. Angenommen, die Frage lautet "gibt es Gott", und die Definition von "Gott" sei in irgendeiner Form vorgegeben. Diese Frage repräsentieren wir durch die (parameterlose) Funktion g(). Die Antwort muss nun entweder ja oder nein lauten - und für beide Antworten lässt sich leicht ein Algorithmus konstruieren, der die korrekte Antwort ausgibt. Es gibt also immer einen solchen Algorithmus, wir wissen nur nicht, welcher es ist. Das gilt nur bei zweiwertiger Logik. Ein agnostizistischer Algorithmus würde antworten können: Ich weiß nicht. Der Mensch jedenfalls ist dazu in der Lage. --Hutschi 16:55, 28. Okt 2004 (CEST)

Die obige Aussage gilt doch für alle speziellen Aussagen, zum Beispiel auch die Frage "kommt eine Folge von 13 mal der Ziffer 7 in der Dezimaldarstellung von Pi vor?" - die Antwort "ich weiß es nicht" ist keine Antwort auf die Frage, sondern eine Aussage des Programms über sich selbst. Das hat keine Bedeutung dafür, ob das Problem berechenbar ist - im bereich der Wissenrepräsentation ist diese Art von "Meta-Antwort" allerdings in der Tat sehr wichtig. -- D. Düsentrieb ⇌ 17:16, 28. Okt 2004 (CEST)

Die gewählte Logik muss schon zum Problem passen, also eine gewisse Isomorphie zwischen Problem und logischem Modell vorhanden sein. Sonst funktioniert die Übertragung von Modellvorhersagen auf das Problem schlicht nicht zuverlässig. --Marc van Woerkom 17:43, 28. Okt 2004 (CEST)

"die Antwort "ich weiß es nicht" ist keine Antwort auf die Frage, sondern eine Aussage des Programms über sich selbst. " - Man könnte die Antwort durch "Vielleicht" ersetzen. Setzt Berechenbarkeit ein zweiwertiges determiniertes logisches Modell voraus? Eine weitere Frage zur Berechenbarkeit in dem Zusammenhang: Setzt die Frage der Berechenbarkeit voraus, dass das Ergebnis richtig und eindeutig ist? Beispiel: Ein endlicher Automat unterschiedlicher Länge berechnet ein Ergebnis, das aber bei einer anderen Länge davon abweicht, was bei dem anderen entsteht. Hat die Funktion g, die oben definiert wurde, innere Parameter? Gibt sie immer die gleiche Antwort? --Hutschi 08:52, 29. Okt 2004 (CEST)

Die Frage "gibt es einen allmächtigen Gott" lässt sich per Deduktion einfacher entscheiden - wäre das besser? Also Annahme "allm. Gott existiert", Folgerung "kann alles", Folgerung zB "kann einen Stein so schwer machen, dass er ihn selbst nicht stemmen kann", Widerspruch, also Annahme falsch. --JJJK 22:11, 21. Jun. 2007 (CEST)

Berechenbarkeit und Terminiertheit

Da ist noch ein dicker Fehler im Artikel, nämlich, dass Terminiertheit erforderlich sei. Darauf komm es nicht an. Für die Berechenbarkeit ist entscheidend, dass eine mathematische Funktion $f$durch die Maschinenfunktion $f_{M}$realisiert wird, d.h. gefordert ist

$f=f_{M}$

Z.B. ist die Funktion $f(x)={\mbox{div}}$ (also die Funktion, die für beliebiges x nicht terminiert) berechenbar, da man z.B. eine Registermaschine angeben kann, die diese Funktion realisiert.

Sollte jemand eine abweichende Definition kennen, bitte ich um eine Literaturangabe!

--Marc van Woerkom 17:36, 3. Jan 2005 (CET)

Hm, bei Algorithmus hatte ich vor einiger Zeit mal die Frage aufgeworfen ob Terminiertheit eine notwendige Eigenschaft von Algorithmen ist oder nicht. Entgegen meiner persönlichen Präferenz scheint die Definition tatsächlich Terminiertheit zu verlangen. Wenn nun eine Maschienenfunktion ein Algorithmus ist, dann ist auch hier Terminiertheit pflicht. Oder ist das bei den Algorithmen doch nicht so klar? -- D. Dÿsentrieb ⇌ 19:32, 3. Jan 2005 (CET)

Die Definition von Berechenbarkeit, die ich gelernt habe, operiert nicht mit dem windelweichen Begriff Algorithmus. Es werden Registermaschinen mathematisch präzise eingeführt und die von ihnen berechneten Funktionen als berechenbar erklärt. Das beinhaltet auch partielle Funktionen, im Extremfall die Funktion, die nirgends definiert ist. Die ist hier explizit berechenbar. Ich habe mir heute ein paar Bücher anderer Autoren bestellt, um mal zu klären, wie diese diesen Begriff erklären. --Marc van Woerkom 20:09, 3. Jan 2005 (CET)

Es ist wirklich nervend, dass oft viele Köche ihre diversen Definitionen durcheinander rühren, wo dann nix kompatibles rauskommt, ohne zwischendurch klar Referenzen zu nehmen. Wissenschaftlich wäre das ein sehr unsauberes Arbeiten. Sauber ist es, evt. verschiedene Definitionen klar zu benennen, mit Herkunft. Das ist hier und bei Algorithmus noch nicht geschehen. --Marc van Woerkom 20:41, 3. Jan 2005 (CET)

Endlichkeit und Unendlichkeit

Ich sehe hier ein Paradoxon:

1. Die Berechenbarkeit mit endlichen Maschinen liefert ein "ungenaues" Ergebnis. 2. Unendlich lange rechnende Maschinen fallen nicht unter den angegebenen Begriff der Terminiertheit. Daraus folgt, dass bereits die meisten rationalen Zahlen nicht mehr berechenbar sind. 1/3=0.3333333 ... bricht nicht ab. Aber auf endlichen Automaten terminiert das (fast) immer. (Man könnte natürlich einen nicht abbrechenden Algorithmus zu jedem beliebigen Problem angeben, der es in unendlich langer Zeit löst.)

Funktionen sind als eindeutige Abbildungen definiert. Wenn die Berechnung ungenau ist, wird das Ganze gegebenenfalls mehrdeutig. Dann sind es aber keine Funktionen mehr. --Hutschi 10:04, 12. Jan 2005 (CET)

Du hast schon ein paar der Probleme für das Rechnen mit reellen Zahlen erkannt. Turingmaschinen etc. rechnen ja nur mit endlichen Darstellungen dieser Zahlen, also nur genähert. Native Datentypen von Turingmaschinen sind nur abzählbare Objekte, wenn ich es mal salopp ausdrücke.

Es gibt Erweiterungen der gängigen Modelle. Z.B. behandeln Büchiautomaten den Fall, wenn man unendliche lange Wörter bekommt. Da ist dann eine sinnvolle Terminierungsbedingung (Automat erkennt das unendlich lange Wort), wenn man zeigen kann, dass ein "Endzustand" unendlich oft angenommen wird.

Weitet man die Berechenbarkeitstheorie auf reelle Zahlen aus, dann landet man bei der Berechenbaren Analysis, ein Standardwerk ist hier Computable Analysis von Klaus Weihrauch.

Dort werden Typ-2 Maschinen als Maschinenmodell verwendet. Die haben unendlich lange Ein- und Ausgabebänder, jedoch sind das Einwegbänder. Ebenfalls sind die Terminierungsbedingungen ähnlich wie oben angedeutet angepasst.

Da bestimmte reelle Zahlen mehrere Darstellungen haben, z.B. kann man 1 als 0.9999.. oder 1.0000.. schreiben, man sich aber leider für eine entscheiden muss, führt es dazu, das bestimmte reelle Operationen nicht berechenbar sind, z.B. die reelle Multiplikation mit 3.

Ich mache dazu noch ein paar Artikel. --Marc van Woerkom 15:27, 12. Jan 2005 (CET)

Danke, Mark. Ich dachte mir schon, dass der Artikel noch einseitig ist. Weitere Fragen ergeben sich dabei: Im endlichen Bereich: Gibt es da eine Theorie, was und mit welcher Genauigkeit in einer endlichen vorgegebenen Zeit mit endlichen Mitteln berechenbar ist? Gibt es den Begriff der Berechenbarkeit auch für Analogrechner? --Hutschi 16:34, 12. Jan 2005 (CET)

Welche Probleme mit welchem Zeitaufwand berechenbar sind, damit beschäftigt sich die Komplexitätstheorie, siehe besonders Zeitkomplexität. Über Analogrechner weiss ich allerdings nichts... kommt vermutlich auch auf den Typ an. HTH -- D. Dÿsentrieb ⇌ 19:40, 12. Jan 2005 (CET)

Da fällt mir nur die Intervallarithmetik ein, wo neben den Zahlen noch Intervalle für die aktuell erreichte Genauigkeit mitgeführt werden. Diese Rechnungen haben sogar Beweischarakter. Für Analogrechner? Kann sein. Auf jeden Fall gibt es eine Erweiterung auf Quantencomputer. Da untersucht man dann die Quantencomputerversionen von endlichen Automaten und Turingmaschinen. Kommen mitunter andere Ergebnisse raus, als im klassischen Fall. Die Zustände in den Quantencomputern, die Qubits sind ja analoge Grössen. Dürfte Ähnlichkeiten besitzen. Vielleicht findet sich ja noch ein Guru, der sich besser auskennt.

Der Artikel muss jedenfalls mal überarbeitet werden, eigentlich geht es hier um die Analyse grundlegender mathematischer Modelle, mit Implikationen, was durch gewisse formale Methoden halt machbar ist und was nicht. Das zeigt dann gewisse Grenzen für den Bau von Rechnern auf, aber mehr auch nicht. Man darf dann die Aussagen auch nicht überinterpretieren. --Marc van Woerkom 20:50, 12. Jan 2005 (CET)

Also laut dem Qubit-artikel sind Qubits sehrwohl digital, weil sie auch nur 2 Zustände haben. Zwar kann man ein Qubit nicht alleine betrachten, aber selbst wenn man ein System aus endlich vielen Qubits betrachtet hat man noch immer nur endlich viele Zusrtände, also ist das System digital. -MrBurns 02:20, 6. Mär. 2007 (CET)

Psychologie, Physik

Außer Berechenbarkeit in der Rechentechnik,gibt es da nicht auch Berechenbarkeit in der Psychologie und in der Physik? Sollten wir den Begriff "Berechenbarkeit" als "Voraussehbarkeit" mit behandeln? --Hutschi 10:04, 12. Jan 2005 (CET)

Siehe dazu Determinismus, vergleiche Determinismus (Algorithmus)-- D. Dÿsentrieb ⇌ 00:15, 13. Jan 2005 (CET)

Worauf bezieht sich "andernfalls"?

"Eine Funktion $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ heißt berechenbar, wenn es einen Algorithmus gibt, der bei Eingabe von $\left(n_{1},...,n_{k}\right)\in \mathbb {N} ^{k}$ nach endlicher Zahl von Schritten $f\left(n_{1},...,n_{k}\right)$ berechnet, sofern $f\left(n_{1},...,n_{k}\right)$ definiert ist und andernfalls nicht terminiert."

Bezieht sich "andernfalls" auf definiert?

Eine Funktion $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ heißt berechenbar, wenn es einen Algorithmus gibt, der bei Eingabe von $\left(n_{1},...,n_{k}\right)\in \mathbb {N} ^{k}$ nach endlicher Zahl von Schritten $f\left(n_{1},...,n_{k}\right)$ berechnet, sofern $f\left(n_{1},...,n_{k}\right)$ definiert ist und, wenn $f\left(n_{1},...,n_{k}\right)$ nicht definiert ist, nicht terminiert. --Hutschi 15:10, 14. Feb 2005 (CET)

Zahlenfunktionen

Was ist mit "div" in $f(x)=$div gemeint? --Analyx 14:18, 30. Jan. 2010 (CET)

das problem ist zunaechst, dass div kein element der natuerlichen zahlen ist. somit ist $x\mapsto$ div kein beispiel fuer eine funktion $\mathbb {N} ^{k}\to \mathbb {N}$. wahrscheinlich haette der autor gemaess Funktion_(Mathematik) $f$ als funktion nach $\mathbb {N} \cup \{div\}$ definieren wollen (mit der entsprechenden semantik), oder alternativ f als partielle funktion nach $\mathbb {N}$ definieren muessen. --jemand jan 2014 (nicht signierter Beitrag von 46.223.175.29 (Diskussion) 13:20, 4. Jan. 2014 (CET))

Verwechslung Berechenbarkeit und Entscheidbarkeit

„Unabhängig davon ist zu beachten, dass nicht jede mathematische Funktion berechenbar ist, so ist beispielsweise das Halteproblem unberechenbar.“

Hier scheint Berechenbarkeit mit Entscheidbarkeit verwechselt worden zu sein. Nicht jede mathematische Funktion hat ein definiertes Ergebnis. Man spricht dann von einer partiellen Funktion, wozu auch die im Artikel genannte div-Funktion gehört, die ja ausdrücklich berechenbar ist. Das Halteproblem ist semi-entscheidbar. Semi-entscheidbar ist gleichwertig mit rekursiv aufzählbar [1]. In der Chomsky-Hierarchie entspricht das genau den Typ-0-Sprachen. Für alle Typ-0-Sprachen existiert eine Turingmaschine, die die entsprechende Sprache erkennt. Das Halteproblem ist daher durchaus mit einer Turingmaschine berechenbar. Klar, die Berechnung wird zu keinem Ergebnis führen, da das Problem nicht entscheidbar ist, aber das ist ja nicht die Frage bei der Berechenbarkeit (siehe Definiton der Berechenbarkeit: Funktion heißt auch dann berechenbar, wenn bei undefinierten Funktionsergebnissen der Algo nicht terminiert). --Matthäus Wander 20:36, 25. Jul 2005 (CEST)

Ähm, ich meine nicht, dass das Halteproblem durch eine Turingmaschine berechnet wird. Funktionen können berechenbar sein. Das Halteprobelm ist aber eine Menge, die können eben z.B. entscheidbar oder semi-entscheidbar sein. Der Versuch den Begriff berechenbar auf Mengen anzuwenden führt nur zu unnötiger Verwirrung.

Halteproblem/Berechenbarkeit/Entscheidbarkeit

Zunächst wird erwähnt, dass man Berechenbarkeit nicht mit Entscheidbarkeit verwechseln solle. Das ist sehr wohl wahr. Danach bare wird wervechselt, was nur wervecheselt werden kann. da poltert alles munter durcheinander und auf einmal ist von entscheidbaren Funktionen die Rede. No way. Probleme (also Mengen) sind entscheidbar, Funktionen niemals. Das ganze mündet dann in dem Erguss, das Halteproblem sei berechenbar. Autsch. Funktionen können berechenbar sein, Probleme können entscheidbar sein.

Der Zusammenhang zwischen Berechenbarkeit und Entscheidbarkeit lässt sich über die charakteristische Funktionen herstellen. Ein Problem ist nämlich genau dann entscheidbar, wenn seine charakteristische Funktion berechenbar ist. Der Vollständigkeit halber sei erwähnt, dass eine charakteristische Funktion immer total ist.

--Gar kein name 00:46, 30. Jan. 2007 (CET)

Danke, dass du das hier mal klargestellt hast, auf den Unterschied wird sonst fast nirgendwo hingewiesen. Allerdings wirkt es etwas inkonsequent in einem satz zu schreiben: "Funktionen können berechenbar sein, Probleme können entscheidbar sein." und kurz darauf: "Ein Problem ist nämlich genau dann entscheidbar, wenn seine charakteristische Funktion berechenbar ist.". Ich hatte das jetzt so verstanden, dass funktionen NUR berechenbar und Probleme NUR entscheidbar/semi-entscheidbar sind? Wieso hat denn dann ein problem plötzlich eine Funktion die berechenbar ist? Ich weiß es nicht besser, bin hier aber etwas verwirrt. (nicht signierter Beitrag von VanceVega (Diskussion | Beiträge) 17:26, 24. Mär. 2014 (CET))

Reelle Zahlen

Die Bemerkung die in diesem Artikel über die Berechenbarkeit auf reellen Zahlen gemacht wird ist zumindest unbrauchbar, vielleicht sogar falsch. Reelle Zahlen lassen sich womöglich durch unendliche Wörter repräsentieren. Von diesen ist aber im ganzen Rest des Artikels nicht die Rede. Der gesamte Artikel bezieht sich (wenn überhaupt) auf klassische Berechenbarkeitstheorie, nicht jedoch auf Berechenbarkeit auf überabzählbaren Mengen. In dem Zusammenhang zu behaupten, die Berechenbarkeit auf reellen Zahlen, sei mit der Definition geeigneter Wörter erschlagen, ist wohl etwas verkürzt.

Ich frage mich, wozu die Bemerkung überhaupt gemacht wird? (Eigentlich frage ich mich wozu dieser Artikel überhaupt dient: Für eine Fachfremden, der sich über den Begriff informieren möchte, steht da viel zu viel. Eine solche Information müsste sich in wenigen Sätze fassen lassen. Und das auch noch reichlich unsortiert. Wenn jemand z.B. noch mal etwas (Bekanntes) nachlesen möchte, nützt ihm dieser Artikel aber auch wenig, dafür ist er zu ungenau und zu unsortiert).

Nun denn, bisher wollte man mir die Löschung dieses Satzes nicht gewähren. Das hielte ich aber für angebracht. Man kann das guten Gewissens nicht so stehen lassen. Nunmehr stelle ich diesen Satz zur Diskussion.

Weiterhin wurde ich vorschlagen, diesen Artikel auf einen Verweis auf die Berechenbarkeitstheorie zu ersetzen und jenen Artikel gegebenenfalls zu überarbeiten.

--Gar kein name 17:46, 11. Feb. 2007 (CET)

Es ist schon spannend. Wenn man einen Satz löscht findet sich schnell jemand, der ihn wieder einstellt. Möchte man jedoch darüber diskutieren, kommt nichts mehr. Ich werde also diesen Satz erneut zu löschen versuchen. Wer meint, dass er bleiben soll, möchte das begründen.

--Gar kein name 19:07, 24. Feb. 2007 (CET)

Theologische Berechenbarkeit?

Am Ende des Artikels Berechenbarkeit steht Kategorie:Berechenbarkeitstheorie. Von Kategorie:Theologie ist nicht die Rede. Theologische Erörterungen haben also in dem Artikel keine Berechtigung. Ich bin daher sehr dafür, den Abschnitt Berechenbarkeit#Spezielle Probleme zu löschen, zumal er überdies sehr spekulativ ist. Irgendwelche Einwände? --AlfonsGeser 11:27, 15. Jun. 2008 (CEST)

Ich habe den Absatz jetzt umgeschrieben. Möglicherweise ging es dem Autor ja um "uniforme" Berechenbarkeit. --Wuzel 22:29, 28. Aug. 2008 (CEST)

Markierung "Belege fehlen" eingefügt

Ich war positiv erstaunt, dass der Artikel - im Gegensatz zur englischen Version - mit Registermaschien arbeitet; allerdings fehlen Turing-Maschinen, endliche Automaten usw; ferne gibt es Überschneidungen mit Berechenbarkeitstheorie.

Dabei ist mir auch aufgefallen, dass es keine Literaturangaben gibt. Das ist bei Registermaschinen schwierig, ist aber unvermeidlich.

Auch zur eigenen Motivation habe ich daher den Baustein "Belege fehlen" eingefügt, der zwar etwas drastisch klingt, aber vielleicht mehr Beiträge bringt als wenn ich alleine Literatur hinzufüge.

Vielleicht hilft die Suche nach Literatur auch, die Artikel untereinander abzugleichen.

--rainglasz 12:08, 21. Okt. 2011 (CEST)

Hat sich das mittlerweile geklärt? Der Baustein hängt da nun schon seit 4 Jahren... --TheRandomIP (Diskussion) 14:22, 29. Jan. 2016 (CET)

Nein, hat es sich nicht. U.a. ist die "formale Definition" problematisch. Sie schleudert bei partiellen Funktionen und trennt den intuitiven Berechenbarkeitsbegriff nicht klar von der Turing-Berechenbarkeit. Siehe z.B.: [2] oder [3]. Hier sollte man die Definitionen besser wirklich belegen. -- Cobalt pen (Diskussion) 02:48, 30. Dez. 2018 (CET)