Diskussion:Algorithmus

Müsste es nicht heissen "Ein Algorithmus ist eine wohldefinierte endliche Methode oder Prozedur, um ein Problem zu lösen."

Markus: Ich finde das sprachlich ungeschickt. Das "um" stört mich. Besser wäre: "Ein Algorithmus ist eine wohldefinierte endliche Methode oder Prozedur zur Lösung eines Problems."

Markus: Habe dies in den Text integriert --66.171.5.203 17:38, 28. Feb 2004 (CET)

Ich tendiere dazu, diesen Artikel vollständig zu überarbeiten (und von der jetzigen Version nicht viel übrig zulassen) und zwar aus folgenden Gründen:

Es gibt insgesamt 4 Beschreibungen/Definitionen eines Algorithmus (Einleitung, Algorithmus, Grundprinzip, Definition)
Schlechte Gliederung
Teilweise (nach meinem Verständnis von Algo.) Falschaussagen (schon in der Definition) wie " Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert" (Gegenbsp. nicht-deterministischer Algorithmus) oder " Das Verfahren muss in endlich vielen Schritten zum Ende gelangen." (Gegenbsp. nicht terminierender Algorithmus) - sollte ich da falsch liegen, ist der von mir angelegte Artikel Determinismus (Algorithmus) auch falsch.
Unvollständig
...

Mein Vorschlag der Gliederung:

Einleitung (ohne Überschrift)
Definition
Eigenschaften (Finitheit, Komplexität, Terminierung, Determiniertheit, Determinismus, Effizienz, ...?)
Implementierung - da können dann Sätze wie "Algorithmen werden meistens als Computerprogramm implementiert." rein
Beispiele
Geschichte

Ich finden den Artikel ziemlich wichtig, weil Algorithmus ein Basisthema für die Informatik ist (somit auch für Wikipedia:WikiProjekt Wirtschaftsinformatik). Sollte es kein Feedback geben, lass ichs, weil alleine ist mir das Thema zu umfangreich/komplex (alleine zur Definition hab ich im Internet schon umfangreichste Diskussionen gefunden - Bsp. google-groups) --brunft 16:02, 13. Mär 2004 (CET)

Ich stimme dir voll und ganz zu. Die jetzige Form des Artikels ist ziemlich unübersichtlich. Ich hab mir deshalb erlaubt den Artikel neu zu gliedern. Dabei habe ich einiges ergänzt. Das Problem mit den Definitionen besteht glaube ich immer noch, allerdings abgeschwächt: Im ersten Satz sollte eine einfache Definition vorkommen. Der Geschichtsteil beinhaltet auch eine Definition, jedoch im historischen Kontext ;). Unter dem Gliederungspunkt Definition findet sich eine sehr knappe Definition(wie sie beispielsweise im Informatikschulunterricht gegegeben wird). Unter Implementierung könnten vielleicht noch Beispielimplementationen des Beipiels: In einer Programmiersprache, als schriftliche Rechnung etc. Aber ich wollte erstmal abwarten ob eine Neustrukturierung überhaupt erwünscht ist.-- Ich hab hunga 18:36, 3. Mai 2004 (CEST)Beantworten

Ich hab die Definition, die sich ja selbst nicht einig ist, und den formaleren Kram weiter nach hinten verschoben, Doppeltes etwas gekürzt. Beispiel eukl. Alg. ganz nach vorne, damit man versteht, wovon überhaupt die Rede ist. Auch Umsetzung in eine Programmiersprache finde ich wichtig, also nach vorne und um Beispiele ergänzt. Die Geschichte anschliessend, da enzyklopädisch wohl interessanter und eindeutiger als die "Definition" --Hubi 12:06, 13. Mai 2004 (CEST)Beantworten

Hm, sehe das etwas anders: diese lange Beschreibung des Euklidischen Algorithmus lenkt mehr ab, als das sie hilft -- ein kleines Beispiel wäre nett, ok, aber so fand ich's zu lang -- und hab ihn deshalb ausgelagert in seinen eigentlichen Artikel. Hatte Deine Nachricht hier allerdings nicht zuvor gelesen, hat sich wohl überschnitten. Meinst Du nicht, dass das Beispiel so zu lang wäre? Wenn jemand ein kleineres zur Hand hat, fände ich das jedenfalls gut... habe alternativ die Sektion "Beispiele" aufgemacht, wer sich einen konkreten Fall anschauen will, wird da sicher fündig. --Pinguin.tk 12:27, 13. Mai 2004 (CEST)Beantworten

