Czy istnieje związek między problemem zatrzymania a entropią termodynamiczną?

Alan Turing zaproponował model maszyny (Maszyna Turinga, TM), który oblicza (liczby, funkcje itp.) I udowodnił twierdzenie Haltinga .

TM to abstrakcyjna koncepcja maszyny (lub silnika, jeśli chcesz). Twierdzenie Haltinga jest wynikiem niemożliwości. Silnik Carnota (CE) to abstrakcyjna koncepcja silnika cieplnego, a Carnot udowodnił twierdzenie Carnota , kolejny wynik niemożliwości związany z entropią termodynamiczną.

Biorąc pod uwagę, że TM jest fizycznie możliwa do zrealizowania (przynajmniej tyle co CE, a może nie?), Czy istnieje mapowanie lub reprezentacja lub „izomorfizm” TM lub CE, który mógłby pozwolić na ujednolicenie tych wyników i dodatkowo połączyć się z entropią?

Istnieją oczywiście sformułowania TM i twierdzenia Haltinga w kategoriach algorytmicznej teorii informacji (np. Chaitin, Kołmogorow itp.) I entropii (w tym kontekście). Pytanie dotyczy bardziej fizycznej koncepcji entropii (jeśli w trakcie potencjalnej odpowiedzi pojawi się entropia algorytmiczna, jest w porządku, ale nie o to dokładnie pyta pytanie).

W fizyce można także sprawdzić inne pytanie, które wiąże niepewność kwantową z drugą zasadą termodynamiki. Zobacz także: algebraiczna charakterystyka entropii , algorytmiczna charakterystyka entropii , przegląd i powiązania między różnymi sformułowaniami entropii

W ogóle nie jestem ekspertem w tej dziedzinie, ale wierzę, że będziecie zainteresowani komputerami odwracalnymi . Obejmuje to między innymi badanie związku między procesami fizycznie odwracalnymi a procesami logicznie odwracalnymi. Myślę, że sprawiedliwie byłoby powiedzieć, że „założycielami” tej dziedziny byli / są Ralph Landauer i Charles H Bennett (myślę, że obaj badacze IBM).

Dotyka obliczeń kwantowych i teorii informacji kwantowej, ale bada także pytania typu „jakie są granice obliczeń pod względem czasu, przestrzeni i energii?” Wiadomo (o ile dobrze pamiętam), że można sprawić, by energia wymagana do wykonania odwracalnego obliczenia dowolnie mała, powodując, że zajmie to arbitralnie długi czas. Oznacza to, że energia czas (= akcja ) wymagana do wykonania odwracalnego obliczenia może być stała. Nie dotyczy to obliczeń nieodwracalnych.$\times$

Wiele osób studiujących w tym obszarze pracuje również nad obliczeniami kwantowymi i fizyką cyfrową (idea, że ​​wszechświat jest dużym automatem kwantowym). Nazwane imiona badaczy to Ed Fredkin , Tommaso Toffoli i Norm Margolus .

Te pytania są absolutnie na temacie dla informatyki. Nie tylko dla teorii (która obejmuje zarówno fajną matematykę, jak i fajną fizykę), ale także dla inżynierów, którzy chcą poznać ostateczne granice obliczeń. Czy wymagana jest minimalna objętość lub energia do przechowywania odrobiny informacji? Działania wymagane do wykonywania odwracalny obliczeń może być stała, ale istnieją ograniczenia na co to jest stała? To kluczowa wiedza dla inżynierów próbujących przekroczyć granice możliwości.

Nie jestem zaznajomiony z Twierdzeniem Carnota, z wyjątkiem tego, co właśnie przeczytałem w Wikipedii, ale nawet z tego pobieżnego wprowadzenia istnieje związek w strukturze dowodów, co może być dla ciebie interesujące, ponieważ jest to technika dowodu ma to zastosowanie w wielu domenach.

Oba są dowodami sprzeczności, w których można wykazać, że żadna rzecz w danej klasie nie ma jakiejś własności, można przypuszczać, że jakaś instancja faktycznie ma tę właściwość, a następnie pokazać, że pojawia się sprzeczność.

Problem zatrzymania jest interesujący, ponieważ sprzeczność wynika z pewnej interakcji między sobą w odniesieniu do konkretnej instancji (która jest maszyną M, która może ustalić, czy dowolna maszyna zatrzyma się z danym wejściem). W szczególności konstruujesz nową maszynę, która zawiera M jako komponent, a następnie podajesz nową maszynę do M.

Ktoś z większą wiedzą na temat twierdzenia Carnota mógłby go rozwinąć (do czego nie jestem uprawniony), ale wydaje się, że sprzeczność wynika z rodzaju silnika cieplnego, który można zbudować, gdybyś miał instancję z posiadaną własnością.

