Gibt es einen Zusammenhang zwischen dem Halteproblem und der thermodynamischen Entropie?

31

Alan Turing schlug ein Modell für eine Maschine vor (die Turing Machine, TM), die berechnet (Zahlen, Funktionen usw.) und den Haltesatz bewies .

Ein TM ist ein abstraktes Konzept einer Maschine (oder eines Motors, wenn Sie möchten). Der Haltesatz ist ein Unmöglichkeitsergebnis. Eine Carnot-Engine (CE) ist ein abstraktes Konzept einer Wärmekraftmaschine, und Carnot hat das Carnot-Theorem bewiesen , ein weiteres Unmöglichkeitsergebnis im Zusammenhang mit der thermodynamischen Entropie.

Wenn ein TM physikalisch realisierbar ist (mindestens so viel wie ein CE oder nicht?), Gibt es eine Abbildung oder Darstellung oder einen "Isomorphismus" von TM oder CE, der es ermöglichen könnte, diese Ergebnisse zu vereinheitlichen und zusätzlich mit Entropie in Verbindung zu bringen?

Es gibt natürlich Formulierungen von TM und des Halting-Theorems in Bezug auf algorithmische Informationstheorie (z. B. Chaitin, Kolmogorov usw.) und Entropie (in diesem Zusammenhang). Die Frage fragt nach dem physikalischeren Konzept der Entropie (wenn im Verlauf einer möglichen Antwort algorithmische Entropie entsteht, ist dies in Ordnung, aber es ist nicht das, was die Frage genau fragt).

Man kann auch eine andere Frage in physics.se prüfen , die die Quantenunsicherheit mit dem 2. Hauptsatz der Thermodynamik in Beziehung setzt. Siehe auch: eine algebraische Charakterisierung der Entropie , eine algorithmische Charakterisierung der Entropie , eine Übersicht und Zusammenhänge zwischen verschiedenen Entropieformulierungen

Nikos M.
quelle
1
Es gibt einen Sinn, in dem die beschriebenen Konzepte genau entgegengesetzt sind . Theormodynamische Gesetze über den Anstieg der Entropie schließen eine Perpetuum Motion Machine aus . Eine nicht haltende Maschine ist eine Maschine mit ständiger Bewegung .
vzn
Ja, ich verstehe, wenn man den Zustand ohne Unterbrechung als Perpetuum Mobile (der 2. Art?) umwandelt, ist dies genau im Sinne der Frage, aber ist es das, was der Stoppsatz besagt? Es heißt, wir wissen nicht, ob es anhält oder nicht, wegen "Kreisförmigkeit", schön
Nikos M.
Ein Vorschlag, "Thermodynamik" und / oder "Thermodynamik-Berechnung" als neue Tags in CS.se hinzuzufügen? Ich bin mir nicht sicher, ob ich es alleine schaffen kann (wahrscheinlich), aber lass uns andere Meinungen hören
Nikos M.

Antworten:

11

Ich bin kein Experte auf diesem Gebiet, aber ich glaube, Sie werden an reversiblem Computing interessiert sein . Dies beinhaltet unter anderem die Untersuchung der Beziehung zwischen physikalisch reversiblen Prozessen und logisch reversiblen Prozessen. Ich denke, es wäre fair zu sagen, dass die "Gründer" des Feldes Ralph Landauer und Charles H. Bennett (beide von IBM Research, denke ich) waren / sind.

Es geht auf Quantencomputing und Quanteninformationstheorie ein, untersucht aber auch Fragen wie "Was sind die Grenzen der Berechnung in Bezug auf Zeit, Raum und Energie?" Es ist bekannt (wenn ich mich richtig erinnere), dass Sie die Energie, die für eine reversible Berechnung erforderlich ist, beliebig klein machen können, indem Sie eine beliebig lange Zeit in Anspruch nehmen. Das heißt, Energie Zeit (= Aktion ), die erforderlich ist, um eine reversible Berechnung durchzuführen, kann zu einer Konstanten gemacht werden. Dies ist bei nicht umkehrbaren Berechnungen nicht der Fall.×