Ja ok, aber ein klitzekleines Beispiel am Anfang muss schon sein. Der Eukl. Algorithmus eignet sich dazu hervorragend. --Hubi 12:46, 13. Mai 2004 (CEST)Beantworten

Okay, aber nicht in epischer Breite und mit Implementierung (die beim Stichwort "Algorithmus" ohnehin nicht viel zu suchen hat), sondern eine Kurzfassung -- für Details dann einfach auf Euklidischer Algorithmus verweisen. --Pinguin.tk 13:41, 13. Mai 2004 (CEST)Beantworten

Doch genau das ist was die Leser eigentlich interessiert. In Euklidischer Algorithmus hat es noch weniger verloren, da werd ich's bei Gelegenheit (aber nicht heute) wieder rausschmeissen. Der Unterschied zw. Algorithmus und Programm sollte schon im Artikel Algorithmus behandelt werden. Und die Geschichte ist jetzt ziemlich verkorkst, da sie mit dem Begriff beginnt, Algorithmen aber schon älter sind. Das hat die frühe Erwähnung des Eukl. Algorithmus in der vorherigen Version besser hingekriegt. So ist die Entwicklungsrichtung eigentlich etwas kontraproduktiv. --Hubi 14:09, 13. Mai 2004 (CEST)Beantworten

Ich seh grad, dass Computerprogramm eigentlich nur eine lasche Definition ist, da gehören die rausgeschmissenen Teile eigentlich viel besser rein. Bei Algrithmus sollte man dann doch wieder ggt als Beispiel rein (bis zu Ausführung von Hand), der Rest dann in Computerprogramm. --Hubi 14:19, 13. Mai 2004 (CEST)Beantworten

Hm, ich sehe ein, dass die Implementierung beim EA nicht so richtig viel zu suchen hat, das war etwas voreilig. Hier im Artikel würd ich halt gern die Unterschiede Algorithmus -> Implementierung -> Computerprogramm darstellen, aber nicht unbedingt eine Implementierung reinschreiben. Ob die in Computerprogramm oder in Implementierung besser aufgehoben ist, weiß ich noch nicht... --Pinguin.tk 15:17, 13. Mai 2004 (CEST)Beantworten

Ich werd in nächster Zeit mal den Artikel Algorithmus in Ruhe lassen. Evtl. Anmerkungen von mir dann hier. Computerprogramm muss aber definitiv etwas ergänzt werden. Mal überlegen. --Hubi 16:52, 13. Mai 2004 (CEST)Beantworten

Habe die Endlichkeit aus dem Artikel rausgenommen und auf das Halteproblem verwiesen. Der Artikel hat sich bislang selbst widersprochen: Erst heißt es, Algos seien endlich, dann am Ende heißt es, ob sie terminieren, lernt man in der Berechenbarkeitstheorie. Naja.

--Thorwald C. Franke 03:00, 9. Apr 2004 (CEST)

Also ich glaube, daß Du das verschlimmbessert hast: Algorithmen sind immer endlich. Berechenbarkeitstheorie sagt aus, ob es einen Algorithmus gibt (der endlich ist), der das gegebene Problem loest.

Sprich: der Satz, "ob sie terminieren" ist falsch. Ein Algorithmus der nie terminiert ist halt kein Algorithmus. --DaTroll 11:51, 9. Apr 2004 (CEST)

Hm, das ist zunächst eine definitorische Frage.

Diese löst man am besten, indem man in Fachliteratur nachschlägt.

Schüler-Duden Informatik:

Hier sind Algorithmen auch nciht endlich. Turingmaschinen werden als

eine Realisierung angesehen. Also auch nicht-endliche.

Zitat: "Für die Praxis sind meist nur solche Algorithmen von Bedeutung,

die für jede Eingabe nach endlich vielen Schritten ein Resultat liefern

und anhalten."

Goldschlager/Lister, "Informatik" (ein Klassiker):

S. 25: Prozesse/Algorithmen können unendlich sein (z.B. Alarmanlagen steuern),

S. 79: Kapitelüberschrift: "Theorie der Algorithmen",

