Programmieren: Für wen oder für was? Hardwarespezifik

[Web-Schecki]

Definiere doch mal, was "berechnen" ist. Solange Du das nicht tust ist die Diskussion für die Katz.

Der Begriff ist absichtlich nicht genau definiert, weil er eine Einschränkung an den Begriff der Berechenbarkeit darstellen würde. Der Begriff der Berechenbarkeit ist hingegen sehr gut definiert (siehe Wikipedia). Grob gesagt könnte man daraus ableiten, dass "berechnen" bedeutet: "Einen Algorithmus (also eine Berechnungsanweisung) ausführen". Die "Ausführung" ist dabei schlicht die Anwendung von logischen Regeln, wie das bei einer Turingmaschine der Fall ist, oder eben auch bei einer Programmiersprache. Die definiert diese logischen Regeln übrigens weitgehend unabhängig von der Maschine, die sie ausführt.
HTML definiert aber keine logischen Regeln, deren Anwendung dazu führt, dass ein Algorithmus ausgeführt werden kann.

Schleifen und Rekursion sind von der Mächtigkeit äquivalent.

Genau das habe ich gesagt.

Dass Schleifen keine zusätzliche Mächtigkeit haben, ist unabhängig davon klar.

Trotzdem sind es zwei unterschiedliche Dinge.
Turingmaschinen und Registermaschinen sind auch gleich mächtig, dennoch sind es zwei unterschiedliche Dinge.
Du hast behauptet, Schleifen gäbe es auch in funktionalen Sprachen. Das ist so, als würde ich behaupten, eine Turingmaschine hätte auch Register. Weil Registermaschinen ja genauso mächtig sind.
Das ist aber offenbar falsch.

 

[andy_m4]

Genau das habe ich gesagt.

Dann verstehe ich nicht das Problem was Du daraus machst.

Trotzdem sind es zwei unterschiedliche Dinge.

Klar sind das unterschiedliche Dinge. Aber das ändert doch nix am Argument.

Du hast behauptet, Schleifen gäbe es auch in funktionalen Sprachen.

Jaein. Strenggenommen hast Du sie natürlich nicht, kannst sie aber mit Rekursion nachbilden. De-facto hast Du also doch Schleifen oder zumindest ein Konzept was gleich mächtig ist. Und genau das ist der entscheidende Punkt bei der Argumentation. Denn dabei ging es um Mächtigkeiten.

er Begriff der Berechenbarkeit ist hingegen sehr gut definiert (siehe Wikipedia). Grob gesagt könnte man daraus ableiten, dass "berechnen" bedeutet: "Einen Algorithmus (also eine Berechnungsanweisung) ausführen". Die "Ausführung" ist dabei schlicht die Anwendung von logischen Regeln, wie das bei einer Turingmaschine der Fall ist, oder eben auch bei einer Programmiersprache.

Also ich stelle noch mal die Frage, das wenn Du Turing-Vollständigkeit (oder ein Äquivalent davon ) nicht als Maßstab nimmst ab wann eine Sprache als Programmiersprache zählt, was zählt denn dann?

 

[Web-Schecki]

Klar sind das unterschiedliche Dinge. Aber das ändert doch nix am Argument.

Welches Argument?
Ich hatte ursprünglich nur angemerkt, dass Schleifen nunmal keine Voraussetzung für Turing-Vollständigkeit sind. Dass man - vage formuliert - in irgendeiner Weise in der Lage sein muss, bestimmte Berechnungen abhängig von der Eingabe beliebig oft auszuführen, mag ja stimmen, aber das geht eben auch mit anderen Konzepten als der Kontrollstruktur "Schleife".

Also ich stelle noch mal die Frage, das wenn Du Turing-Vollständigkeit (oder ein Äquivalent davon ) nicht als Maßstab nimmst ab wann eine Sprache als Programmiersprache zählt, was zählt denn dann?