Viele der Menschen, die in diesem Bereich studieren, beschäftigen sich auch mit Quantencomputern und digitaler Physik (die Idee, dass das Universum ein großer quantenmolekularer Automat ist). Die Namen der Forscher sind Ed Fredkin , Tommaso Toffoli und Norm Margolus .

Diese Fragen sind für die Informatik absolut aktuell . Nicht nur für die Theorie (die sowohl coole Mathematik als auch coole Physik beinhaltet), sondern auch für Ingenieure, die die ultimativen Grenzen der Berechnung kennen wollen. Gibt es ein Minimum an Volumen oder Energie, um ein bisschen Information zu speichern? Die zur Durchführung einer reversiblen Berechnung erforderliche Aktion kann konstant sein. Gibt es jedoch Grenzen für diese Konstante? Dies sind wichtige Kenntnisse für Ingenieure, die versuchen, die Grenzen des Möglichen zu erweitern.

Wandering Logic
quelle
Ja, es gibt eine Beziehung zur Thermodynamik der Berechnung (Bennett, Landauer et al.), Aber mehr Fragen in Bezug auf den Haltesatz und / oder die Abbildung zwischen TM und CE (wie in Frage), aber eine gute Antwort
Nikos M.
1
Ah, du hast recht. Ich stimme meine Antwort ab. Die Kommentare unter Ihrer Frage, die besagten, dass es nicht zum Thema gehörte, ließen mich rot sehen, und ich antwortete hauptsächlich darauf. Zur Beantwortung Ihrer eigentlichen Frage: Schauen Sie sich die Church-Turing-These an. Angenommen, Sie glauben, dass und auch, dass die Mathematik alles in der Natur modellieren kann, dann ist das Halteproblem ein physikalischer Unmöglichkeitssatz.
Wandering Logic
Ich denke , die Church-Turing - These , dass physikalische Berechnung ist effektive Berechnung in der Tat notwendig sein könnte, einen Blick auf diesem Papier auch
Nikos M.
5

Ich bin nicht mit Carnots Theorem vertraut, außer dem, was ich gerade in Wikipedia gelesen habe, aber selbst aus dieser flüchtigen Einführung ergibt sich ein Zusammenhang in der Struktur der Beweise, und das könnte für Sie interessant sein, da es sich um eine Beweistechnik handelt das gilt in vielen bereichen.

Sie sind beide widersprüchliche Beweise, mit denen gezeigt werden soll, dass kein Objekt in einer bestimmten Klasse eine Eigenschaft hat. Sie nehmen an, dass eine Instanz diese Eigenschaft tatsächlich hat, und zeigen dann, dass ein Widerspruch folgt.

Das Problem des Anhaltens ist insofern interessant, als der Widerspruch aus einer Selbstinteraktion in Bezug auf die bestimmte Instanz (die eine Maschine M ist, die bestimmen kann, ob eine beliebige Maschine mit einer bestimmten Eingabe anhält) entsteht. Insbesondere konstruieren Sie eine neue Maschine, die M als Komponente enthält, und führen dann die neue Maschine M zu.

Jemand mit mehr Wissen über Carnots Theorem könnte es näher erläutern (wozu ich nicht befugt bin), aber es scheint, dass der Widerspruch von der Art der Wärmekraftmaschine herrührt, die Sie bauen könnten, wenn Sie eine Instanz mit der Eigenschaft zur Hand hätten.

In beiden Fällen geht es also um die Konstruktion von:

  • Angenommen, ein X hat die Eigenschaft P.
    • Erstellen Sie von X aus das verwandte Y.
    • Die Beziehungen zwischen X und Y sind widersprüchlich.
  • Daher hat kein X die Eigenschaft P.

Es scheint jedoch einen Unterschied darin zu geben, dass der Widerspruch im Fall des Halting-Theorems ein reiner logischer Widerspruch ist und in jeder Einstellung der klassischen Logik widersprüchlich wäre. Der Carnot-Satz ist meines Wissens nur in Bezug auf den zweiten Hauptsatz der Thermodynamik widersprüchlich. Aus logischer Sicht ist dies ein Axiom. Wenn Sie also eine andere Axiomatisierung wählen würden, in der das zweite Hauptsatz der Thermodynamik nicht gilt, wäre Carnots Theorem kein Theorem, da der Widerspruch nicht existieren würde. (Wie eine Formalisierung der Thermodynamik ohne den zweiten Hauptsatz aussehen würde, ist die Art von Frage, die Geometer zu nichteuklidischer Geometrie führte.)

