Diskussion:Berechenbarkeitstheorie

Einzelartikel

Hallo, es gibt neue Artikel Berechenbare Folge, Berechenbare Funktion, Berechenbare Menge und Berechenbare Zahl, die alle das Stub-Niveau nicht überschreiten und deren Ausbau vermutlich nur zu Überschneidungen führen würde. Vielleicht möchte sich ja jemand hier eine sinnvolle Lösung überlegen.--Gunther 02:48, 23. Jul 2005 (CEST)

Ich habe mich der Sache angenommen, ohne Deinen Vorschlag gesehen zu haben. Ich habe auch noch weitere Begriffe hinzugefügt und den Begriff berechenbare Menge entfernt, da er nicht eindeutig verwendet wird. Man landet jetzt bei semi-entscheidbaren Mengen. Ich denke es ist sinnvoll, alle Begriffe als Anlaufpunkt stehen zu lassen. Grüße, --Gerhard Buntrock 17:12, 26. Aug 2005 (CEST)

Hauptsache, jemand (= Du) hat den Überblick und denkt sich etwas dabei. Berechenbare Folge überzeugt mich allerdings noch nicht wirklich, daraus könnte man ja vielleicht doch eine Weiterleitung auf Berechenbare Funktion machen, oder?--Gunther 17:19, 26. Aug 2005 (CEST)

Näherungen?

Gibt es den Begriff der näherungsweisen Berechenbarkeit? --Hutschi 15:15, 26. Aug 2005 (CEST)

Ist mir nicht bekannt. Ich denke es gibt dafür auch keinen Bedarf. Näherungsweise kann nur mit beschränktem Aufwand sinnvoll sein. Hier gibt es Approximationen und Heuristiken etc. Wenn wir an die Berechnung von reellen Zahlen denkeen, dann gibt es den Begriff der nicht terminierenden und immer weiter die Zahl bestimmenden Algorithmen. Aber diese heißen meines Wissens nach auch nicht näherungsweise berechenbar. Grüße --Gerhard Buntrock 17:17, 26. Aug 2005 (CEST)

Maschinenmodelle

Wozu sind die Maschinenmodelle endlicher Automat bis LBA aufgeführt? Sie sind nicht gegenüber den Turing-Maschinen abgegrenzt und dadurch könnte der Eindruck entstehe, sie seien gleichmächtig.

Außerdem möchte ich anmerken, dass man sich zwar sehr wohl mit diesen Modellen auch Sicht der Berechenbarkeit beschäftigen kann, man sie aber wohl traditionell eher in der Theorie der formalen Sprachen behandelt.

--Gar kein name 17:58, 15. Feb. 2007 (CET)

Endlichkeit realer Computer

Ein realer, nicht vernetzter Computer kann nie die "Mächtigkeit" einer Turingmaschine erreichen, da sein Zustandsraum endlich ist. Ein vernetzter Computer hat zwar einen potentiell unendlichen Zustandsraum, aber so ein System ist nicht mehr deterministisch. --RokerHRO 19:13, 4. Mär. 2007 (CET)

Wie bekommst du mit einer endlichen Anzahl vom Speicherzellen einen unendlichen Zustandsraum hin? Die einzige Moeglichkeit, wirkliche Turingberechenbarkeit zu erlangen liegt - meines Wissens nach - darin, dass man Quantenrechner nutzt und dann mit den Elektronen und Atomen irgendwie (TM) relle Zahlen komplett darstellen kann. Das waere dann sogar maechtiger als die TM. --Tetha 16:34, 3. Jun. 2008 (CEST)

Mit Quantencomputern kann man auch nichts anderes darstellen und keine anderen Probleme lösen, als mit "klassischen Computern". Der Unterschied liegt lediglich in der Effizienz. Für einige Probleme, wie das "diskrete Logarithmus"-Problem, für deren Lösung keine effizienten (in Polynomialzeit ablaufende) Algorithmen für "klassische Computer" bekannt sind (die bekannten Algorithmen zum Berechnen des diskreten Logarithmus sind alle Iterationsverfahren und haben somit keine polynomielle Laufzeit), sind effiziente Quantenalgorithmen bekannt (z. B. der Shor-Algorithmus). Trotzdem kann ein Quantencomputer keine Probleme lösen, die ein "klassischer Computer" nicht lösen kann. Zum Beispiel kann auch ein Quantencomputer das Halteproblem nicht lösen. Der Effizienzvorteil des Quantencomputers liegt darin begründet, dass er von Haus aus auf Basis von komplexen Zahlen arbeitet. Die kleinste Informationseinheit in einem Quantencomputer ist nämlich das Qbit, also ein Bit mit Real- und Imaginärteil (und somit 4 definierten Zuständen, nämlich 0+i0, 0+i1, 1+i0 und 1+i1). Wenn ein Algorithmus von komplexen Zahlen nicht profitiert, ist er auf einem Quantencomputer auch nicht effizienter, als auf einem "klassischen Computer". Im Sinne der Berechenbarkeitstheorie können beide die gleichen Probleme lösen und sie können immernoch nur einen diskreten Zahlenraum darstellen, da sie über eine endliche Menge diskreter Informationseinheiten (Qbits) mit einer endlichen Menge an definierten Zuständen (4) verfügen. Wenn man wirklich einen kontinuierlichen Zustandsbereich verwenden möchte, muss man Analogrechner, etwa auf Basis von Operationsverstärkern, verwenden. Dann bekommt man allerdings Genauigkeitsprobleme durch Rauschen der Verstärker und ähnliche Einflüsse. 217.94.253.95 19:11, 22. Nov. 2009 (CET)

Die Berechenbarkeitstheorie wird oft auch als Rekursionstheorie bezeichnet. Manchmal wird letzterer Begriff auch benutzt, wenn man die Berechenbarkeitstheorie als Teilgebiet der mathematischen Logik auffasst oder um zu betonen, dass auch verallgemeinerte

Die Mutmaßungen über die Verwendung des Begriffs sind nicht belegt und mir auch nicht geläufig. Klar gibt es Rekursion aber die Begrifflichkeit ist nicht einfach eine andere Auffassung.--Jocme (Diskussion) 09:45, 22. Dez. 2017 (CET)