Oba przypadki dotyczą budowy:

• Załóżmy, że niektóre X ma właściwość P.
  • Od X, zbuduj powiązane Y.
  • Relacje między X i Y są sprzeczne.
• Dlatego żaden X nie ma właściwości P.

Wydaje się jednak, że istnieje różnica w tym, że sprzeczność w przypadku twierdzenia Haltinga jest czystą logiczną sprzecznością i byłaby sprzeczna w każdym układzie logiki klasycznej. Twierdzenie Carnota, jak rozumiem, jest tylko sprzeczne w odniesieniu do drugiej zasady termodynamiki. Z logicznego punktu widzenia jest to aksjomat, więc gdyby przyjąć inną aksjatyzację, w której nie obowiązywało drugie prawo termodynamiki, twierdzenie Carnota nie byłoby twierdzeniem, ponieważ sprzeczność nie istniałaby. (Jak wyglądałoby sformalizowanie termodynamiki bez drugiego prawa jest rodzajem pytania, które doprowadziło geometry do geometrii innej niż euklidesowa.)

IANAfizyk, ale nie widzę żadnego związku. Maszyny Turinga są obiektami czystej matematyki, a nierozstrzygalność problemu zatrzymania jest niezależna od jakiejkolwiek fizycznej realizacji czegokolwiek.

to różnorodne pytanie na wiele tematów unf nie ma prostej / łatwej odpowiedzi i dotyczy aktywnych obszarów badań TCS. jednak to rzadkie pytanie dotyczy związku między fizyką a TCS, który interesuje mnie od lat. istnieje kilka różnych kierunków, w których należy przejść. podstawowa odpowiedź jest taka, że ​​jest to „pytanie otwarte”, ale z pewnymi aktywnymi / nowoczesnymi badaniami dotykającymi go i wskazującymi na połączenia.

• istnieją pewne zaskakujące / głębokie nierozstrzygalne problemy z zaawansowanej fizyki. na przykład z układów dynamicznych. jednakże nie widziałem tego związanego z entropią per se, ale entropia jest powiązana ze wszystkimi układami fizycznymi (np. można to zobaczyć w teorii chemii), więc musi istnieć co najmniej pośredni związek.

• entropia rzeczywiście pojawia się w CS, ale bardziej w formie teorii informacji i teorii kodowania. narodziny teorii kodowania obejmowały zdefiniowanie / analizę entropii związanej z kodami komunikacyjnymi przez Shannona. wypróbuj tę świetną referencję online Teoria Entropy & Information firmy Gray

• entropia wiąże się również czasami z pomiarem losowości w PRNG. istnieje związek separacji klas złożoności (np. P =? NP) z PRNG w słynnej pracy „Natural Proofs ” autorstwa Razborova / Rudicha. trwają badania nad tym tematem.

• wspominasz o termodynamice i jej połączeniu z TCS. istnieje głęboki związek między namagnesowaniem w szkłach spinowych w fizyce a kompletnymi problemami NP badanymi w punkcie przejścia SAT. tam (ponownie) system fizyczny jest powiązany z entropią, ale prawdopodobnie był badany bardziej w kontekście fizyki niż w kontekście TCS.

Istnieje prosty problem myślowy, który czasami jest wykorzystywany jako wprowadzenie do niekonwencjonalnych paradygmatów obliczeniowych:

Masz dwie żarówki i odpowiadające im wyłączniki. Ktoś otwiera i zamyka oba światła jeden po drugim. Jak ustalić, który z nich został zamknięty jako pierwszy, a który jako ostatni? Określ minimalną liczbę razy, kiedy będziesz musiał otworzyć światła, aby rozwiązać ten problem.

Większość informatyków zwykle próbuje znaleźć jakieś rozwiązanie oparte na logice boolowskiej. Odpowiedź brzmi (przynajmniej jedna): dotykając żarówek i sprawdzając, która z nich jest cieplejsza.

W informatyce istnieją paradygmaty oparte na cieple: symulowany wyżarzanie jest znanym algorytmem (komputer kwantowy fal D jest kwantowym odpowiednikiem algorytmu).

Czy istnieje związek z problemem Haltinga?

Klasyczne dzieło Chaitina i Calude'a na temat problemu Haltinga za pomocą koncepcji liczb Omega można powiązać z probabilistycznym sformułowaniem problemu Haltinga. Jest to najnowszy traktat na temat problemu, o którym mogę myśleć ... i brak wyraźnego związku z entropią (termodynamiczną). Teraz, jeśli entropia informacji (w sensie Shannona) jest dla ciebie dobra, liczba Omega koduje w najbardziej zwięzły sposób problem Haltinga, w sensie związanym z Shannonem.