darunter dann Berechenbarkeitstheorie etc. => Algos können auch nciht-endlich sein.

Lexikon der Informatik und Datenverarbeitung:

Auch hier gibt es die Möglichkeit, dass die Berechnung nciht abbricht.

Fazit:

Algorithmen sind auch nciht-endlich.

--Thorwald C. Franke 20:05, 9. Apr 2004 (CEST)

Könnte es sein, daß da gerade zwei Sachen durcheinander gehen?

Sind Algorithmen endliche Beschreibungen? (Ja)
Ist die Ausführung eines Algorithmus ein endlicher Prozeß? (Nein, Beispiel: Der Algorithmus, mit dem man alle natürlichen Zahlen erzeugen kann.)

--Skriptor 20:32, 9. Apr 2004 (CEST)

Nein, ich glaube nicht, dass ich DaTroll falsch interpretiert habe. Das Wort "terminieren" macht deutlich, worum es ihm geht. Er meint, dass z.B. eine Endlosschleife kein Algorithmus mehr wäre. Ist es aber doch. Endlosschleifen werden sogar praktisch eingesetzt.

Hier geht es bei Endlichkeit klar um das Halteproblem.

--Thorwald C. Franke 00:50, 10. Apr 2004 (CEST)

Thorwald hat mich schon richtig verstanden. Und ich glaube dann einfach mal, dass er Recht hat. Viele Gruesse, DaTroll 15:35, 13. Apr 2004 (CEST)

Ein Computer ist ein Werkzeug, welches bei der Lösung bestimmter Probleme hilft.

Was soll der Leser aus diesem Satz lernen? Insbesondere, wenn er sich folgenden Sachverhalt vor Augen führt:

Ein Hammer ist ein Werkzeug, welches bei der Lösung bestimmter Probleme hilft.

Ich habe folgenden Abschnitt rausgeschmissen:

Grundprinzip eines Algorithmus

Ein Algorithmus basiert auf zwei Grundelementen, der (Rechen-)Anweisung und dem bedingten Sprung. Ein bedingter Sprung zeigt an, an welcher Stelle im Algorithmus fortgefahren werden soll, wenn eine bestimmte Bedingung erfüllt ist (z.B. die, dass zwei Werte gleich sein müssen), und an welcher fortgefahren werden soll, wenn diese Bedingung nicht erfüllt ist (wenn im Beispiel also die Werte nicht gleich sind).

Das stimmt so einfach nicht; es gibt ganz verschiedene Methoden, einen Algorithmus zu formulieren, und das Verfahren mit bedingten Sprunganweisungen ist nur eine davon. Eine andere Möglichkeit sind Wenn-Dann-Abfragen in Verbindung mit Schleifen oder Markov-Algorithmen, die auf reinen Zeichenersetzungsregeln beruhen, oder µ-rekursive Funktionen. All diese Verfahren sind äquivalent im Sinne der rechnerischen Mächtigkeit. --Mussklprozz 15:30, 25. Apr 2004 (CEST)

"Typischerweise wird ein Algorithmus durch eine endliche Folge von Anweisungen beschrieben, die nacheinander ausgeführt und oft in festgelegter Weise wiederholt werden."

Die Endlichkeit hat nichts mit dem Begriff des Algorithmus zu tun.
Der Beweis, daß die rationalen Zahlen zwar unendlich sind, aber nicht dicht (im Gegensatz zu den reellen Zahlen) liegen, wird zum Bsp. über die Abzählbarkeit geführt. (Siehe auch Eulers Beweis, der Transzendenz von PI.). Das Abzählen sehe ich als einen nicht endlichen Algorithmus an. Man belehre mich eines Besseren.

In dem Satz "Die Theoretische Informatik beschäftigt sich u.a. mit der Frage, welche Problemstellungen algorithmisch, d.h. mittels genau definierter Handlungsanweisungen, gelöst werden können und wie rechenaufwendig Lösungen gegebener Probleme mindestens sein müssen." liegt dann auch schon der Hund begraben. Basis der Analyse zu diesem Begriff muß natürlichen die Algorithmentheorie sein. Die Formulierung ist nicht nur inhaltlich, sondern auch sprachlich ("Lösungen gegebener Probleme") sehr fragwürdig.

