Czy hałaśliwa wersja gry życia Conwaya obsługuje uniwersalne obliczenia?


30

Cytując Wikipedię , „[Gra życia Conwaya] ma moc uniwersalnej maszyny Turinga: to znaczy wszystko, co można obliczyć algorytmicznie, można obliczyć w ramach Gry życia Conwaya”.

Czy takie wyniki obejmują hałaśliwe wersje Gry życia Conwaya? Najprostsza wersja jest taka, że ​​po każdej rundzie każda żywa komórka umiera z małym prawdopodobieństwem a każda martwa komórka ożywa z małym prawdopodobieństwem (niezależnie).ts

Inną możliwością jest rozważenie następującego probabilistycznego wariantu reguły samej gry.

  • Każda żywa komórka z mniej niż dwoma żywymi sąsiadami umiera z prawdopodobieństwem .1-t
  • Każda żywa komórka z dwoma lub trzema żywymi sąsiadami żyje z prawdopodobieństwem do następnej generacji.1-t
  • Każda żywa komórka z więcej niż trzema żywymi sąsiadami umiera z prawdopodobieństwem .1-t
  • Każda martwa komórka z dokładnie trzema żywymi sąsiadami staje się żywą komórką z prawdopodobieństwem .1-t

Pytanie: Czy te hałaśliwe wersje Gry Życia nadal obsługują uniwersalne obliczenia? Jeśli nie, to co można powiedzieć o ich „mocy obliczeniowej”?

Powiązane informacje na temat mocy obliczeniowej automatów komórkowych i hałaśliwych wersji automatów komórkowych również będą mile widziane.

(To pytanie powstało z tego pytania na temat MathOverflow. Odpowiedź Vincenta Beffary na temat MO zawiera interesujące odniesienia do powiązanych wyników dotyczących obliczeniowych aspektów głośnych automatów komórkowych).


2
@vzn 1) nie, to nie jest „prawdziwe pytanie”, to zupełnie inne pytanie; Pytanie Gila dotyczy odporności prostego modelu obliczeniowego na hałas, a nie siły losowości; 2) TM z losową taśmą nie są bardziej wydajne niż deterministyczne TM, patrz odpowiedź: cstheory.stackexchange.com/a/1415/4896
Sasho Nikolov

2
Prawdziwe pytanie brzmi, czy stochastyczne / hałaśliwe wersje „Gry życia” nadal obsługują obliczenia. (Jeśli te wersje obsługują obliczenia w P, to ich moc może sięgać aż do BPP.) Możliwe jest, że moc obliczeniowa tych stochastycznych wersji gry życia jest znacznie niższa.
Gil Kalai

3
Być może twierdzę, że to oczywiste, ale możesz tyle razy zduplikować konfigurację, aby z dużym prawdopodobieństwem zagwarantować, że wersja konfiguracji nie ma nawet odwróconej jednej komórki. Moim osobistym przekonaniem jest to, że możemy zrobić znacznie, znacznie lepiej, ale przynajmniej jest to prosta dolna granica.
user834

4
Nie jestem pewien, czy pytanie jest dobrze zdefiniowane. Załóżmy, . Wydaje mi się, że możesz znaleźć komputer, który radzi sobie z jednobitowymi błędami w „Grze życia”, dając ci obliczenia odporne na błędy, chyba że spontanicznie otrzymasz duży blok błędów naraz. Ale nie sądzę, że wszystko może być odporne na wszystkie błędy. Załóżmy na przykład, że błędy spontanicznie tworzą wrogiego przeciwnika, którego celem jest zakłócenie obliczeń. Możesz być w stanie pokazać, że obliczenia się powiodły z prawdopodobieństwem > 1 - 10 - 9, ale nie powiodło się z prawdopodobieństwem > 10 - 10000 . Czy to się liczy?t=10-9>1-10-9>10-10000
Peter Shor,

