Kann man folgendes als Algorithmus bezeichnen ?

Michael E.

FreakY<3Cpp schrieb:

Mit Endlichkeit meine ich, dass der Algorithmus in endlich vielen Anweisungen beschreibbar und in endlicher Zeit eine Ausgabe erzeugen muss.

Eine Ausgabe erzeugen muss oder terminieren muss? Mit letzterem wäre ich nicht einverstanden, siehe z.B. Turingmaschinen, die Sprachen aufzählen.

Die Erklärung für Ausführbarkeit klingt wohl etwas "schwachsinnig", aber man versteht darunter, dass es ein Prozessor(Maschine) oder Mensch existieren muss, der den Algorithmus durchführen kann und für diesen jede einzelne Anweisung verständlich ist.

Zählen auch Gedankenexperimente? Denn Turingmaschinen kann man nicht bauen.

freaky

Michael E. schrieb:

FreakY<3Cpp schrieb:

Mit Endlichkeit meine ich, dass der Algorithmus in endlich vielen Anweisungen beschreibbar und in endlicher Zeit eine Ausgabe erzeugen muss.

Eine Ausgabe erzeugen muss oder terminieren muss? Mit letzterem wäre ich nicht einverstanden, siehe z.B. Turingmaschinen, die Sprachen aufzählen.

Terminiertheit

Terminiertheit heißt: Ein Algorithmus hält nach endlich vielen Schritten an (bricht kontrolliert ab). Dies gilt für jede mögliche Eingabe. Würde ein Algorithmus nicht terminieren (und somit zu keinem Ergebnis kommen), wäre die Folge eine so genannte Endlosschleife.

Michael E. schrieb:

FreakY<3Cpp schrieb:

Die Erklärung für Ausführbarkeit klingt wohl etwas "schwachsinnig", aber man versteht darunter, dass es ein Prozessor(Maschine) oder Mensch existieren muss, der den Algorithmus durchführen kann und für diesen jede einzelne Anweisung verständlich ist.

Zählen auch Gedankenexperimente? Denn Turingmaschinen kann man nicht bauen.

Naja, ein Algorithmus, der nicht ausgeführt werden kann, ist für mich dann kein Algortihmus, denn:

Ein Algorithmus ist eine aus endlich vielen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines Problems[...]

Und wenn mir diese "Handlungsvorschrift" das Problem nicht löst, da ich es nicht ausführen kann, habe ich kein Algorithmus.

Michael E.

So, ich hab mir mal die Definition auf Wikipedia durchgelesen.

FreakY<3Cpp schrieb:

Michael E. schrieb:

Eine Ausgabe erzeugen muss oder terminieren muss? Mit letzterem wäre ich nicht einverstanden, siehe z.B. Turingmaschinen, die Sprachen aufzählen.

Terminiertheit

Terminiertheit heißt: Ein Algorithmus hält nach endlich vielen Schritten an (bricht kontrolliert ab). Dies gilt für jede mögliche Eingabe. Würde ein Algorithmus nicht terminieren (und somit zu keinem Ergebnis kommen), wäre die Folge eine so genannte Endlosschleife.

Nach Definition muss ein Algorithmus nicht auf jeder Eingabe terminieren. Sonst wäre das weiter unten erwähnte Halteproblem auch trivial.

Michael E. schrieb:

FreakY<3Cpp schrieb:

Die Erklärung für Ausführbarkeit klingt wohl etwas "schwachsinnig", aber man versteht darunter, dass es ein Prozessor(Maschine) oder Mensch existieren muss, der den Algorithmus durchführen kann und für diesen jede einzelne Anweisung verständlich ist.

Zählen auch Gedankenexperimente? Denn Turingmaschinen kann man nicht bauen.

Naja, ein Algorithmus, der nicht ausgeführt werden kann, ist für mich dann kein Algortihmus, denn:

Ein Algorithmus ist eine aus endlich vielen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines Problems[...]

Und wenn mir diese "Handlungsvorschrift" das Problem nicht löst, da ich es nicht ausführen kann, habe ich kein Algorithmus.

Hier stimmst du auch nicht mit der Wikipedia-Definition überein, weil diese Turingmaschinen benutzt, welche man nicht bauen kann.

hustbaer

Jedes Programm das auf einer Turingmaschine (oder sonstwo) läuft, und in endlicher Zeit terminiert, kann nur endlich viele Felder/Zellen des Bandes (bzw. allgemein: Resourcen) benötigen.
Und abgesehen vom unendlichen Band, weiss ich jetzt keinen Grund, warum man eine Turingmaschine nicht bauen können sollte.

volkard

Michael E.

hustbaer schrieb:

Jedes Programm das auf einer Turingmaschine (oder sonstwo) läuft, und in endlicher Zeit terminiert, kann nur endlich viele Felder/Zellen des Bandes (bzw. allgemein: Resourcen) benötigen.

Dieses "endlich viele" kann aber mehr sein als es Atome auf der Erde gibt.

Und abgesehen vom unendlichen Band, weiss ich jetzt keinen Grund, warum man eine Turingmaschine nicht bauen können sollte.

Du nennst ja selbst den Grund.

Michael E. schrieb:

Nach Definition muss ein Algorithmus nicht auf jeder Eingabe terminieren.

hm?

Michael E.

!rr!rr_. schrieb:

Michael E. schrieb:

Nach Definition muss ein Algorithmus nicht auf jeder Eingabe terminieren.

hm?

Das hab ich doch schon erläutert. Wenn jeder Algorithmus auf jeder Eingabe terminieren müsste, wäre das Halteproblem trivial. Ansonsten denke mal an Las-Vegas-Algorithmen. Da ist auch nicht garantiert, dass sie terminieren.