Wer kam eigentlich auf die merkwürdige Idee der "Verballhornung" im Bereich Geschichte? Scheinbar haben diese Bemerkung schon Einige Internetseiten aus wikipedia übernommen...

Wie gesagt, ich lass mich gern überzeugen. --Ping 16:16, 25. Apr 2004 (CEST)

Vielleicht hilft die Umstellung, das Problem deutlicher werden zu lassen, dass hier teils redundante,aber teils auch nicht redundante Erklärungen des Begriffs vorhanden sind. Es wäre wohl gut, alles unter einen Hut zu bringen. -Hati 16:32, 25. Apr 2004 (CEST)

Ich hab versucht, umzustellen, die Definitionen (allgemeine Definition, mathematische Definition) zu ordnen, und auch das Endlichkeitsproblem klar heraus zu stellen. Was meint Ihr? --Mussklprozz 16:39, 25. Apr 2004 (CEST)

Vielleicht habe ich jetzt zu schnell gelesen aber das "Ein Algorithmus ist eine eindeutige Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen." Hat mir eigentlich ganz gut gefallen, vor allem weil es wie im aller ersten Erklärungssatz ohne Prozedur auskommt, die ja im strengen Sinne auch nur ein Algorithmus ist. Vielleicht wird die Materie noch fassbarer, wenn man sie gegen Heuristik abgrenzt? ansonsten: der Fortschritt ist nicht aufzuhalten :-> -Hati 16:51, 25. Apr 2004 (CEST)

Warum Deine Version von 16:25, 25. Apr 2004 von Musklprozz so schnell gelöscht wurde, verstehe ich auch nicht. Die Formulierung "Ein Algorithmus ist eine eindeutige Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen." als Einleitung kann man durchaus stehen lassen. Wenn man auf die Endlichkeit so einen Wert legt, ließe sich das meiner Meinung nach auch durch das Wort "Abbruchbedingung" klar stellen. --Ping 17:32, 25. Apr 2004 (CEST)

Danke für Eure Stellungnahme.

Ich war gleichzeitig mit Hati am Arbeiten; beim Speichern gab es einen Bearbeitungskonflikt. Darauf hin habe ich vor dem Speichern Hatis Version gegen die Vorversion geprüft und gesehen, dass er eine Umstellung im Sinn hatte. Genau das hatte ich unter anderem ja auch vor. Na ja, und als ich das gesehen hatte, habe ich meine bereits fertig vorbereitete neue Version eingesetzt.

Hatis Einleitungssatz habe ich jetzt in die Definition übernommen; ich finde ihn auch besser, weil weniger technisch und somit einladender als die Version mit den Eingabe- und Ausgabegrößen. Vorher war er meinem Aufräumen unter den Definitionen zum Opfer gefallen, wo sich meines Er8ens doch einiges im Kreis herum gedreht und wiederholt hat, siehe die Diskussion weiter oben.

Dass das mit der Endlichkeit ein Problem darstellt, geht aus der Diskussion oben hervor. Daher habe ich versucht, klar abzugrenzen, in welcher Hinsicht ein Algorithmus endlich ist und in welcher Hinsicht nicht.

--Mussklprozz 19:31, 25. Apr 2004 (CEST)

Der Beitrag Leda verweist auf Algoritmus, fehlt hier -- Robodoc 23:56, 10. Jun 2004 (CEST)

Alltagsbeispiele

Die neuen Besipiele in der Tabelle am Schluss bereiten mir Magenschmerzen. Partiturlesen als Algorithmus? Dann ist jedes Buch, jeder Roman, jedes Gedicht, jeder Comic ein Algorithmus. Im Definitionssatz steht ein deutlicher Bezug zu einem Problem. Oder muss der da raus? Ein Algorithmus zum Spielen eines Instruments dürfte wesentlich komplexer sein als eine Partitur. -Hati 16:16, 4. Jul 2004 (CEST)

finde ich auch nicht gut, ist teilweise auch einfach falsch: die meisten Rezepte z.B. sind keine Algorithmen, denn "eine Prise Salz" ist keineswegs wohldefiniert, und auch bei 1 TL Backpulver wird's schwierig... Bei uns in der Informatikvorlesung fiel sowas unter was ist kein Algorithmus ;-) --Pinguin.tk 18:27, 4. Jul 2004 (CEST)

