Was ist für die universelle analoge Berechnung erforderlich?

17

Welche Operationen müssen ausgeführt werden, um eine beliebige analoge Berechnung durchzuführen ? Wäre Addition, Subtraktion, Multiplikation und Division ausreichend?

Weiß auch jemand genau, welche Probleme mit analogen Berechnungen, nicht aber mit digitalen, zu lösen sind?

Matthew Matic
quelle
Vielleicht interessiert Sie der Begriff Turing-Vollständigkeit: en.wikipedia.org/wiki/Turing_completeness
Alex ten Brink
5
Was meinst du mit analoger Berechnung? Bitte geben Sie die Definition im Beitrag an oder verlinken Sie auf eine Definition.
Kaveh
@Kaveh Vor der Erfindung des digitalen Computers führten Wissenschaftler Berechnungen mit analogen Computern aus Operationsverstärkern durch.
Mohammad Al-Turkistany
1
@Mohammad, ich weiß, ich frage nicht nach Geschichte, ich frage nach einer Definition. Das OP sollte entweder ein bestimmtes Modell spezifizieren oder allgemeiner definieren, was ein analoges Berechnungsmodell ist.
Kaveh
4
„Universalität“ ist nur definierbar in Bezug auf eine bestimmte, formal, gut definierte Berechnungsmodell. Ohne ein solches Modell ist diese Frage einfach nicht zu beantworten.
JeffE

Antworten:

7

Leider gibt es im analogen Rechnen kein "universelles" Konzept der Universalität. In diesem Artikel von Delvenne wird jedoch ein einheitlicher Formalismus für die Universalität in diskreten (z. B. Turing Machines) und kontinuierlichen (z. B. Differentialgleichungen) dynamischen Systemen vorgeschlagen, und es werden einige in der Literatur untersuchte universelle Systeme besprochen . Hier ist ein Auszug aus dem Beitrag, der informell das Verfahren zum Nachweis der Universalität eines dynamischen Systems beschreibt:

Die meisten in Mathematik und Physik untersuchten dynamischen Systeme haben jedoch einen nicht abzählbaren Zustandsraum, z. B. zellulare Automaten, Differentialgleichungen, stückweise lineare Abbildungen usw. Beispiele für diese Systeme haben sich als universell erwiesen. Ihr Stopp-Problem wird auf folgende Weise von der Turing-Maschine imitiert. Wir wählen eine bestimmte zählbare Familie von Anfangszuständen und eine zählbare Familie von Endzuständen oder Endzustandsmengen. Dann wird dem Halteproblem ein Anfangszustand und ein Endzustand / eine Menge von Zuständen gegeben, ob die Trajektorie, die von dem Anfangszustand ausgeht, den Endzustand / die Menge von Zuständen erreicht. Speziellere Beispiele finden Sie in Abschnitt 7.

Jean-Charles Delvenne, Was ist eine universelle Rechenmaschine ?, Angewandte Mathematik und Berechnung, Band 215, Ausgabe 4, 15. Oktober 2009, Seiten 1368-1374

Mohammad Al-Turkistany
quelle
10

Ich denke nicht, dass die Frage beantwortet werden kann, es sei denn, wir haben eine Definition, um welche Art von Berechnungen es sich handelt.

Die Universalität eines Maschinenmodells für eine Berechnungsklasse bedeutet, dass jede Berechnung in dieser Klasse von einer Maschine berechnet werden kann. Solange Sie nicht die Klasse der "willkürlichen analogen Berechnungen" definieren, können wir nicht beantworten, was Universalität für sie bedeutet.

Jetzt geben die von Ihnen aufgelisteten Funktionen nur noch Polynome und deren Quotienten an, was eine eher kleine Klasse von reellen Funktionen ist. Sie können nicht einmal einfache Funktionen wie , , , ... mit berechnen Sie.2xxx


Wenn Ihre Frage lautet, ob es physische Systeme gibt, die ausgehend von einem Anfangszustand irgendwann einen anderen Zustand erreichen, und wenn dies immer berechenbar ist, hängt die Antwort davon ab, um welche Art von Physik es sich handelt und was es sich handelt, sie einzurichten eine Erstkonfiguration und Beobachtung des Ergebnisses usw.

Wenn wir nur mathematisch über die klassische Physik sprechen (wir können jede Anfangskonfiguration auf unendliche Präzision einstellen und ohne Überlegungen zu Dingen wie Energie, die zum Einrichten der Konfiguration benötigt wird, und das Beobachten des Ergebnisses ist aus mathematischer Sicht ähnlich), dann ist es bekannt Lange Zeit gab es Differentialgleichungen über berechenbare Funktionen, deren Lösung jedoch nicht berechenbar war, siehe Marian B. Pour-El und J. Ian Richards, " Computability in Analysis and Physics ", 1989.

Ein interessanter Fall ist, wenn das n-Körper-Problem berechenbar ist (und wenn ich mich richtig erinnere, lautet die Antwort nein, zumindest für ).n>4