Es gibt mit Sicherheit keine unumstrittene, vollständige Charakterisieung. Aber man wird sich darauf einigen können, dass eine Programmiersprache ein Berechnungsmodell implizieren muss, sodass man in der Lage ist, Algorithmen zu formulieren und anhand des Berechnungsmodells logisch auszuführen. Man muss aber (womöglich) nicht zwingend alle berechenbaren Funktionen auch berechnen (d.h die entsprechenden Algorithmen formulieren und logisch ausführen) können - Turing-Vollständigkeit wäre also keine notwendige Voraussetzung.

Bei HTML kann man keine nichttrivialen Algorithmen formulieren und logisch ausführen, weil HTML kein Berechnungsmodell impliziert. Es ist also schlicht nicht definiert, wie man mittels HTML nichttriviale Algorithmen formulieren und logisch berechnen kann. Bei Programmiersprachen sollte das aber definitiv der Fall sein. Ich hab das jetzt schon mehrfach so geschrieben und verstehe nicht, was daran unklar sein sollte.

Ich würde sogar soweit gehen und behaupten, Turing-Vollständigkeit ist nicht mal eine hinreichende Voraussetzung für eine Programmiersprache. Die zugrundeliegende Logik von einem unendlich-Minesweeper ist auch Turing-vollständig. Aber um damit wirklich Algorithmen zu formulieren, muss man gewisse Annahmen über "Eingabe" und "Ausgabe" treffen, die durch Minesweeper als Spiel alleine nicht gegeben sind. Deshalb wäre unendlich-Minesweeper auch keine Programmiersprache, was intuitiv sinnvoll ist - auch wenn man damit theoretisch beliebige Dinge berechnen kann...

 

[BeBur]

Um es noch unübersichtlicher zu machen ;-):
"Schleifen" und "Rekursion" sind allgemeine Begriffe die verschiedenes bedeuten können, z.B. reine foreach Schleifen terminieren grundsätzlich und sind daher z.B. nicht vom Halteproblem betroffen aber führen afaik daher auch nicht zu Turing-Vollständigkeit (zusammen mit dem üblichen anderen restlichen Konstrukten ).

Bei Rekursion gibt es womöglich ähnliche Abstufungen, sprich man kann nicht einfach von "Schleifen" oder "Rekursion" sprechen .

Davon ab verweise ich auf #16.

 

[andy_m4]

Welches Argument?

Ähm. Willst Du, das noch mal wiederhole was bereits gesagt wurde weil Du keine Lust hast selber nachzugucken?

Ich hatte ursprünglich nur angemerkt, dass Schleifen nunmal keine Voraussetzung für Turing-Vollständigkeit sind.

Schon wieder hängst Du Dich am Begriff Schleife auf. Der ist doch hier eher nur nebenbei relevant. Hab ich aber schon mehrmals ausgeführt und verweise deshalb auf meine früheren Beiträge.
Ich würde mich da lediglich wiederholen. Sollte an meinen Ausführungen etwas unklar sein, frag halt konkret nach.

Aber man wird sich darauf einigen können, dass eine Programmiersprache ein Berechnungsmodell implizieren muss

Na dann nenne doch endlich mal ein konkretes Berechnungsmodell. Dann können wir darüber reden.
Du machst es Dir einfach weil Du stets vage bleibst.

(d.h die entsprechenden Algorithmen formulieren und logisch ausführen) können - Turing-Vollständigkeit wäre also keine notwendige Voraussetzung.

In PROLOG formulierst Du auch keine konkreten Rechenschritte, sondern deklarierst Dein Programm lediglich.
Ist PROLOG jetzt eine Programmiersprache oder nicht? Und wenn nein, warum nicht? Und wenn ja, warum ja.

Bei HTML kann man keine nichttrivialen Algorithmen formulieren und logisch ausführen, weil HTML kein Berechnungsmodell impliziert. Es ist also schlicht nicht definiert, wie man mittels HTML nichttriviale Algorithmen formulieren und logisch berechnen kann.