Joshua Taylor
quelle
Dieses Papier bietet viel in die Richtung, die Sie erwähnen, imo. Sehr relevant finde ich auch die Zirkularität (oder Diagonalisierung) der Argumente. Es gibt Forschungsrichtungen, die irreversible logische Transformationen mit irreversiblen thermodynamischen Prozessen verbinden (z. B. Landauers-Prinzip und deren Einwände). Es gibt Einwände gegen einige Aussagen des 2. Gesetzes, aber man kann Formulierungen finden, die noch gültig sind (zB Prigogines Arbeit)
Nikos M.
Wie diese Verbindung zustande kommen könnte, lesen Sie auch in den Kommentaren zur vorherigen Antwort (nur aus Plausibilitätsgründen)
Nikos M.,
Bezüglich anderer Formulierungen des 2. Gesetzes (noch allgemeiner und für Nichtgleichgewichtsprozesse) können Sie die Aussage von Caratheodory in Bezug auf Phasenraum und Geometrie, Prigogins Arbeit über Nichtgleichgewichtssysteme und die Hatzopoulos-Gyftopoulos-Beretta- Formulierung (mit weiteren Verbindungen zu) überprüfen Quantenmechanik)
Nikos M.
In gewisser Hinsicht gibt es so viele Facetten der Entropie wie es Facetten von Goedels Theoremen gibt ( wie in Turings Stoppsatz, Tarskis Undefinierbarkeitssatz , Rossers Satz , Chaitins Unvollständigkeitssatz ), gibt es sogar einen kategorietheoretischen Beweis eines "Allgemeinen" Goedel-Theorem ", das alle vorhergehenden umfasst, die auf festen Punkten basieren
Nikos M.
Auch wenn eine Verbindung zwischen dem Halteproblem und der thermodynamischen Entropie in der Form von if und when the 2md Law bewerkstelligt wird, dann ist es immer noch so gut wie diese Frage (im Zusammenhang mit dem Einwand, dass das 2. Gesetz wie das folgende sein könnte) 5. Postulat auf Parallelen in der euklidischen Geometrie)
Nikos M.
4

IANAPhysiker, aber ich sehe keine Verbindung. Turingmaschinen sind Objekte der reinen Mathematik und die Unentscheidbarkeit des Halteproblems ist unabhängig von jeglicher physischen Realisierung von irgendetwas.

David Richerby
quelle
2. Gesetz Unmöglichkeitsergebnisse haben vieles gemeinsam mit (mathematischen) logischen Problemen und Zirkularitäten, vielleicht besteht dort ein Zusammenhang?
Nikos M.
1
Man müsste mehr ins Detail gehen: Wie gesagt, ich bin kein Physiker. Aber ich sehe nicht ein, wie physikalische Gesetze einen Einfluss auf ein Konstrukt haben können, das unabhängig von der physikalischen Realität existiert.
David Richerby
Sie haben einen Punkt dort, ich kann viele erkenntnistheoretische Gründe geben, warum dies sehr plausibel ist (zB die Mathematik, die wir von der Welt abhängen, die wir leben , a-la-Einstein), aber ich möchte etwas darüber hinaus, wenn ich eine bereite Antwort hätte würde wahrscheinlich einen Artikel veröffentlichen :)
Nikos M.
2
@vzn Wir verwenden das Wort "Zeit" für die Anzahl der Schritte, die die Maschine ausgeführt hat, und "Leerzeichen" für die Anzahl der verwendeten Bandzellen, aber diese Wörter wurden ausgewählt, um unsere physische Intuition als physische Wesen anzusprechen. "Zeit" ist jedoch nur ein Index für eine Folge von Konfigurationen, und Raum ist nur ein Index für eine Folge von Symbolen. Stellen Sie sich zum Beispiel eine Turing-Maschine vor, bei der der Kopf gerade nach rechts abschießt. Es verwendet unendliche "Zeit" und unendlichen "Raum", aber Sie können das in einer endlichen Menge von Echtzeit und realem Raum
herausfinden
2
Sicher, aber die Tatsache, dass wir Turing-Maschinen als interessante Objekte betrachten, kann etwas mit der Physik zu tun haben.
Gilles 'SO- hör auf böse zu sein'
1