Edit: Da ist nicht mal auf Eingaben, bei denen es eine Lösung gibt, garantiert, dass sie terminieren. Also find ich die Wikipedia-Definition blöd.

Edit 2: Randomisierte Algorithmen kann man auf Turingmaschinen nicht ausführen, weshalb die Wikipedia-Definition nicht allgemeingültig genug ist. Wenn man ein randomisiertes Modell betrachtet, wird man wenigstens wieder das Problem los, dass Las-Vegas-Algorithmen nicht terminieren müssen.

knivil

Randomisierte Algorithmen kann man auf Turingmaschinen nicht ausführen

Ach?

Man kann jeden randomisierten Algorithmus deterministisch machen, indem man ihn für alle Belegungen der Zufallsbits simuliert.

Dieses "endlich viele" kann aber mehr sein als es Atome auf der Erde gibt.

Und?

Du nennst ja selbst den Grund.

Ja, aber abgesehen von diesem?

Michael E.

knivil schrieb:

Randomisierte Algorithmen kann man auf Turingmaschinen nicht ausführen

Ach?

Man kann jeden randomisierten Algorithmus deterministisch machen, indem man ihn für alle Belegungen der Zufallsbits simuliert.

Dann mach mal bitte:

void recursion()
{
    if(Münzwurf ergibt "Kopf")
        recursion();
}

Dieses "endlich viele" kann aber mehr sein als es Atome auf der Erde gibt.

Und?

Also kann man eine Turingmaschine nicht bauen, weshalb es ein Gedankenexperiment bleibt.

Du nennst ja selbst den Grund.

Ja, aber abgesehen von diesem?

Ein Grund reicht, um keine Turingmaschinen bauen zu können.

Michael E. schrieb:

Das hab ich doch schon erläutert. Wenn jeder Algorithmus auf jeder Eingabe terminieren müsste, wäre das Halteproblem trivial.

das Halteproblem besteht darin, am Turing-Programm abzulesen, ob die Turingmaschine auf irgendeine Eingabe in eine Endlosschleife läuft oder nicht. In dieser Definition kommt das Wort "Algorithmus" nicht einmal vor.

Bashar

!rr!rr_. schrieb:

das Halteproblem besteht darin, am Turing-Programm abzulesen, ob die Turingmaschine auf irgendeine Eingabe in eine Endlosschleife läuft oder nicht. In dieser Definition kommt das Wort "Algorithmus" nicht einmal vor.

Das ist ja auch nicht die richtige Definition.

doch

Bashar

OK.

Michael E.

!rr!rr_. schrieb:

das Halteproblem besteht darin, am Turing-Programm abzulesen, ob die Turingmaschine auf irgendeine Eingabe in eine Endlosschleife läuft oder nicht. In dieser Definition kommt das Wort "Algorithmus" nicht einmal vor.

Ein Algorithmus ist nach Wikipedia als Turingmaschine definiert. Umgekehrt lässt sich jede Turingmaschine als Algorithmus (in der intuitiven Definition) beschreiben, indem man die Zustandsüberführungsfunktion betrachtet. Von dieser intuitiven Definition möchte ich auch nur ungern abweichen, weil ansonsten sowas wie "Lies Quelltext ein und führe ihn aus" kein Algorithmus wäre. Zur universellen Turingmaschine gäbe es auch keinen Algorithmus. Wie soll man sowas dann bezeichnen?

knivil

Michael E. schrieb:

Dann mach mal bitte: ...

a) Das ist kein Algorithmus. b) Mit deiner Argumentation kann man nichtmal Nichtdeterministische endliche Automaten in deterministische umwandeln.

Also kann man eine Turingmaschine nicht bauen, weshalb es ein Gedankenexperiment bleibt.

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.

Ein Algorithmus ist nach Wikipedia als Turingmaschine definiert.

SO genau definiert Wikipedia Algorithmus gar nicht. Zu meiner Zeit war ein entschiedenes Merkmal die Terminiertheit. Deswegen ist eine Turingmachine auch kein Algorithmus und im Zusammenhang mit dem Halteproblem wurde waehrend meines Studiums auch nie von Algorithmen gesprochen. Schaut doch einfach in einem Standardwerk der theoretischen Informatik nach.

knivil

Also Leute, ich habe in der Bibel nachgelesen, also in The Art of Computer Programming:

Finitness: An algorithm must always terminate after a finite number of steps.

D.h. Algorithmen und Programme fuer Turing-Maschinen sind nicht das gleiche. Er schraenkt das "endlich" etwas spaeter sogar weiter ein.

Michael E. schrieb:

Zur universellen Turingmaschine gäbe es auch keinen Algorithmus. Wie soll man sowas dann bezeichnen?

man könnte das intuitive Wort "Algorithmus" vermeiden, und stattdessen je nach Kontext vom "Programm" oder der (partiellen) "Funktion" (E/A-Verhalten) sprechen. Endlosschleifen entsprechen dann den nicht-definierten Stellen der partiellen E/A-Funktion.

Dann gibt es keine Verwechslung zwischen dem Programm (bspw. als 0-1-Kette codiert) einer universellen TM, und der (partiell definierten) E/A-Funktion, die von einer universellen TM berechnet werden soll.

Jester

knivil schrieb:

Also Leute, ich habe in der Bibel nachgelesen, also in The Art of Computer Programming:

Finitness: An algorithm must always terminate after a finite number of steps.

Das heißt es ist im Allgemeinen unentscheidbar, ob eine gegebene Handlungsvorschrift einen Algorithmus darstellt oder nicht. Klingt ja total nützlich... Vielleicht lieber weniger Bibel lesen?

knivil

Nee, es heisst, dass Algorithmus und Turing-Maschine zwei unterschiedliche Konzepte sind und nicht in einen Topf geworfen werden sollten. So wie hier!