Entropia i złożoność obliczeniowa

12

Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć odpowiedź.F(n)F(n)

XL _At_Here_There
źródło
Powiązanie z danym dokumentem poprawiłoby to pytanie.
Stella Biderman
@StellaBiderman dziękuję, ale nie znalazłem linku w twoim komentarzu.
XL _At_Here_There
Nie wiem o jakim papierze / badaczu mówisz. Sugeruję, abyś dostarczył I
Stella Biderman
1
@StellaBiderman Nie zrozumiałem waszych komentarzy, w rzeczywistości po prostu przeczytałem tekst o treści „wymazywanie bitów wymaga zużycia energii” w złożoności Kołmogorowa i jego zastosowania przez Viatanyi i Li. Myślę, że nie czytałem żadnych innych powiązanych artykułów i książek
XL _At_Here_There 5'18

Odpowiedzi:

16

Tak, ale większość dotychczasowych prac (z wyjątkiem bardzo niedawnych, patrz poniżej) koncentrowała się na przekształceniu obliczeń nieodwracalnych w odwracalne, mając nadzieję na uniknięcie generowania entropii. (Uwaga: istnieje istotna różnica między energią potrzebną do uruchomienia obliczeń a entropią wygenerowaną przez obliczenia i wypuszczoną do środowiska, zwykle w postaci ciepła).

kTln(2)

Niedawno,

Demaine, Lynch, Mirano i Tyagi. Algorytmy energooszczędne , 2016.

studiował częściowo odwracalne algorytmy - to znaczy, jeśli jesteś skłonny zapłacić trochę entropii, dla standardowych zadań algorytmicznych można poprawić ogólne symulacje nieodwracalne do odwracalnych wspomniane powyżej. Komputery odwracalne poświęcone są całej społeczności naukowców, a mianowicie. odwracalny Computing Conference, teraz w jej 10 lat.

ln(2)

Kolchinsky & Wolpert, Zależność rozproszenia od początkowego rozkładu między państwami . J. Stat. Mech 2017 ( link arXiv )

(i odnośniki tam zawarte).

W sierpniu 2017 r. Gościliśmy warsztaty na ten temat w Instytucie w Santa Fe (gdzie można zobaczyć nazwiska niektórych badaczy i tytuły ważnych rozmów), co rodzi zupełnie nowy zestaw pytań zarówno w zakresie fizyki, jak i termodynamicznej złożoności obliczeniowej.

Joshua Grochow
źródło
Maszyna Turinga lub teoria Kościoła-Turinga może być rządzona lub ograniczana przez prawo fizyczne, więc możliwość, czy można zastosować obliczenia kwantowe lub komunikację kwantową, można wywnioskować z prawa fizyki, takiego jak drugie prawo mechaniki statystycznej, ogólna teoria względności. Sądzę więc, że jeśli jest jakikolwiek wynik dotyczący powiązania tezy i prawa fizyki
XL _At_Here_There
Wydaje się, że strona fizyki nie jest zainteresowana tego rodzaju tematami.
XL _At_Here_There 3'18
@XL_at_China: Istnieje „teza o fizycznym kościele Turinga”, ale nie ma ona nic wspólnego z drugim prawem, ponieważ zarówno teza o kościele, jak i jej wersja fizyczna dotyczą tylko tego, co jest obliczalne, a nie jakichkolwiek oszacowań ilościowych , ale drugie prawo jest stwierdzeniem ilościowym. Ponadto, chociaż być może nie było jeszcze wielu publikacji na ten temat, w naszych warsztatach fizycy zdecydowanie wydawali się zainteresowani.
Joshua Grochow
Próbowałem znaleźć powiązanie kilka lat temu, ale nie uzyskałem żadnego rezultatu. Intuicyjnie wydaje się, że obliczalność musi być powiązana z drugim prawem termodynamicznym. Biorąc pod uwagę maszynę Turinga w kategoriach ogólnej teorii względności, problem staje się interesujący. Ale nie wiem, czy fizycy są zainteresowani takim problemem.
XL _At_Here_There
Czy możemy zadać powiązane pytanie dotyczące fizyki witryny i przedyskutować je z fizykiem?
XL _At_Here_There