Diese vielfältige, themenübergreifende Frage ist nicht einfach zu beantworten und berührt aktive Bereiche der TCS-Forschung. Es ist jedoch eine seltene Frage nach einer Verbindung zwischen Physik und TCS, die mich im Laufe der Jahre interessiert hat. Es gibt ein paar verschiedene Richtungen, um dies zu tun. Die grundlegende Antwort ist, dass es sich um eine "offene Frage" handelt, die jedoch von aktiver / moderner Forschung aufgegriffen und auf Zusammenhänge hingewiesen wird.

  • Es gibt einige überraschende / tiefgreifende, unentscheidbare Probleme aus der fortgeschrittenen Physik. zum Beispiel aus dynamischen Systemen. Habe jedoch nicht gesehen, dass dies mit der Entropie per se verbunden ist, aber die Entropie ist mit allen physikalischen Systemen verbunden (z. B. kann man dies in der Chemietheorie sehen), so dass es zumindest eine indirekte Verbindung geben muss.

  • Entropie zeigt sich zwar in CS, aber mehr in Form von Informationstheorie und Codierungstheorie. Die Geburtsstunde der Codierungstheorie war die Definition / Analyse der Entropie von Kommunikationscodes durch Shannon. Probieren Sie diese großartige Online-Referenz Entropy & Information Theory von Gray

  • Entropie wird auch manchmal mit der Messung der Zufälligkeit in PRNGs in Verbindung gebracht. In dem berühmten "Natural Proofs" -Papier von Razborov / Rudich gibt es einen Zusammenhang zwischen Komplexitätsklassentrennungen (z. B. P =? NP) und PRNGs . zu diesem thema wird weiter geforscht.

  • Sie erwähnen die Thermodynamik und ihre Verbindung zu TCS. Es gibt einen tiefen Zusammenhang zwischen der Magnetisierung in Spingläsern in der Physik und NP-vollständigen Problemen, die am SAT-Übergangspunkt untersucht wurden. Dort (wieder) ist dem physikalischen System eine Entropie zugeordnet, die jedoch wahrscheinlich eher im physikalischen Kontext als im TCS-Kontext untersucht wurde.

vzn
quelle
Ich
siehe auch CS defn of entropy stackoverflow
vzn
Es ist interessant, "out of the box" denken zu können (zumindest manchmal). Haben Sie sich mit Bennets Arbeiten zur Thermodynamik der Berechnung befasst? Die Motivation hinter dieser Frage ist zu zeigen, ob das Stopp-Theorem als eine Konsequenz der Thermodynamik angesehen werden kann (mit einem geeigneten Modell oder einer geeigneten Darstellung, zumindest für einige Fälle). Ich denke, es wäre wirklich interessant, wenn dies so oder so geregelt werden könnte
Nikos M.,
Vielleicht haben Sie diese Artikel bereits gesehen: philsci-archive.pitt.edu/313/1/engtot.pdf und cc.gatech.edu/computing/nano/documents/…
Nikos M.
Die meisten Konzepte der "Entropie", wie sie in der Informatik verwendet werden, beziehen sich entweder auf Shannons Informationstheorie oder auf die algorithmische Informationstheorie nach Kolmogorov / Chaitin / Solomonov. Dies wird bereits in der Frage erwähnt und ist sehr wichtig. Die einzige Verbindung zur thermodynamischen Entropie, die ich kenne (die mit der inf. Entropie in Verbindung gebracht werden kann), ist die Thermodynamik der Berechnung. Die Frage bezieht sich auf die Thermodynamik der Berechnung, aber auf eine andere Weise
Nikos M.
1

Es gibt ein einfaches Gedankenproblem, das manchmal als Einführung in nichtkonventionelle Computerparadigmen verwendet wird:

Sie haben zwei Glühbirnen und ihre jeweiligen Ein-Aus-Schalter. Jemand öffnet und schließt beide Lichter nacheinander. Wie stellen Sie fest, welches zuerst und welches zuletzt geschlossen wurde? Bestimmen Sie, wie oft Sie die Lichter mindestens öffnen müssen, um dieses Problem zu beheben.

Die meisten Informatiker versuchen normalerweise, eine auf Boolescher Logik basierende Lösung zu finden. Die Antwort lautet (mindestens eine davon): Durch Berühren der Glühbirnen und Erkennen der heißeren Glühbirnen.

Wärmebasierte Paradigmen existieren in der Informatik: Simuliertes Tempern ist ein bekannter Algorithmus (D-Wellen-Quantencomputer ist das Quanten-Gegenstück des Algorithmus).

Besteht nun ein Zusammenhang mit dem Halting-Problem?

Die klassische Arbeit von Chaitin und Calude zum Halting-Problem über das Konzept der Omega-Zahlen kann mit der probabilistischen Formulierung des Halting-Problems verknüpft werden. Es ist die neuere Abhandlung über das Problem, die ich mir vorstellen kann ... und keine klare Beziehung zur Entropie (thermodynamisch). Wenn die Informationsentropie (im Sinne von Shannon) für Sie gut ist, codiert die Omega-Zahl das Halting-Problem im Sinne einer Shannon-Bindung auf die prägnanteste Weise.

Kurz gesagt, eine Omega-Zahl ist die Wahrscheinlichkeit, dass ein Zufallsprogramm anhält. Die Kenntnis der Konstanten würde die Aufzählung aller gültigen mathematischen Aussagen (Wahrheiten, Axiome usw.) ermöglichen und ist nicht berechenbar. Calude berechnete eine Version von Omega, indem er das einheitliche Wahrscheinlichkeitsmaß durch ein Maß änderte, das umgekehrt proportional zur Länge eines Zufallsprogramms war, und indem er Präfix-freie Kodierungen verwendete. Man könnte also von Chaitins Omega und Caludes Omega sprechen.

user13675
quelle
Gute Antwort, der Teil, der sich auf die Wärme der Glühbirnen bezieht, wird oft als Verbindung zwischen Informationsentropie und thermodynamischer Entropie verwendet (ein Sinn, der Jaynes 'Ansicht als subjektive Unsicherheit zuwiderläuft). Mein eigener Gedanke wäre, die Argumentation auf der Zirkularität beider Konstrukte zu gründen und durch eine (geschickte?) Kaskade eine Implikation (zumindest in einer Richtung) zu schaffen
Nikos M.
Eine ähnliche Überlegung wird bei Batterien (anstelle von Glühbirnen) verwendet, um festzustellen, welche Batterien entladen sind ...
Nikos M.
0

Ja !, seltsamerweise habe ich darüber nachgedacht. Hier ist die Idee:

Erster Schritt

Modellieren Sie den Maxwell's Demon als Computerprogramm. Dann Wie kam Dämon Teilchen der Geschwindigkeit und Position kennen , bevor die Tür für die Auswahl öffnen?

Angenommen, der Dämon kann die Geschwindigkeit, mit der Partikel auf die Tür treffen, nicht messen. Warum? weil dies die Geschwindigkeit der Partikel verändern würde, muss der Dämon herausfinden, bevor er sie öffnet, ohne hinzuschauen, ohne zu messen. Um fair zu sein, werden wir den Dämon im Voraus über die Spielregeln informieren, dh ihn mit Bewegungsgesetzen, Wechselwirkungen von Partikeln und Anfangsbedingungen ausreichend vom physikalischen / dynamischen Modell versorgen.

Zweiter Schritt

Nun modellieren Sie das Gas der Partikel auch als Computerprogramm, in dem für jedes Partikel derselbe Code ausgeführt wird, den der Dämon erhalten hat. Das Gas berechnet also ein Ergebnis aus den Anfangsbedingungen ): Nämlich "ein Teilchen mit der richtigen Geschwindigkeit ist an der Tür", die Entscheidung, die wir dem System mit Ja / Nein stellen, lautet "Haben ein Teilchen die richtige Position und genug Geschwindigkeit?". Wenn dies der Fall ist, könnte die Tür geöffnet werden und das schnelle Teilchen kann in die Hochtemperaturseite des Raums gelangen und dort neue Ausgangsbedingungen einstellen (werden diese aufeinander folgenden Probleme eine Antwort haben? oder für immer laufen?)

