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

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).$t$$s$

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).

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

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.

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ś.

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.