Czy można odwrócić nieodwracalne? Z jednej strony, z definicji, nie można. Z drugiej strony jednak można. Na przykład tak:
nieodwracalne
po odwróceniu staje się
enlacarwdoein
Czyli można. Kwestia woli. Albo kwestia chytrości. Diabeł słynie z chytrości. Człowiek też bywa chytry. Taki Prometeusz na przykład. Wykradł bogom ogień. Z jednej strony źle, bo przecież ukradł. Z drugiej dobrze, bo ukradł by ludziom zimno nie było. Bogom było to obojętne, no i co, że ludziom zimno, grunt, że nam ciepło.
Zatem Prometeusza ludzie lubią, choć na bogów jakoś się nie obrażają, bo z bogami mają swoje interesy.
Ale zboczyliśmy z tematu, a tematem jest odwracanie nieodwracalnego. Tak w ogóle, to nie wszelką nieodwracalność będziemy dyskutować. Ograniczymy się do odwracania nieodwracalnych automatów komórkowych. Ograniczenie to niewielkie jeśli przyjmiemy wiarę kilku geniuszy, że mianowicie cały wszechświat to jeden wielki automat. Jednego takiego geniusz już wymieniałem w poprzednich notkach – to Stephen Wolfram. Drugi geniusz, co się dopiero w moich notkach dzisiaj dopiero pojawia to Edward Fredkin. Z polskiej wikipedii dowiemy się:
Edward Fredkin (ur. 1934) – naukowiec, profesor Carnegie Mellon University (CMU) i wczesny pionier fizyki cyfrowej. Największe zasługi odniósł na polu badań nad odwracalnym rachunkiem komputerowym i automatami komórkowymi.
Bramka Fredkina stanowi zasadniczy przełom w pracach nad rachunkiem odwracalnym, któremu wielkie znaczenie nadaje już w 1969 roku Konrad Zuse w książce "Calculating Space" (Obliczanie przestrzeni). W swoich ostatnich pracach wprowadza pojęcie filozofii cyfrowej[1][2].
Pracował również na wydziale informatyki MIT i jako badacz fizyki na Uniwersytecie w Bostonie.
Wygląd ma taki jakby charakterystyczny, jak na geniusza przystało. Odniósł zasługi „na polu badań nad odwracalnym rachunkiem komputerowym i automatami komórkowymi.” No, no,... Przyjrzyjmy się z bliska jednej takiej jego zasłudze. Zrobimy to na przykładzie. Za przykład weźmiemy automat komórkowy z numerem 37. Czemu 37? Bo o tym numerze nawet film na youtube można znaleźć. Widocznie 37 ma jakąś zasługę. Sam automat 37 jest nieodwracalny. Jednak po odwracaniu staje się ciekawy, do tego stopnia, że jest kandydatem na model wszechświata. No, no.
Czyli 37. Co to takiego. Zapisujemy dwójkowo:
37 = 32 + 4 + 1= 25+22+20
Zatem 37 dziesiątkowe to dwójkowe 00100101. Zamieniamy to na regułę automatu elementarnego
111 → 0,110 → 0,101 → 1,100 → 0, 011 → 0,010 → 1,101 → 0,000 → 1
Albo obrazkowo
Widać, że reguła jest symetryczna. Jak się człowiek wytęży, to może ją zapisać jednym wzorem:
f(a,b,c) = abc+a+c+1 mod 2
Tutaj a,b,c to 0 lub 1. Komórka b, otoczona z lewej przez a i z prawej przez c, przechodzi w komórkę f(a,b,c). Automat jest totalnie nieciekawy. Wystarczy zajrzeć do Wolframa pod Rule 37. Automat jest nieodwracalny. Można to zobaczyć samemu, można popatrzeć na „State transition diagram”.
Jest nieodwracalny, ale my chcemy go odwrócić. I tu na pomoc przychodzi genialny Ed Fredkin. To on, niedouczony fizyk i spec od programowania podpowiedział dwóm fizykom, Tomasso Toffoli i Norman Margolus, jak się odwraca nieodwracalne. Oni to opublikowali w 1990 roku w czasopiśmie Physica D 45, „Invertible cellular automata: A review”. Prosta sztuczka.
Co to jest automat? Automat to jest coś co ma stany, i ma regułę jak każdy stan się transformuje w stan następny. Jeśli q(t) jest stanem w chwili t, to w następnej chwili mamy
q(t+1) = F(q(t))
Reguła działania automatu jest zakodowana w funkcji F. Automat jest nieodwracalny gdy różne q(t) prowadzą do tego samego q(t+1). Nasz automat 37 jest nieodwracalny, bowiem periodyczny stan ...1110011100111.... daje w chwili następnej same zera, tak samo jak stan …..1111111111111....
Otóż Fredkin miał ideę by zmusić automat do odwracalności każąc mu sięgać pamięcią o dodatkowy krok wstecz. Zaproponował mianowicie, by regułę q(t+1) = F(q(t)) zastąpić przez
q(t+1) = F(q(t)) – q(t-1)
Sprytne. Można bowiem stąd obliczyć q(t-1):
q(t-1) = F(q(t)) – q(t+1)
Genialne! Moja przyszłość zależy nie tylko od mojej teraźniejszości, ale od mojej bliskiej przeszłości. To jasne. Probabilista powie: niemarkowskie. Ale niemarkowskie sztuczką można przekształcić w markowskie. To już jest inna znana sztuczka. Fizycy wiedzą, że równania ruchu w mechanice Newtona są równaniami z drugimi pochodnymi, jednak można przejść do formalizmu Lagrange'a lub Hamiltona i już mamy tylko pierwszy rząd. Sztuczki, sztuczki.
Ale ta sztuczka Fredkina jest w istocie prosta i genialna. Coś w niej jest głębokiego. Co? Tego nie wiem. Sam Fredkin tez pewnie nie wie.
Odwrócony po Fredkinowski automat 37 opiszę w następnej notce.