2
Peter, jeśli twoje obliczenia powiodą się z prawdopodobieństwem 2/3, jestem szczęśliwy.
Gil Kalai

Odpowiedzi:


8

Oto niektóre „najlepsze w pobliżu” referencje, za jakie są warte. Wydaje się, że sposobem na postawienie tego pytania jest sprowadzenie go do pytania dotyczącego „głośnych maszyn Turinga”, które były badane (nieco niedawno) i które najwyraźniej są najbliższym odpowiednim obszarem literatury. Podstawowa / ogólna / rozsądna odpowiedź wydaje się być taka, że ​​jeśli TM może się opierać / korygować pod względem szumu (jak pokazano w tych odnośnikach), jest całkiem prawdopodobne, że CA może również, w pewnych granicach / progach.

Pytanie, jak zredukować „głośny CA” do „głośnego TM” (i odwrotnie) jest bardziej otwarte. To może nie być trudne, ale wydaje się, że nie opublikowano badań w tej dziedzinie. Inną kwestią jest to, że głośna TM jest nowym modelem i dlatego może istnieć wiele (naturalnych?) Sposobów reprezentowania głośnej TM. Na przykład w poniższych artykułach omówiono zakłócenia funkcji przejścia stanu, ale innym naturalnym modelem są zakłócenia symboli taśmy (te ostatnie są bardziej związane z hałaśliwymi CA?). Może istnieć pewien związek między nimi.

  • Odporna na uszkodzenia maszyna Turinga autorstwa Ilir Capuni, 2012 (praca doktorska)

    Maszyna Turinga jest najlepiej zbadanym uniwersalnym modelem obliczeń. Teza ta bada pytanie, czy istnieje maszyna Turinga, która może obliczać niezawodnie, nawet jeśli naruszenia jej funkcji przejścia występują niezależnie od siebie z niewielkim prawdopodobieństwem.

    W tej tezie dowodzimy istnienie maszyny Turinga, która z wielomianowym nad głową może symulować dowolną inną maszynę Turinga, nawet gdy jest ona podatna na wady powyższego typu, odpowiadając w ten sposób na pytanie otwarte przez 25 lat.

  • Maszyna Turinga odporna na pojedyncze wybuchy usterek Ilir Capuni i Peter Gacs, 2012
  • Noisy Turing Machines autorstwa Eugene'a Asarina i Pietera Collinsa, 2005
(Kolejne pytanie: czy może być jakiś związek między hałaśliwymi bazami TM a probabilistycznymi maszynami Turinga ?)


7

Gil pyta, czy GL zapomina o swojej początkowej konfiguracji w czasie, niezależnie od wielkości, kiedy każda komórka „wyłącza” funkcję przejścia niezależnie od innych komórek z niewielkim prawdopodobieństwem.

Według mojej najlepszej wiedzy nie jest to znane z GL. To bardzo interesujące pytanie. Jeśli jest w stanie wytrzymać hałas, powinien zachować swoją uniwersalność.

Krótki przegląd najnowszego stanu techniki jest następujący.

  1. Reguła Tooma może uratować jeden bit wiecznych błędów, które występują niezależnie od siebie z niewielkim prawdopodobieństwem.
  2. Powszechnie uważano (hipoteza o dodatnich prędkościach), że wszystkie 1 dim CA są ergodyczne, dopóki P. Gacs nie skonstruował swojego wieloskalowego CA, który może symulować dowolny inny CA z umiarkowanym narzutem, nawet gdy jest poddany wspomnianemu hałasowi.
  3. Pytanie, czy reguła G (acs) K (urdiumov) L (evin) może zaoszczędzić jeden bit na zawsze w obecności powyższego hałasu, jest nadal otwarte. Kihong Park - uczeń Gacs --- pokazał, że nie będzie, gdy hałas będzie tendencyjny.
  4. Kiedy praca w 2 została opublikowana, M. Blum zapytał, czy TM może kontynuować swoje obliczenia, jeśli na każdym etapie przejście nie jest wykonywane zgodnie z funkcją przejścia z pewnym małym prawdopodobieństwem niezależnie od innych kroków, zakładając, że informacje przechowywane na taśma daleko od głowy się nie psuje. Pozytywną odpowiedź udzielił I. Capuni (inny student Gacs) w 2012 r.