Es wird eine Zeit geben, in der es kein Teilchen gibt, das schnell genug ist, um die Grenze zu überschreiten. Es wird also eine Zeit geben, in der der Code für fast jeden Schwellenwert für immer ausgeführt wird (nicht anhalten).

Demon möchte das Ergebnis wissen, das vom Gas berechnet wird, aber das Ergebnis ist in gewissem Sinne möglicherweise im Quellcode der Partikelgesetze enthalten, zuzüglich der Anfangsbedingungen. Natürlich müssen wir dieses Programm ausführen, um es zu wissen. Wenn Demon dasselbe Programm ausführen und auf die richtige Geschwindigkeit am Ausgang warten, könnte das Programm anhalten oder für immer laufen (aber wir nehmen auch an, dass Demon nicht mehr Rechenleistung als das Gas hat, sodass es nicht in der Lage ist, die zu bestimmen Tür öffnet pünktlich).

Daemon könnte versuchen, die Programmausgabe herauszufinden (oder ob sie angehalten wird), indem er die Quelle und Eingaben betrachtet, ohne sie auszuführen , aber es ist, als würde er versuchen, das Anhalten-Problem zu lösen. Warum? Da Demon nicht weiß, welche Gesetze und Anfangsbedingungen es geben wird, sollte Demon darauf vorbereitet sein, alle Gesetze und Anfangsbedingungen zu lösen, und wir wissen, dass es im Allgemeinen nicht möglich ist, wird es ein Orakel brauchen, wenn es könnte Sei genug, um einen Dämon zu bauen, der aus dem Nichts Energie erzeugt. (Selbst wenn man die Gesetze und die Ausgangsbedingungen kennt, ist beides schon schwer genug zu wissen)

Dieses Gedankenexperiment kann verknüpfen, wie eine Verringerung der Entropie durch Computer in gewisser Weise durch das Problem des Anhaltens begrenzt werden könnte , als ein Problem, das die Ergebnisse im Allgemeinen vorwegnimmt.

(Manchmal scheinen alle Limits gleich zu sein.)

Mehr über Partikelgesetze

Die Gesetze der Teilchen sind nicht das Hauptthema dieses Gedankenexperiments, diese Gesetze könnten quantenmßig oder klassisch sein, aber wir müssen die Tatsache der Komplexität der Gesetze und Anfangsbedingungen berücksichtigen, die Komplexität der Anordnung der Teilchen ist nicht begrenzt, und sie könnten es haben eine Menge zusätzliche Komplexität (in einem extremen Beispiel für Anfangsbedingungen könnten Sie sogar einen ganzen Computer einsetzen, der Partikel gemäß einem internen Quellcode abfeuert, und diesen Code dem Daemon geben).