Krótko mówiąc, liczba Omega to prawdopodobieństwo, że program losowy zatrzyma się. Znajomość stałej pozwoliłaby na wyliczenie wszystkich prawidłowych stwierdzeń matematycznych (prawd, aksjomatów itp.) I jest nieobliczalna. Calude obliczył wersję Omegi, zmieniając jednolitą miarę prawdopodobieństwa miarą odwrotnie proporcjonalną do losowej długości programu i stosując kodowanie bez prefiksów, więc moglibyśmy mówić o Omegi Chaitina i Omegi Calude'a.

Tak !, o dziwo pomyślałem o tym .. Oto pomysł:

Pierwszy krok

Model Demona Maxwella jako program komputerowy. Zatem, w jaki sposób Demon poznał prędkość i pozycję cząstki, zanim otworzył drzwi do selekcji?

Załóżmy, że demon nie jest w stanie zmierzyć prędkości, z jaką cząstki uderzają w drzwi, dlaczego? ponieważ zmieniłoby to prędkość cząstek, więc demon musi się dowiedzieć, zanim je otworzy, bez patrzenia, bez pomiaru. Aby być uczciwym, z wyprzedzeniem powiadomimy demona o zasadach gry, tj. Nakarmimy demona prawami ruchu, oddziaływaniami cząstek i warunkami początkowymi, dość modelu fizyki / dynamiki.

Drugi krok

Teraz zamodeluj gaz cząstek również jako program komputerowy, który uruchamia ten sam kod podany demonowi dla każdej cząstki, więc gaz oblicza wynik z jego początkowych warunków, Demon nie zna tego wyniku, dopóki się nie zatrzyma (jeśli w ogóle ): mianowicie „cząstka o właściwej prędkości jest u drzwi”, decyzja tak / nie zadajemy systemowi pytanie „Czy cząstka ma odpowiednią pozycję i wystarczającą prędkość?”, jeśli tak, drzwi można otworzyć a szybka cząsteczka może przejść do strony o wysokiej temperaturze w pomieszczeniu, ustanawiając nowe warunki początkowe (czy te kolejne problemy mają odpowiedź? czy będą działać wiecznie?)

Będzie czas, gdy nie będzie cząstki o prędkości wystarczającej do przekroczenia granicy, więc będzie czas, w którym kod będzie działał wiecznie (nie zatrzymuj się) dla prawie dowolnego progu.

Demon chce poznać wynik obliczany przez gaz, ale wynik jest w pewnym sensie potencjalnie zaangażowany w kod źródłowy praw cząstki plus warunki początkowe. Oczywiście musimy uruchomić ten program, aby to wiedzieć. Jeśli Demon uruchomi ten sam program, czekając na odpowiednią prędkość na wyjściu, program może się zatrzymać lub może działać wiecznie (ale przypuszczamy również, że demon nie ma więcej mocy obliczeniowej niż gaz, więc nie będzie mógł zdecydować czas otwarcia drzwi).

Daemon może spróbować dowiedzieć się, jaki jest wynik programu (lub jeśli się zatrzyma), obserwując źródło i dane wejściowe bez uruchamiania go, ale to tak, jakby próbować rozwiązać problem zatrzymania, dlaczego? ponieważ Demon nie wie, jakie prawa i warunki początkowe będą karmione, dlatego Demon powinien być przygotowany do rozwiązania dowolnego zestawu przepisów i warunków początkowych, i wiemy, że ogólnie nie jest to możliwe, będzie potrzebował wyroczni, jeśli mógłby, to będzie wystarczy zbudować demona, aby wytworzyć energię z niczego. (nawet znając prawa i stan początkowy, obie rzeczy są już wystarczająco trudne do poznania)

Ten eksperyment myślowy może powiązać, w jaki sposób ograniczenie entropii za pomocą komputerów może być w jakiś sposób ograniczone przez problem zatrzymania , jako problem do przewidzenia w ogólności wyników.

(Czasami wszystkie limity wydają się być takie same…)

Więcej o prawach cząstkowych

Prawa cząstek nie są głównym zagadnieniem tego eksperymentu myślowego, prawa te mogą być kwantowe lub klasyczne, ale musimy wziąć pod uwagę fakt złożoności praw i warunków początkowych, złożoność układu cząstek nie jest ograniczona i mogłaby mają dużo większą złożoność (w skrajnym przykładzie warunków początkowych można nawet wstawić cały komputer odpalający cząstki zgodnie z wewnętrznym kodem źródłowym i przekazać ten kod demonowi).