„Jeśli nie jest ergodyczny, zachowa swoją uniwersalność” ... czy masz jakieś dowody na to stwierdzenie? Czy to jest twierdzenie? Gdzie to udowodniono? Uważam, że praca Gacsa pokazuje, że jest to prawdą w co najmniej jednym przypadku, ale nie rozumiem, jak to się sprawdza w przypadku gry Conwaya.
Peter Shor,

Dzięki za wskazanie. To nie jest twierdzenie, ale interesujące otwarte pytanie. Bycie ergodycznym wydaje się zbyt mało, by prosić o tak silne stwierdzenie.
user8719,

3

Na początek pamiętaj, że badania w Conway's Game of Life są nadal w toku, a przyszłe opracowania mogą stanowić znacznie mniej skomplikowane rozwiązanie.

A teraz Co ciekawe, jest to temat, który jest tak samo zgodny z biologią i fizyką kwantową, jak z tradycyjną informatyką. U podstaw problemu leży pytanie, czy jakiekolwiek urządzenie może skutecznie przeciwdziałać przypadkowym zmianom jego stanu. Prosta i prosta odpowiedź brzmi: nie da się stworzyć takiej maszyny, która byłaby idealnaodporny na takie losowe zmiany. Oczywiście jest to prawdą w podobny sposób, w jaki mechanika kwantowa może powodować pozornie niemożliwe zdarzenia. Tym, co zapobiega takim zdarzeniom (prowadząc większość ludzi do ich uznania za absolutnie niemożliwą), jest niezwykle małe prawdopodobieństwo, że takie wydarzenie się wydarzy. Prawdopodobieństwo tak małe ze względu na dużą różnicę skali między poziomem kwantowym a poziomem ludzkim. Podobnie możliwe jest stworzenie maszyny stanów odpornej na małe stopnie losowych zmian, po prostu czyniąc ją tak dużą i nadmiarową, że każda zauważona „zmiana” jest w rzeczywistości zerowa, ale zakłada się, że nie jest to celem. Zakładając, że można to osiągnąć w taki sam sposób, w jaki zwierzęta i rośliny są odporne na promieniowanie lub uszkodzenia fizyczne.

Pytanie może zatem nie polegać na tym, jak zapobiegać zbyt dużym uszkodzeniom przez zakłócenia niskiego poziomu, ale raczej na tym, jak wyzdrowieć z jak największej liczby uszkodzeń. Tutaj biologia staje się istotna. Zwierzęta i rośliny faktycznie mają tę zdolność na poziomie komórkowym. (Uwaga: w tej odpowiedzi mówię o komórkach w sensie biologicznym). W grze życia Conwaya pojęcie budowy urządzenia komputerowego w skali pojedynczych komórek jest atrakcyjny (w końcu sprawia, że ​​takie kreacje są znacznie mniejsze i bardziej wydajne), ale chociaż możemy budować samoreprodukujące się komputery ( patrz Bliźnięta ), ignoruje to fakt, że sam obiekt konstruktora może zostać uszkodzony przez zakłócenia.

Innym, bardziej odpornym sposobem, w jaki mogę to rozwiązać, jest budowanie komputerów z samoreprodukujących się zbędnych części (myśl komórki biologiczne), które wykonują swoje operacje, rozmnażają się i są zastępowane.

