Was genau ist Berechnung?

Ich weiß, was Berechnung in einem vagen Sinn ist (es ist das, was Computer tun), aber ich möchte eine strengere Definition.

Dictionary.comDie Definitionen von Computing, Computing, Calculate und Computing sind zirkulär und helfen daher nicht weiter.

WikipediaDefiniert Berechnung als "jede Art von Berechnung, die einem genau definierten Modell folgt". Es definiert Berechnung als "den absichtlichen Prozess, der eine oder mehrere Eingaben in ein oder mehrere Ergebnisse mit variabler Änderung umwandelt". Es scheint jedoch, dass diese Definition viele Aktionen als Berechnungen umfasst, obwohl sie normalerweise nicht als Berechnungen betrachtet werden.

Zum Beispiel, würde das nicht bedeuten, dass zum Beispiel eine Bombenexplosion eine Berechnung ist, bei der der Eingang die Zündschnur und der Ausgang die Explosion ist?

Also, was genau ist Berechnung?

Vielleicht liegt das Problem hier in der Suche nach einer hochspezifischen Definition eines sehr allgemeinen Konzepts. Ich sehe das Problem, praktisch alles als Berechnung anzusehen, nicht. Obwohl wir nicht darüber nachdenken, ist alles, was wir tun, in Bezug auf die Physik der Einzelteile zum Ausdruck zu bringen, bis hin zu zumindest herumschwirrenden Quarks. Wir haben die gleiche Situation mit der Berechnung. Es gibt Inputs, Outputs und einen Prozess (die alle trivial sein könnten). Ob sie als Berechnungen oder Berechnungsmodelle interessant oder nützlich sind, ist eine ganz andere Frage.

Die stärkste funktionierende Definition, die wir haben, stammt aus der (starken) Church-Turing-These, wonach jedes physikalisch realisierbare Rechenmodell nicht leistungsfähiger ist als eine Turing-Maschine. Wenn Sie glauben, dass dies zutrifft, können wir, obwohl wir viele Möglichkeiten haben, Dinge auszudrücken, letztendlich jede Berechnung auf eine Turing-Maschine reduzieren und somit eine Definition der Berechnung als "alles, was wir auf eine Turing-Maschine reduzieren können" angeben.

In diesem Modell ist die explodierende Bombe eine Berechnung. Es ist nicht weit verbreitet (wir hoffen;)), aber wir können in gewisser Weise mit einer Turing-Maschine modellieren (obwohl es hier ein Argument über die Art der Ausgabe und die Äquivalenz mit der TM-Ausgabe gibt). Es ist auch kein gutes Rechenmodell im Allgemeinen, da es unwahrscheinlich erscheint, dass das explodierende Bombenmodell vollständig ist.

Dies ist die Frage, die Turing in seinem berühmten Aufsatz über berechenbare Zahlen aus dem Jahr 1936 mit einer Anwendung auf das Entscheidungsproblem zu lösen versuchte . Siehe insbesondere Abschnitt 9.

Turings Arbeit steht im Kontext berechenbarer Zahlen . Es gibt andere Begriffe der Berechnung, die für die Berechnung anderer Arten von Strukturen geeignet sind, und ihre Untersuchung ist Teil der Berechnungstheorie (auch als Rekursionstheorie bekannt).

Der Hauptunterschied zwischen dem allgemeinen Begriff der Berechnung und Ihrem Beispiel (einer explodierenden Bombe) ist das, was berechnet wird. Was wird von Ihrer explodierenden Bombe berechnet? Ein weiterer Unterschied ist das rechnerische Mittel, aber man kann sich einen mechanischen Apparat vorstellen, der Bomben verwendet, um etwas legitimeres zu berechnen.

Ein weiterer Punkt ist, ob die klassischen Vorstellungen von Rechnen auf das zutreffen, was wir heute als Rechnen betrachten - nämlich die wechselseitige Interaktion zwischen Computer und Benutzer. Dies ist eine verbreitete Kritik, die gegen den klassischen Begriff der Berechenbarkeit gerichtet ist, obwohl die Interaktion mit den Werkzeugen der Berechnungstheorie modelliert werden kann (es ist einfach nicht das, was Sie im Unterricht lernen).

$A$$B$$x\in A$$y\in B$$x\in A$$x$

$x$$x$$y$$x$$y$

$t=0$$t=1$

Fazit: Jede Zuordnung definiert eine Berechnung. Jedes "Gerät", das eine Eingabe in die entsprechende Ausgabe umwandelt, führt diese spezifische Berechnung durch ("berechnet").

⁽¹⁾ Wir können die Diskussion auf diese Arten von Berechnungen ausweiten. Dies ist sinnvoll, wenn Sie an Funktionen denken, die nicht rekursiv sind, aber ich bevorzuge, nicht dorthin zu gehen.

Ich werde nicht versuchen zu definieren, was eine Berechnung ist, was von Luke Mathieson und Yuval Filmus ziemlich gut gemacht wurde.

