Kann man folgendes als Algorithmus bezeichnen ?
-
knivil schrieb:
Nee, es heisst, dass Algorithmus und Turing-Maschine zwei unterschiedliche Konzepte sind und nicht in einen Topf geworfen werden sollten. So wie hier!
Ja, aber um festzustellen ob etwas ein Algorithmus ist, muß man nach der Definition doch feststellen, ob es immer terminiert. Oder hab ich das falsch verstanden? Und das kriegt man im Allgemeinen doch nicht so ohne weiteres hin.
-
Was kann man dann mit dem Algorithmus-Begriff anfangen? Ich hatte das ja immer als Abstraktion eines Programms oder aber als Überbegriff für die Darstellungsformen berechenbarer Funktionen (Turingmaschine, Lambda-Ausdruck, GOTO-Programm usw.) verstanden. Weder das eine oder das andere terminiert zwingend. Also haben wir hier noch einen dritten Begriff, und ich weiß nicht wohin damit.
-
Darum geht es ja nicht. Wenn ich beispielsweise 'Monoid' sage, dann verknuepfe ich bestimmte Eigenschaften damit. Das gleiche gilt fuer den Begriff 'Algorithmus'. Bei 'Algorithmus' stehen andere Fragestellungen im Vordergrund als beim Begriff 'Turing-Maschine', beispielsweise das Laufzeitverhalten. Und wenn ich staendig die Terminiertheit in Frage stelle, dann sind Gedanken zur Komplexitaet voellig irrelevant. Kurz: Wenn ich 'Algorithmus' sage, dann meine ich eine bestimmte Menge. Diese Menge ist Teilmenge von 'Turing-Maschine'. Entscheidung ob etwas in der Menge 'Algorithmus' gehoert, kann nicht innerhalb der Menge 'Algorithmus' geloest werden, sondern fruehestens in der Obermenge.
Darueber hinaus ist Algorithmus nicht an Berechnungsmodell gebunden, aber sie sind wohl den entscheidbaren (im Sinne von Turing) Problemen gleichzusetzen (wenn man in der Informatik bleibt).
-
knivil schrieb:
a) Das ist kein Algorithmus.
Möglich. Ich hätte es als einen bezeichnet.
b) Mit deiner Argumentation kann man nichtmal Nichtdeterministische endliche Automaten in deterministische umwandeln.
Doch, wieso auch nicht? Wo ist denn der Fehler in meiner Argumentation?
Eine Umsetzung in die Praxis orientiert sich auch an der Praxis. Und ich brauche in der Praxis kein Band mit astronomischer Laenge. Es reicht bei Bedarf Stuecke anzufuegen.
Das heißt, jedes Jahr zählt ein bisschen mehr als Algorithmus, weil die Festplatten größer werden?
Ein Algorithmus ist nach Wikipedia als Turingmaschine definiert.
SO genau definiert Wikipedia Algorithmus gar nicht.
Doch, siehe hier:
wikipedia schrieb:
Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.
Deswegen ist eine Turingmachine auch kein Algorithmus
[...]
Nee, es heisst, dass Algorithmus und Turing-Maschine zwei unterschiedliche Konzepte sind und nicht in einen Topf geworfen werden sollten.
[...]
Wenn ich 'Algorithmus' sage, dann meine ich eine bestimmte Menge. Diese Menge ist Teilmenge von 'Turing-Maschine'.Widerspricht sich oder nicht?
Meine Frage mit den Las-Vegas-Algorithmen bleibt weiterhin. Mir scheint es nicht sinnvoll, die Menge der Algorithmen als Teilmenge der (deterministischen) Turingmaschinen zu definieren.
-
Widerspricht sich oder nicht?
Natuerlich nicht, aber du hast die entscheidende Stelle nicht zitiert.
Das heißt, jedes Jahr zählt ein bisschen mehr als Algorithmus, weil die Festplatten größer werden?
Haha.
Zu wikipedia: Leider ohne Referenz versehen. Das Urteil der breiten Masse, also alles was man irgendwie gehoert hat, dort mit eingebracht. So wie hier. Gerade der Punkt Terminiertheit ist sehr widerspruechlich dargestellt. Man koennte mal schauen, wann die angegebene Literatur veroeffentlicht wurde. Vielleicht ist es ja ein Generationskonflikt und sie haben erst von der Turing-Maschine erfahren und dann den Euklidischen Algorithmus kennen gelernt oder die Tuerme von Hanoi nie in Real-Life gesehen.
Zu Las-Vegas: Klar kann ich durch Nameszusaetze Eigenschaften aufweiten einschraenken. Wenn wir uns dann auf eine Schnittmenge der Eigenschaften stuetzen, landen wir zweifelsohne bei 'Turing-Maschinen'. Nur haben wir 'Algorithmus' aus den Augen verloren.
-
Ist doch für die Definition egal, ob es terminiert oder nicht. Muss man halt dazu sagen.
Wir betrachten jetzt TMs, die auf allen Eingaben terminiert.
Wirt betrachten jetzt TMs die auf allen Eingaben manchmal terminieren.
Wir betrachten jetzt TMs, die auf manchen Eingaben terminieren.
etc.Wo ist das Problem?
-
das Problem ist, daß "Algorithmus" kein exakt def. Begriff ist.
Was ist eine "Berechnungsvorschrift" ? Formal kann man das nur in bezug auf einen bestimmten Automaten- oder Maschinenkalkül definieren, und dann spricht man im Fall von Maschinen von "Programmen".
Andererseits kann man das E/A-Verhalten eines "Algorithmus" analysieren, und sich fragen, ob es ein Programm mit diesem oder jenem E/A-Verhalten gibt.
-
'Berechnungsvorschrift' ist falsch. Es heisst konkret 'Handlungsanweisung', die verstanden und ausgefuehrt werden kann, z.B. von einem Menschen.
Wo ist das Problem?
Das Problem ist, dass 'Algorithmus' eben anders definiert ist, ohne TM.