Ok. Aber was muss denn dann da sein, um als Programmiersprache zu gelten? Wieviel Mächtigkeit darfs denn sein?
Ab wann beginnen nichttriviale Algorithmen?
Wieder machst Du es Dir einfach, indem Du vage bleibst.

Ich würde sogar soweit gehen und behaupten, Turing-Vollständigkeit ist nicht mal eine hinreichende Voraussetzung für eine Programmiersprache. Die zugrundeliegende Logik von einem unendlich-Minesweeper ist auch Turing-vollständig.

Sag nicht was es nicht ist, sondern sag was es ist.

Es gibt mit Sicherheit keine unumstrittene, vollständige Charakterisieung.

Wenn Du keine vollständige Definition geben kannst, dann ist das ja auch nicht dramatisch. Nur wirds dann halt schwierig, wenn man dann Behauptungen a-la ABC ist eine Programmiersprache und XYZ aber nicht.

"Schleifen" und "Rekursion" sind allgemeine Begriffe die verschiedenes bedeuten können, z.B. reine foreach Schleifen terminieren grundsätzlich und sind daher z.B. nicht vom Halteproblem betroffen aber führen afaik daher auch nicht zu Turing-Vollständigkeit (zusammen mit dem üblichen anderen restlichen Konstrukten ).

Dem kann ich nur uneingeschränkt zustimmen.
Generell meinte ich aber mit Schleifen die turing-vollständige Variante und nicht z.B. eine Iteration über einer endlich lange Liste.

 

[BeBur]

Ok. Aber was muss denn dann da sein, um als Programmiersprache zu gelten? Wieviel Mächtigkeit darfs denn sein?
Ab wann beginnen nichttriviale Algorithmen?
Wieder machst Du es Dir einfach, indem Du vage bleibst.

Es gibt gewiss eine diskutable Grauzone, HTML gehört aber nicht dazu. CSS auch nicht, auch wenn neuere Versionen Turing-Vollständig sind.

 

[Web-Schecki]

Schon wieder hängst Du Dich am Begriff Schleife auf.

Nö, ich erkläre dir nur, warum ich das anfangs getan habe und warum ich deine Äußerung dazu für falsch halte.

Na dann nenne doch endlich mal ein konkretes Berechnungsmodell. Dann können wir darüber reden.
Du machst es Dir einfach weil Du stets vage bleibst.

Das Berechnungsmodell wird aber erst durch die Programmiersprache definiert! Für jede Programmiersprache ist das grundsätzlich anderes Modell. Ist das so schwer zu verstehen?

In PROLOG formulierst Du auch keine konkreten Rechenschritte, sondern deklarierst Dein Programm lediglich.
Ist PROLOG jetzt eine Programmiersprache oder nicht? Und wenn nein, warum nicht? Und wenn ja, warum ja.

Auch PROLOG entspricht ganz genau dem, was ich gesagt habe. PROLOG definiert ein Berechnungsmodell und mithilfe von PROLOG-Programmen kann man Algorithmen beschreiben und diese - anhand des durch die Sprache selbst definierten Berechnungsmodells - ausführen.

Ok. Aber was muss denn dann da sein, um als Programmiersprache zu gelten? Wieviel Mächtigkeit darfs denn sein?
Ab wann beginnen nichttriviale Algorithmen?
Wieder machst Du es Dir einfach, indem Du vage bleibst.

Nö, ich bin nicht vage, du verstehst nur nicht, was ein Berechnungsmodell ist, und da hilft dir Wikipedia sicher weiter. Triviale Algorithmen wären solche, die die Identität oder eine Konstante C "berechnen", also f(x) = x oder f(x) = C. Man könnte argumentieren, dass das selbst mit HTML geht, aber grundsätzlich geht das mit ALLEM - daher wäre das trivial. Nichttrivial ist alles, was darüber hinaus geht.

Sag nicht was es nicht ist, sondern sag was es ist.

Du verstehst nicht, was der mathematische Begriff "Charakterisierung" bedeutet, kann das sein?