Hernan_eche
quelle
1
Ich verstehe den Zusammenhang mit dem Halteproblem nicht. Erstens scheinen Sie neu definiert zu haben, was es bedeutet, dass eine Maschine anhält. Zweitens scheint es nur ein Programm zu geben (den Gasteilchensimulator). Es ist durchaus möglich zu beweisen, dass ein festes Programm stoppt oder nicht, ohne die Unentscheidbarkeit des allgemeinen Stopp-Problems zu verletzen .
David Richerby
Über Anhalten, es hat das Anhalten nicht neu definiert, hier ist das Anhalten des Programms wie immer, wenn das Programm endet und Sie eine Ausgabe erhalten, daher wird die Ausgabe als der genaue Moment definiert, in dem ein Partikel mit der richtigen Geschwindigkeit auf die Tür auftrifft , und Sie könnten eine Tür bauen, die sie erkennt, damit sie anzeigt, wenn das Programm anhält (und das Programm dann unter diesen Anfangsbedingungen für eine andere Ausgabe erneut ausgeführt wird). Daemon möchte wissen, wann er anhält, kann aber nicht wissen, ob er anhält.
Hernan_eche
1
Turingmaschinen können das Halteproblem für Turingmaschinen nicht entscheiden. Anscheinend haben Sie das Stopp-Problem wie folgt neu definiert: "Tut eines dieser Gasmoleküle jemals X?", Ein völlig anderes Problem als "Hält diese Turing-Maschine an, wenn sie mit dieser Eingabe gestartet wird?" Turings Beweis für die Unentscheidbarkeit des Problems des Anhaltens der Turing-Maschine sagt nichts darüber aus, ob eine Turing-Maschine berechnen kann, ob ein Gasmolekül jemals X kann.
David Richerby
Davids Kommentar ist korrekt, da er nicht direkt mit dem Halteproblem zusammenhängt. Es ist jedoch ein Argument, das dem Geist der Frage folgt
Nikos M.
1
@Gilles, danke, dass du das bemerkt hast, ich stimme dem zu, falls nötig, wird ein Chat erstellt. Ich würde es vorziehen, wenn diese Kommentare trotzdem hinterlassen würden, da sie sich sowohl auf die Frage als auch auf die spezifische Antwort (wie entwickelt) beziehen
Nikos M.
-1

Sehr fesselnde Frage, und wir werden sehen, dass Ihr Denken richtig ist .

Lassen Sie uns zunächst sehen, was das zweite Prinzip der Thermodynamik besagt.

Die Entropiefunktion wird im 2. Hauptsatz der Thermodynamik verwendet. Es stammt aus Carnots Theorem, das besagt, dass Prozesse, die in Dampfmaschinen ablaufen, einen Wirkungsgrad haben, der niedriger oder bestenfalls gleich dem der entsprechenden "umkehrbaren" Maschine ist (was übrigens über die 150 Jahre Thermodynamik als instabiles Konzept erscheint). Carnot hat die Entropiefunktion nicht selbst geprägt, aber zusammen mit Clausius sagen sie:

Da es keine Perpetuum-Maschine gibt, können wir eine Funktion S namens Entropie aufbauen, die makroskopische thermodynamische Maße in eine bestimmte Gleichung einschränkt, nämlich diese S (V, T, P usw.) = 0

Beachten Sie, dass diese Gleichung nichts anderes ist als die Gleichung einer Hyperfläche im Raum thermodynamischer Maßnahmen.

Betritt Carathéodory.

Carathéodory ist ein deutscher Mathematiker und möchte, wie alle Mathematiker, aus Carnots und Clausius 'Überlegungen einige Axiome extrahieren, die es ihm ermöglichen würden zu klären, was der zweite Hauptsatz wirklich ist geht. Mit anderen Worten, er möchte die Thermodynamik reinigen, um genau zu wissen, was Entropie ist.

Nachdem er eine bestimmte Anzahl von Axiomen aufgelistet hat, schafft er es, sein zweites Gesetz zu formulieren, das besagt (mehr oder weniger):

Es gibt einige adiabatische Prozesse. Oder prosaischer, wenn Sie zurückkehren möchten, ist es manchmal nicht genug, allein zu arbeiten. Du brauchst ein bisschen Wärme.

Nun, das scheint sich sehr von der Formulierung von Clausius zu unterscheiden! Aber in Wirklichkeit ist es das nicht. Alles, was Carathéodory tat, war, die Reihenfolge der Wörter zu ändern, ähnlich wie Mathematiker 2000 Jahre lang mit Euklides 5. Axiom spielten und viele verschiedene Formulierungen für dieses Axiom erstellten. Und wenn Sie einen Schritt zurücktreten, sollten Sie von Carathéodorys Aussage zum zweiten Gesetz nicht allzu überrascht sein. Tatsächlich führt Carathéodorys zu genau derselben Entropiefunktion und Hyperflächengleichung S (V, T, P usw.) = 0

Denken Sie gut über Carnots Theorem nach. Als Mathematiker sollten Sie nicht zu zufrieden sein mit der Art und Weise, wie Carnot zugibt, dass Perpetuum-Maschinen nicht existieren. Tatsächlich würden Sie als Mathematiker eher so etwas sehen:

Es gibt eine Entropiefunktion S, die makroskopische Maßnahmen einschränkt, WENN UND NUR WENN es keine Perpetuum-Maschinen gibt. "

JETZT hast du einen Satz. Und was steht da? Solange es kein isoliertes mechanisches System gibt, das unendlich viel Energie erzeugt und Sie in einen beliebigen Zustand führen könnte, finden Sie eine Entropiefunktion. Ein isoliertes mechanisches System ist ein adiabatischer Prozess. Daher Carathéodorys Formulierung: Kein adiabatisches System kann Sie irgendwohin führen. Manchmal braucht man etwas Wärme.

Wir sind also nicht nur sicher, dass Carathéodorys richtig ist, sondern auch, dass seine Formulierung ziemlich einfach ist.

Wo haben Sie nun den Eindruck, dass das zweite Gesetz à la Carathéodory dem Halteproblem ähnlich ist?

Machen Sie einen Schritt zurück zu Carathéodorys Aussage. Alles was es sagt ist, dass sobald Sie ein isoliertes mechanisches System haben, mit dem Sie aufhören, sich zu vermischen, Sie keinen Zustand erreichen können, den Sie wollen.

Klingt das nicht GENAU nach dem Problem des Stillstands? Das heißt, wenn Sie alle Axiome Ihrer Theorie geschrieben und alle möglichen Übergänge festgelegt haben, gibt es Probleme, die Sie nicht lösen können. Manchmal müssen Sie weitere Axiome hinzufügen.

Wenn Sie wirklich tief gehen und die Formulierung von Carathéodory codieren möchten, führt dies zu demselben Code wie das Stopp-Problem bei adiabatischen Prozessen anstelle von Turing-Maschinen und zu Zuständen anstelle von Problemen.

Was denkst du?

HINWEIS: Ich habe meine Antwort fast vollständig bearbeitet, sodass die folgenden Kommentare nicht mehr mit dem übereinstimmen, was sie jetzt enthalten.

Hieronymus
quelle
1
"Reis gibt an, dass keine Turing-Maschine auf unbestimmte Zeit eine nicht triviale Eigenschaft hervorbringen kann." Das ist keine Umschreibung von Reis, die ich wiedererkenne. Was meinst du?
David Richerby
1
Was meinst du mit "unendlich produzieren eine nicht-triviale Eigenschaft"?
David Richerby
Ein bisschen verdreht. Laut Rice kann nicht nachgewiesen werden, dass ein TM eine bestimmte Funktion implementiert. Wenn nun ein TM A auf unbestimmte Zeit eine nicht-triviale Eigenschaft (N-TP) erzeugt, bedeutet dies, dass es für JEDEN Eintrag ein N-TP erzeugt. Wie kann das in der Praxis wahr sein? Nun, es scheint der einzige Weg dafür zu sein, einen undefinierten Eintrag e zu betrachten und zu zeigen, dass sein A (e) ein N-TP hat. Dies würde wiederum bedeuten, dass es uns gelingen würde, zu beweisen, dass die Maschine einen N-TP produziert. Und wir wissen, dass das nicht möglich ist. Tatsächlich postuliere ich also, dass es äquivalent ist zu sagen: "A produziert auf unbestimmte Zeit ein N-TP" und "Ich kann zeigen, dass A ein N-TP produziert"
Hieronymus
"Unendlich eine nicht-triviale Eigenschaft erzeugen" bedeutet, dass Sie eine unendliche Anzahl unterschiedlicher Einträge in das TM werfen können. Und alle Ausgänge haben die NT-P
Jerome
1
OKAY. Ich denke, Ihre Antwort wäre viel klarer, wenn Sie nur Standardbegriffe verwenden würden, anstatt Dinge wie "unendlich eine nicht-triviale Eigenschaft erzeugen" zu erfinden, um zu bedeuten, "eine unendliche Anzahl von Eingaben verarbeiten zu können". Es wäre auch hilfreich zu erklären, welcher Aspekt Ihrer "echten" Turing-Maschine nicht in der Lage ist, eine unbegrenzte Anzahl von Eingaben zu verarbeiten. Ist das Band zum Beispiel endlich?
David Richerby