Das Nachdenken über ein explodierendes Gerät als Berechnung hat mich jedoch zu einem wichtigen Nebenproblem geführt: Wenn die Explosion eine Berechnung ist, was berechnet sie dann? Abgesehen von einer Darstellung des Geräts nach seiner Explosion.

Was ich anstrebe, ist, dass wir ziemlich genau definieren können, was wir als eine Berechnung betrachten, und sogar, was als eine angesehen werden kann. Wir können eine Berechnung beschreiben. Aber können wir sagen, was es berechnet?

Berechnung ist, wie allgemein definiert, ein rein syntaktisches Spiel. Es ist ein Spiel mit physischen Strukturen, die nach präzisen Regeln transformiert werden. Da unser einziges Werkzeug (bis auf Standardtransformationen) zur Darstellung physikalischer Strukturen letztendlich die Zeichenfolge ist, wird die Berechnung als eine Art formale Transformation auf Zeichenfolgen definiert. Dies gilt für Turingmaschinen, Lambda-Kalkül, partielle rekursive Funktionen und andere weniger beliebte Modelle. Das Wort Kalkül (wie im Lambda-Kalkül) spiegelt tatsächlich diese Ansicht wider, da im Lateinischen Kalküle kleine Steine ​​sind, die zur Darstellung verwendet werden.

Was dies jedoch nicht sagt, ist, welche Bedeutung dieser Syntax zuzuordnen ist, was sie darstellt. Hier ist das Wenige, von dem ich denke, dass ich es verstehe, da ich kein Spezialist für solche Probleme bin (also überprüfe mich noch einmal). Das Problem wird durch die Modelltheorie abgedeckt .

Bei einem formalen Repräsentationssystem, das möglicherweise mit einer Logik (Axiome und Inferenzregeln) oder einem Berechnungssystem (Transformationsregeln) verknüpft ist, ist ein Modell der formalen Theorie eine mathematische Struktur mit Komponenten, die diesen Regeln folgen.

Dieselbe Berechnung oder genauer gesagt dieselbe Beschreibung einer Berechnung kann tatsächlich viele Modelle haben, die sehr unterschiedlichen Entitäten entsprechen.

Beispielsweise beschreibt ein GCD-Algorithmus eine Berechnung. Aber es kann auf natürlichen Zahlen oder auf Polynomen interpretiert werden.

Dies erinnert an Bertrand Russell'quote :

Mathematik kann als das Fach definiert werden, in dem wir nie wissen, wovon wir sprechen oder ob das, was wir sagen, wahr ist.

Bei der Berechnung ist die Situation so ziemlich die gleiche. Es ist ein formelles Spiel, bei dem die Bewegungen auf viele verschiedene Arten verstanden werden können. Tatsächlich besteht jedoch eine tiefe Verbindung zwischen der Mathematik, die formal durch axiomatische Systeme und die Berechnungstheorie definiert ist.

Berechnungen, Algorithmen, wurden definiert, um mathematische Probleme zu lösen, und viele der modernen Konzepte wurden von Logikern entwickelt, die versuchten, die Mechanismen zu verstehen, die es uns ermöglichen, Theoreme zu beweisen, ausgehend von Axiomen und der Anwendung von Inferenzregeln.

Um auf die Explosionsvorrichtung zurückzukommen, kann sie daher durchaus als Manipulation einer Darstellung, dh als Berechnung, ausgelegt werden. Aber es ist im Allgemeinen ziemlich schwer, ihm eine andere Bedeutung als sich selbst zuzuordnen.

Dies ist jedoch nicht immer der Fall oder war es nicht. Das Prinzip der analogen Berechnung beruht auf der Idee, dass unterschiedliche Darstellungssysteme für Berechnungen verwendet werden können, die auf eine präzise Art und Weise zusammenhängen. Dann können wir mit einem System berechnen, um eine Vorstellung davon zu bekommen, was das andere System (zu unhandlich, um es tatsächlich zu verwenden, zum Beispiel ein Universum :) in der entsprechenden Einstellung berechnen würde.

Ich beantworte gerne solche Fragen zur Terminologie in ethymologischen Begriffen.

Die Berechnung kommt also vom lateinischen Wort compŭtus, was wörtlich "Berechnung" bedeutet.

In lateinischen Sprachen wie Französisch, Italienisch, Spanisch oder Portugiesisch (unter anderem) wird diese Ethymologie mit "tale" (eine Geschichte) in Französisch (conte) in Spanisch (cuenta) / cuento in Portugiesisch (conta / conto usw.) geteilt.

Berechnen heißt also, zu berechnen und zu erzählen, wie diese Berechnung durchgeführt wurde.

Daher würde ich sagen, dass bei der Berechnung mathematische und logische Regeln verwendet werden, um eine bestimmte Information zu verarbeiten, sodass aus den Originaldaten neue aussagekräftige Informationen abgeleitet werden, die verfolgen, wie diese neuen Informationen erzeugt wurden (Prozessor, Speicher, Eingabe und Ausgang sind dann die Grundlagen beteiligt)