Naprawdę bardzo wciągające pytanie, a przekonamy się, że twoje myślenie jest prawidłowe .

Najpierw zobaczmy, co mówi druga zasada termodynamiki.

Funkcja entropii jest używana w 2. prawie termodynamiki. Wynika to z twierdzenia Carnota, które stwierdza, że ​​procesy zachodzące w maszynach parowych mają wydajność niższą lub co najwyżej równą odpowiedniej „odwracalnej” maszynie (która, nawiasem mówiąc, wydaje się niestabilną koncepcją przez 150 lat termodynamiki). Carnot sam nie wymyślił funkcji entropii, ale razem z Clausiusem tak mówią:

Ponieważ nie ma maszyny wiecznej, możemy zbudować funkcję S zwaną entropią, która ogranicza makroskopowe miary termodynamiczne do pewnego równania, a mianowicie, że S (V, T, P itd.) = 0

Zauważ, że równanie to jest niczym innym jak równaniem hiper-powierzchni w przestrzeni miar termodynamicznych.

Wchodzi do Carathéodory.

Carathéodory jest niemieckim matematykiem i jak wszyscy matematycy chce wyciągnąć z Carnota i Clausiusa uzasadniając pewne aksjomaty, które pozwoliłyby mu wyjaśnić, o czym tak naprawdę jest drugie prawo . Mówiąc wprost, chce oczyścić termodynamikę, aby dokładnie wiedzieć, czym jest entropia.

Po wymienieniu pewnej liczby aksjomatów udaje mu się sformułować JEGO drugie prawo, które mówi (mniej więcej):

Istnieją pewne procesy adiabatyczne. Lub prozaicznie, jeśli chcesz wrócić, czasem praca sama w sobie nie wystarczy. Potrzebujesz trochę ciepła.

Teraz wydaje się to BARDZO różne od sformułowania Clausiusa! Ale tak naprawdę nie jest. Wszystko, co zrobił Carathéodory, polegało na zmianie kolejności słów, trochę jak matematycy grający 5. aksjomatem Euklidesa przez 2000 lat i produkujący wiele różnych sformułowań dla tego aksjomatu. A jeśli cofniesz się o krok, nie powinieneś być zbyt zaskoczony stwierdzeniem Carathéodory'ego o drugim prawie. W rzeczywistości, Carathéodory prowadzi do dokładnie tej samej funkcji entropii i równania hiperpowierzchniowego S (V, T, P itd.) = 0

Zastanów się nad twierdzeniem Carnota. Jako matematyk nie powinieneś być zbyt zadowolony ze sposobu, w jaki Carnot przyznaje, że maszyny perpetuum nie istnieją. W rzeczywistości jako matematyk wolałbyś zobaczyć coś takiego:

Istnieje funkcja entropii S, która ogranicza miary makroskopowe JEŻELI I TYLKO JEŚLI nie ma maszyn perpetuum ".

TERAZ masz twierdzenie. A co to mówi? Że dopóki nie ma izolowanego układu mechanicznego , który wytwarza nieskończoną ilość energii, a zatem może doprowadzić cię do dowolnego pożądanego stanu, znajdziesz funkcję entropii. Izolowane mechaniczny system adiabatyczny proces. Stąd sformułowanie Carathéodory: żaden system adiabatyczny nie doprowadzi cię nigdzie. Czasami potrzebujesz trochę ciepła.

Więc nie tylko jesteśmy pewni, że Carathéodory ma rację, ale także, że jego sformułowanie jest dość proste.

Skąd masz wrażenie, że drugie prawo à la Carathéodory jest podobne do problemu zatrzymania?

Cofnij się o oświadczenie Carathéodory. Wszystko to mówi, że to kiedy masz izolowany układ mechaniczny, z którym przestajesz się mieszać, nie możesz osiągnąć pożądanego stanu.

Czy to nie brzmi PRECYZYJNIE jak problem z zatrzymaniem? To znaczy, kiedy już napiszesz wszystkie aksjomaty swojej teorii i ustalisz wszystkie możliwe przejścia, pojawią się problemy, których nie możesz rozwiązać. Czasami trzeba będzie dodać więcej aksjomatów.

W rzeczywistości, jeśli chcesz naprawdę zagłębić się i zakodować sformułowanie Carathéodory, spowoduje to taki sam kod jak problem zatrzymania procesów adiabatycznych zamiast maszyn Turinga i stanów zamiast problemów.

Co myślisz?

UWAGA: prawie całkowicie zredagowałem swoją odpowiedź, więc poniższe komentarze nie będą zgodne z tym, co teraz zawiera.