W tym momencie możemy zobaczyć kolejną interesującą równoległość w świecie rzeczywistym. Te zaburzenia na niskim poziomie są podobne do skutków promieniowania. Jest to najbardziej znaczące, gdy weźmie się pod uwagę rodzaj uszkodzenia, jakie można wyrządzić automatom komórkowym. Wywołanie awarii kaskady lub „śmierci” komórki w grze życia Conwaya jest łatwe, podobnie jak dzieje się to w przypadku wielu komórek narażonych na promieniowanie. Ale istnieje najgorszy możliwy przypadek mutacji, tworząc „rakową” komórkę, która nadal reprodukuje wadliwe kopie siebie, które nie pomagają w procesie obliczeniowym lub dają nieprawidłowe wyniki.

Jak już powiedziałem, nie da się zbudować systemu, który byłby całkowicie niezawodny, można jedynie sprawić, że usterka naruszy cały system. Oczywiście podstawowe pytanie brzmi: „same symulacje probabilistyczne Turinga zakończone”, co już zostało uznane za prawdziwe . Na początku odpowiedziałbym na to fundamentalne pytanie, z wyjątkiem tego, że nie było to pytanie, które zadałeś.


Łał! Dziękuję za głosowanie za przejęciem! W każdym razie poprawiłem swój post, dodając trochę informacji i źródeł. Przepraszam, że nie miałem czasu, aby to zrobić, kiedy pierwszy raz to opublikowałem. Mógłbym zmodyfikować tę odpowiedź jeszcze bardziej, aby pasowała do standardów wspólnotowych, gdyby nie fakt, że nie podano powodu do głosowania.
Hawkwing

5
Jako osoba bez prawa głosu nie rozumiem, jak to odpowiada na pytanie Gila. Odpowiadasz na pytanie, czy „każde urządzenie może skutecznie przeciwdziałać przypadkowym zmianom jego stanu”, czego nie pytał Gil.
András Salamon,

Dzięki (tym razem nie sarkastycznie) za komentarz, András Salamon. Osobiście głosowałbym, że jest to przydatne, ale nadal jestem nowym użytkownikiem tej przepełnionej witryny. W każdym razie przepraszam, że moja odpowiedź wydaje się nie na temat. Być może zająłem się tym pytaniem bardziej swobodnie, niż zamierzałem, ale czuję, że moja odpowiedź odpowiada na pierwotne pytanie, odpowiadając na podobne pytanie, a następnie rysując podobieństwa między nimi. Czy to może zbyt okrągły sposób odpowiedzi?
Hawkwing

0

Przypomina mi się xkcd 505: A Bunch of Rocks .

Każdy komputer w świecie rzeczywistym jest narażony na pewien poziom hałasu. Symulacja uniwersalnego komputera w idealnym nieskończonym wszechświecie życia Conwaya będzie miała średni czas między awariami, zależny od szczegółów konstrukcyjnych jego projektu. Będzie obliczał się niezawodnie przez okres probabilistyczny, niewiarygodnie przez okres kumulacji błędów, a potem wcale .

Spodziewałbym się, że model logiki rozmytej lub superpozycji kwantowej jasno pokaże, jakiej niezawodności należy oczekiwać od konkretnej konstrukcji. Można chcieć symulować oczekiwane wyniki różnych komponentów, zamiast iteracji po wszystkich ich komórkach, w jakimkolwiek stopniu można je od siebie odizolować. Można oszacować spodziewane zakłócenia z powodu wadliwych komponentów. Algorytm genetyczny powinien być najlepszym sposobem na opracowanie komponentów odpornych na uszkodzenia, odpornych, korygujących} z MTBF tak dużymi, jak jest to pożądane dla danego rozkładu hałasu.


(tajemnicze głosowanie tutaj). Odpowiedź ilościowa byłaby bardzo spekulacyjna. Nie ma bardziej precyzyjnej odpowiedzi niż „tak, warunkowo” bez szeroko zakrojonych eksperymentów na wybranej implementacji UTM. Normalny komputer w środowisku wysokiego promieniowania jest wciąż praktycznie UTM, jeśli tylko na krótko.
user130144
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.