Obwohl ich die Beispiele auch nicht so gut finde, glaube ich nicht, dass man sie so einfach formal wegdiskutieren kann: im Artikel werden als "formale Definition" die Eigenschaften Determinismus, Determiniertheit, Finitheit, Ausführbarkeit und Terminierung angeführt. Wohldefiniertheit finde ich da nicht, daher kann ich nicht finden, dass "eine Prise Salz" oder "1 TL Backpulver" genügen, um das Prädikat "Algorithmus" für Rezepte zu widerlegen. Stattdessen genügt man nehme eine Prise Salz allen Kriterien, es ist determiniert (ich habe danach eine Prise Salz, nichts anderes), die Beschreibung ist endlich gross (Finitheit), die Aktion ist ausführbar in endlicher Zeit (Ausführbarkeit, Terminiertheit). Trotzdem finde ich die Gleichsetzung von Handlungsanweisung etc. mit Algorithus nicht korrekt. Der Artikel hat daher möglicherweise Schwächen in der Abgrenzung/Definition. --Hubi 10:55, 5. Jul 2004 (CEST)

gehört zur Definition von Algorithmus nicht auch Definitheit? Ist das nicht in etwa Wohldefiniertheit? Muss mal nachlesen... --Pinguin.tk 18:14, 5. Jul 2004 (CEST)

Kann schon sein, aber verschiedene Quellen widersprechen sich hier, was die Definition des Wortes angeht. Auch im Artikel wird ja erst definiert, aber dann gibt's da noch die stochastischen/probalisierten/randomisierten und ähnliche Nicht-in-die-Definition-passen-wollende Algorithmen. Aber egal, man nehme eine Prise Salz ist meiner bescheidenen Meinung nach auch (genügend) wohldefiniert, ich nehme also eine wohldefinierte Prise Salz und folge meinem Rezeptalgorithmus weiter :-) --Hubi 18:41, 5. Jul 2004 (CEST)

Eigentlich dürfte ja bei einer "guten" Definition, ein Algorithnmus, der nicht in die Definition passt, nicht als Algorithmus bezeichnet werden. Oder die Definition passt noch immer nicht. Beides scheint hier der Fall zu sein. Siehe dazu die Abgrenzung zu Prozedur bzw. den dortigen doch recht einfachen Artikel. -Hati 15:06, 9. Okt 2004 (CEST)

Church-Turing These

Aus diesem Grunde ist heutzutage die Church-Turing-These: "Jeder Algorithmus kann durch eine Turingmaschine ausgeführt werden" allgemein akzeptiert. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen zu einer Turing-Maschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache.

Mit dieser Aussage wäre ich sehr vorsichtig, weil das was wirklich zu Turing-Maschinen äquivalent ist, sind Maschinenprogramme. Ein Algorithmus ist aber abstrakter. Es gilt in etwa folgende Hierarchie:

Problemlösung in Umgangssprache
Algorithmus
Maschinenprogramm

Ich befürchte, dass man in einem Algorithmus zu leicht auch Anweisungen formulieren kann, die nicht berechenbar sind.

--Marc van Woerkom 09:14, 6. Okt 2004 (CEST)

Ich denke schon, dass sie Churchsche These zurecht allegemein akzeptiert ist. Soweit ich weis ist das so:

Es gibt keinen (bekannten) Formalismus, der eine Problemlösung exakt und eindeutig beschreibt, der nicht durch eine Turingmaschine ausgeführt werden könnte.
Ausführbarkeit durch die Turingmaschine impliziert nicht unbedingt, dass die Turingmaschine auch anhält, das Ergebnis also Berechenbar ist. Zu jedem terminierten Algorithmus gibt es aber ein Turingprogramm das anhält. Manchmal wird auch der Begriff Algorithmus so definiert, dass die terminiertheit als Eigenschaft vorausgesetzt wird - dann entfällt das Problem ganz.
Das einzige, was den aktuellen Berechenbarkeitsbegriff nach Church/Turing evtl. durchbrechen/erweitern könnte, sind Quantencomputer: sie beiten evtl. die möglichkeit, (abzählbar) unendlich viele Möglichkeiten "gleichzeitig" zu testen und würden so auch alle bisher nur semi-berechenbare Probleme berechenbar machen - das schlisst übrigens das Halteproblem mit ein.

-- D. Düsentrieb ⇌ 13:01, 6. Okt 2004 (CEST)