Wenn wir nur die Gleichheit von zwei reellen Zahlen prüfen können, ergibt sich eine Funktion, die hinsichtlich typischer Informationstypologien über reelle Zahlen nicht stetig ist und daher von einer Turing-Maschine nicht berechnet werden kann, da jede Funktion (einschließlich höherer Typfunktionen) einer Turing-Maschine entspricht kann berechnen ist kontinuierlich (bezüglich der Topologie der Informationen).

Kaveh
quelle
4

TL; DR: Wenn Sie mit "analogen Computern" Differentialanalysatoren meinen , lautet die Antwort Addierer, konstante Einheiten und Integrator. Bournez, Campagnolo, Graça und Hainry haben im Jahr 2006 (siehe paywalled / kostenlosen Abdruck ) , dass ein idealisiertes Modell davon erlaubt es, all berechenbaren Funktionen im Rahmen der zur Berechnung berechenbarer Analyse und dieses Modell braucht nur diese drei Arten von Einheiten.

Transzendentale Funktionen

Die Menge der von Ihnen vorgeschlagenen Operationen (Addition, Multiplikation, Subtraktion und Division), die auch durch die Wurzelgleichung vervollständigt wird, reicht definitionsgemäß nicht aus, um eine transzendentale Funktion zu berechnen . Transzendentale Funktionen beinhalten sehr häufige Funktionen wie , , . Wie nachstehend erläutert, ermöglichen einige analoge Computermodelle die Berechnung transzendenter Funktionen und im Grunde aller reellen Funktionen, die von einer Turing-Maschine berechnet werden können.SündeexpLog

Analoge Rechenmodelle

Wie von anderen betont, ist das Konzept der „universellen Berechnung“ für analoge Computer weniger klar als für Standardcomputer, bei denen in den 1930er Jahren ein anderer natürlicher Begriff der Berechenbarkeit in verschiedenen Rechenmodellen als gleichwertig befunden wurde ( Einzelheiten finden Sie auf der Wikipedia-Seite zu Church Turing Thesis ). .

Um eine solche Universalität zu definieren, sollte man zuerst ein gutes Modell für analoge Berechnungen definieren, und es ist eine schwierige Aufgabe, da das Modell idealisiert und natürlich genug sein sollte, um nützlich zu sein, aber seine Idealisierung sollte dem Modell keine unrealistische Kraft verleihen Modell. Ein Beispiel für eine so gute Idealisierung ist das Endlosband von Turing-Maschinen. Das Problem mit analogen Computern besteht in reellen Zahlen, die es ermöglichen könnten, unvernünftige Dinge wie die Zeno-Maschine zu erstellen . Es wurden jedoch mehrere solche Modelle vorgeschlagen und in der Literatur verwendet (Der GPAC ist das Hauptthema dieser Antwort, aber ich versuche, in der folgenden Liste vollständig zu sein, ohne einen Hypercomputer ):

Leistung des GPAC-Modells

Γζy(t)=Γ(t)Es schien lange Zeit, als sei ein solcher analoger Computer nicht „universell“, da er keine angemessenen berechenbaren Funktionen erzeugen kann, die von Mathematikern verwendet werden.

fy(t)f(x)xγζ.

Bournez, Graça und Pouly haben 2013 gezeigt, dass diese analogen Computer eine Turing-Maschine effizient simulieren können ( S.181 eines großen PDFs ), und 2014, dass die Komplexitätsklassen P und NP in diesem Modell gleichwertig sind.

Frédéric Grosshans
quelle
3

Wäre es sinnvoll vorzuschlagen, dass ein universelles analoges System durch ein unendliches neuronales Netz modelliert werden könnte, dh, alle anderen Ein- / Ausgabewerte des analogen Systems können für eine bestimmte Operation auf ein angepasstes neuronales Netzwerk repliziert und Operationen nach Bedarf verkettet werden?

Während ich diesen Gedanken selbst formuliert habe, hat eine nachfolgende Suche einen ähnlichen Vorschlag ergeben:

Was dabei herauskommt, ist eine Church-Turing-ähnliche These, die auf dem Gebiet der analogen Berechnung angewendet wird und das neuronale Netzwerkmodell anstelle der digitalen Turing-Maschine enthält (siehe hier ).

Dann brauchen Sie wohl nur die primitiven Operationen, um den Wert von einem Knoten auf einen anderen zu verschieben. Aus der Manschette, die plus, minus und dividieren könnte, um das Verhältnis zwischen den Verbindungen zu erhalten.

Betrachten Sie nun die unlösbaren Probleme, wenn neuronale Netze erfolgreich angewendet wurden oder aufgrund der Implementierung auf einem diskreten Computer nicht ausreichend funktionieren.

(und entschuldige mich, wenn meine fast laienhafte Meinung zu diesem Thema offensichtlich ist)

Jayfang
quelle