Du verstehst meinen Einwand nicht. Ich behaupte dass der Algorithmusbegriff im jetzigen Artikel nicht streng genug ist.

Eine Registermaschine oder Turingmaschine ist mathematisch präzise definierbar. Insbesonders sind die elementaren Operationen präzise definiert.

Registermaschine: Inkrement, Dekrement, Test auf Null
Turingmaschine: Kopf links, Kopf rechts, Schreiben von Symbol, Test auf Smybol unter Lesekopf

Aber was ist die präzise Definition von Algorithmus? Im Artikel steht:

Ein Algorithmus ist eine genau definierte Verarbeitungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen.

Es wird aber offengelassen, welche Verarbeitungsvorschriften zugelassen sind, bzw. was genau definiert hier heissen soll.

Damit könnten auch Verarbeitungsvorschriften, bzw. elementare Operationen vorkommen, die nicht berechenbar sind. Ein Beispiel:

Algorithmus Halteproblem

1. Lade Flussdiagramm der Turingmaschine

2. Lade Eingabewerte

3: Verfolge im Graphen, ob Maschine hält

4: Falls ja: gib Maschine terminiert aus

5: Falls nein: gib Maschine terminiert nicht aus

6: Halt

Der Knackpunkt ist natürlich Schritt 3, das geht halt nicht immer.

Nach der Definition im Artikel ist das ein Algorithmus. Er ist aber offensichtlich nicht berechenbar. Also bitte eine präzisere Definition von Algorithmus hier.

--Marc van Woerkom 20:21, 6. Okt 2004 (CEST)

Der Punkt ist: es herrscht unklarheit darüber, ob Terminiertheit eine notwenige Eigenschaft jedes Algoritmus ist, oder ledigleich eine häufige Anforderung. Das Taschenbuch der Informatik (3. Auflage, Fachbuchverlag Leipzig) sagt dazu auf Seite 273: Der Begriff Algorithmus (algorithm) bezeichnet eibe Vorschrift zur Lösung eines Problems, die für die Realisierung in Form eines Programmes auf einem Computer geeignet ist. und Später dann: An Algorithmen stellt man bestimmte Anforderungen, z.B. die Bedingung, dass sie Korrekt sind, dass sie terminieren und dass sie [...] ein vorgegebenes Problem lösen. Der Schülerduden Informatik impliziert allerdings in einem Nebensatz, dass es nur für berechenbare Probleme Algorithmen gibt. IMHO muss ein Algorithmus nicht terminiert sein - d.h. es gibt auch Algorithmen für Probleme, die nur semi-berechenbar sind - solche Algorithem terminieren jedoch nicht (sonst wäre das Problem ja berechenbar).

Also, was nun? Ich werde mal versuchen, diese beiden Ansichten in den Artikel einzubauen und das ganze etwas strenger zu gestalten. Gruss -- D. Düsentrieb ⇌ 21:05, 6. Okt 2004 (CEST)

So. Besser jetzt? -- D. Düsentrieb ⇌ 21:50, 6. Okt 2004 (CEST)

Nicht "lässt sich durch eine endliche", sondern wird durch eine ... definiert. Ein Algorithmus ist eine endliche Menge von Regeln, die unmissverstaendlich festlegt, wann welche Regel anzuwenden ist. Die Regeln sind rein mechanisch (d.h. ohne "Intelligenz" oder Kontextwissen) anwendbar. Ein Algorithmus muss terminieren, und zwar auf allen Eingaben. Geprueft anhand zweier Lehrbuecher der theoretischen Informatik, Encarta, und Enzyclopaedia Britannica.

Habe Anweisung in Regel umbenannt, da es in anderen Formalismen nicht immer "Anweisungen" gibt. Habe in der Einleitung den Vergleich mit Programmen ins Spiel gebracht, um Verwechslungen mit Algorithmus vorzubeugen (denen ich selber auch schon unterlag). Falls es nicht gefaellt, einfach loeschen. Ist nur ein Vorschlag.

Zu Church-Turing-These: In der These geht es nicht darum zu zeigen, dass die Formalismen aequivalent sind, das war nur die Voraussetzung, die These formulieren zu koennen.
Da der Begriff der Berechenbarkeit heutzutage meist durch Turingmachinen oder aehnliches definiert wird, sagte der Satz weiter nichts, als dass berechenbare Probleme berechenbar sind, was trivial ist. Ich habe deshalb intuitiv eingefuegt. Wahrscheinlich sollte "durch Turingmaschine geloest" durch "durch Algorithmus geloest" ersetzt werden. (Kann nicht mal jemand den Originaltext ausmachen und genau uebersetzen? In Hofstadters "Goedel Escher Bach" ist auch eine ausfuehrliche Diskussion darueber enthalten.) Auch ist diese These alles andere als "allgemein anerkannt", lasst nur die Leute aus der Kuenstlichen Intelligenz oder Philosophie hier aufkreuzen.

(Habe Literatur Ottmann/Witmayer geloescht, weil zu speziell. Habe dafuer einen Klassiker hinzugefuegt.) --Dirk Beyer 14:57, 9. Okt 2004 (CEST)

Es wäre interessant, den Algorithmus verschiedener einflussreicher Autoren mal genauer anzuschauen. Intuitiv verstehen wir wohl alle ein Kochrezept darunter. Was sagt z.B. Knuth dazu? Die Church Turing These hat eine interessante Richtung, wo behauptet wird, dass jegliche physikalische Rechenmaschine, die man bauen kann, letztlich immer nur berechenbare Funktionen

f\in P^{(1)}

berechnen kann. Aber wer weiss, vielleicht geht ja doch mehr aus der Physik rauszuholen.

--Marc van Woerkom 20:03, 9. Okt 2004 (CEST)

Aus Knuth, TAOCP 1: Besides merely being a finite set of rules that gives a sequence of operations for solving a specific type of problem, an algorithm has five important features:

finiteness [...]
definiteness [...]
input [...]
output [...]
effectiveness [...]

Also Terminierung. Aber Knuth ist halt doch irgendwo ein Praktiker, und ich meine gelernt zu haben, dass das mit der Terminierung Ansichtssache ist. Wenn ich was schriftliches dazu finde, schreib ich's hierher... --Pinguin.tk 16:08, 10. Okt 2004 (CEST)

Ich halte es nach wie vor für stritting, ob ein Algorithmus notwendigerweise terminieren muss. Die meisten definitionen, die ich finde, sagen nichts darüber. Einige verlangen die Terminiertheit, andere verlangen Determiniertheit (was IMHO definitiv falsch ist). Ich werde mich bei gelegenheit mal in der Uni-Bib schlau machen (Knuth wäre wohl ein guter Anfang...). -- D. Düsentrieb ⇌ 21:02, 9. Okt 2004 (CEST)

Die Enzyklopaedie muss unbedingt kompatibel zu Lehrbuechern der theoretischen Informatik und den anderen Enzyklopaedien sein. Falls andere das mit der Terminierung nicht so ernst nehmen,

lasst uns Avantgarde sein! Vielleicht ist ein Abschnitt "Abgrenzung" gut, wo der Unterschied zu Computerprogramm oder Prozedur (die durchaus Endlosschleifen enthalten duerfen) explizit gezeigt wird. Habe neuen Abschnitt "formale Definition" eingefuegt. Bitte um Verbesserung. Bei inhaltlicher Aenderung bitte genaue Quellenangabe. --Dirk Beyer 11:33, 11. Okt 2004 (CEST)

Das mit der Church-Turing-These gefaellt mir (noch) nicht. Da muesste wirklich sauber recherchiert werden, und am besten ein eigener Artikel angefangen werden. Hier reicht dann eigentlich ein Verweis auf diesen Artikel. --Dirk Beyer 11:57, 11. Okt 2004 (CEST)

Einen Artikel zur Church-Turing-These gibt's doch schon -- vielleicht sollte man die Diskussion dort fortsetzen? Ich finde aber, dass ein reiner Verweis vom Artikel Algorithmus aus nicht ausreicht -- ein Überblick zum Zusammenhang zwischen dem formalen Algorithmenbegriff und der CTT sollte hier schon gegeben werden, schließlich soll nicht jeder die komplette theoretische Informatik verstehen müssen, nur um unseren Algorithmus-Artikel lesen zu können. Dies hier ist kein Fachbuch, sondern eine Enzyklopädie, die auch für Laien verständlich sein sollte. --Pinguin.tk 12:19, 11. Okt 2004 (CEST)