Frank van Hertrooij
Scivolemo 20 Decembro 2017
Pliaj artikoloj
Kiam oni pensas pri komputiloj, oni plej ofte pensas pri la tekokomputilo aŭ persona komputilo kiun oni uzas hejme, pri etaj komputiloj en poŝtelefonoj kaj aliaj maŝinoj, aŭ pri la gigantaj komputiloj kiujn entreprenoj aŭ sciencistoj uzas por prilabori grandajn arojn da datumoj. Malgraŭ ilia diverseco, tiuj maŝinoj havas unu gravan komunan kvaliton, nome ke ili uzas elektronikajn cirkvitojn por fari la kalkulojn. Nenio preventas aliajn sistemojn de iĝi komputiloj tamen. Alternative, oni povas uzi domenajn tabuletojn, rulglobetojn aŭ fluantan akvon por atingi la saman, se oni ruze kunmetas la maŝinon.
Historio
Unu tre interesa ekzemplo estas “Game of Life” (Ludo de la vivo), kiun la Brita matematikisto John Conway elpensis, kiam li eksperimentis kun ĉelaj aŭtomatoj. Tia aŭtomato estas matematika modelo kun krado plena je ĉeloj, kies stato dependas de tiuj de la najbaroj. Tiutempe la komputiloj ne estis tiom fortaj kaj facile haveblaj kiel nun, do la unuaj simuladoj de GOL estis kalkulataj per skribiloj aŭ goo-tabuloj. Oni facile povis erari kaj sistemoj ne povis iĝi tro grandaj kaj komplikaj, sed ĝi estis nekredeble simpla kompare al ĝia antaŭulo, nome la memkopianta maŝino de von Neumann.
John von Neumann revis pri maŝinoj kiuj povus krei perfektan kopion de si mem kaj pruvis ke tiaj maŝinoj estus la plej efika strategio por la minado de ekzemple asteroidoj. Tiu tasko estis ege malfacila. Kvankam li ja sukcesis matematike priskribi tian maŝinon en 1940, ĝi estis tre komplika ĉela aŭtomato kun multaj reguloj kaj 29 statoj de ĉeloj. Ĉiu ĉelo havis kvar najbarojn kun 29 ŝatoj, de kiuj la sekva generacio dependus. Tio donas 295 eblojn, aŭ ĉirkaŭ dudek milionoj, por nur la plej simpla maŝino. Conway volis draste simpligi tiun modelon kaj kunigis aron da studentoj en 1965 por elpensi novajn regulojn. Trovi bonan sistemon estis malfacila kaj oni devis ellabori ĉion permane, sed oni havis kelkajn sukcesojn. Finfine GOL iĝis la plej konata sistemo, interalie pro ĝia simpleco kaj la fakto ke la kalkuloj ne daŭras tro longe.
Reguloj
GOL estas nulpersona ”ludo” kiu estas ludata sur senfine granda tabulo kun kvadrataj ĉeloj. Tiuj ĉeloj povas esti nigraj (vivantaj) aŭ blankaj (mortaj) kaj evoluas dum la tempo. Conway elpensis kvar regulojn por priskribi kiel tiu evoluo okazas kaj ili ĉiuj dependas de la kvanto de najbaroj kiun la ĉelo havas. Malkiel la maŝino de von Neumann, oni ne nur enkalkulas la ĉelojn kiuj flanke limas kiel najbarojn, sed ankaŭ tiujn kiuj diagonale limas.
Por scii kio okazos al la ŝelo, oni nombras kiom da vivantaj najbaroj specifa ĉelo havas kaj sekvas la taŭgan regulon:
La reguloj de la ludo ŝajnas tute hazardaj, sed malantaŭ ili estas amaso da laboro. Per nur iomete ŝanĝi la regulojn, la sistemo perdas sian balancon kaj kreskas senfine aŭ mortas en kelkaj generacioj. Per ĉi tiuj reguloj tamen, la ludo estas tre fleksebla kaj povas krei amason da ĉelajn strukturojn, kiuj similas al aferoj en la naturo. Ekzemplo de tio estas la kreskado de kristaloj, aŭ ”kolonia inteligenteco”, kie grandskalaj interagoj estas kaŭzataj de tre simplaj decidoj je la ĉela nivelo. Tio similas al formika kolonio. Ankaŭ aliaj regularoj ekzistas sub aliaj nomoj, sed neniu ludo estas tiom vaste uzata kiel GOL.
Strukturoj
Ekzistas multaj strukturoj en GOL kun tre diversaj kvalitoj. Kelkaj estas fiksaj, aliaj moviĝas kaj kelkaj eĉ povas fabriki aliajn strukturojn. Tio donas kompleksecon al la sistemo. Oni havas tre bazajn regulojn, sed malsamaj kondiĉoj je la komenco povas krei la plej mirindajn rezultojn. Unue la strukturoj estis tre simplaj tamen, kaj ekde kiam oni sukcesis krei komputilajn programojn por simili la ludon, oni povis malkovri pli kaj pli komplikajn strukturojn. Tiuj malkovroj bone sekvis la evoluon de la kapabloj de komputiloj kaj hodiaŭtage multaj homoj ankoraŭ provas malkovri novajn strukturojn. Certe estas amuze serĉi senkostan programon por mem eksperimenti, aŭ eĉ fari tion per papero kaj skribilo por vidi kiel ĉio funkcias ene. La strukturojn en la bildoj mi kreis per la programo Golly.
La ekzemploj ĉi-supre estas fiksaj strukturoj. Neniu ĉelo mortas aŭ ekvivas sen influoj de ekstere. Tio igas ilin tre gravaj, ĉar ili povas subteni pli grandajn strukturojn per agi kiel bariloj, aŭ ili povas agi kiel komputila memoro. De maldekstre la figuroj nomiĝas ”Bloko” (Block), ”Boato” (Boat), ”Pano” (Loaf) kaj “Abelujo” (Beehive). La strukturoj estas tre simplaj kaj eĉ hazarde aperas kiam oni uzas hazardajn kondiĉojn.
Ankaŭ ekzistas oscilantaj strukturoj. Tiuj estas strukturoj kiuj reiras al la origina stato post specifa kvanto da generacioj. Ili povas esti tre simplaj, sed ankaŭ sufiĉe kompleksaj. La strukturoj sube estas paŭzintaj kaj montras la malsamajn generaciojn unu post la alia.
Ĝis nun montritaj strukturoj ja moviĝis, sed ili ne povis interagi. Por krei pli kompleksajn strukturojn, malsamaj partoj bezonas manierojn por komuniki. Tion oni povas fari per moviĝantaj strukturoj kiuj iras en specifa direkto. Strukturoj kiuj kapablas fari tion nomiĝas kosmoŝipoj kaj ili funkcias ĉar ili revenas al la sama strukturo kiel antaŭe, sed iom ŝovite. Kosmoŝipoj estas speco de informo kaj ne povas vojaĝi pli rapide ol ”lumo”. En GOL tio signifas ke nenio povas vojaĝi pli rapide ol unu ĉelo ĉiun generacion, ĉar ĉeloj nur povas influi siajn rektajn najbarojn. Tiu rapideco estas nomata c, sed praktike spacŝipoj ne povas moviĝi pli rapide ol c/2 sen helpo.
La plej konata kaj ofta spacŝipo estas la Glisilo (Glider). Ĝi estas 3×3 ĉelojn granda kaj moviĝas diagonale je rapideo de c/4.
Ĉi tiuj glisiloj ĉiuj estis kreitaj unu generacio post la alia de dekstre maldekstren. Videblas ke ĉiujn kvar generaciojn la glisilo moviĝas unu ĉelon suben (fakte ankaŭ dekstren, sed tio ne videblas ĉi tie).
Diversaj horizontalaj kosmoŝipoj povas moviĝi je c/2. Ekzemplo de ili estas la Malpeza Kosmoŝipo (Lightweight Spaceship) ĉi-supre.
Kosmoŝipoj povas esti parto de la originaj kondiĉoj de la ludo, sed ili ankaŭ povas esti produktataj de strukturoj. Tio povas okazi tute hazarde, sed oni ankaŭ konstruis maŝinojn, kiuj ritme fabrikas novajn kosmoŝipojn kaj elsendas ilin en rektan linion. Oni povas vidi la kosmoŝipojn kiel informojn kaj la linion kiel ŝnuron. Per aliaj kosmoŝipoj aŭ fiksaj strukturoj oni povas bloki la linion se tio necesas. Ĉi tio estas la bazo de GOL kiel vera komputilo, ĉar ĉi tiun transdonadon de informoj ankaŭ ebligas kalkuladon.
Ĉi tio estas la Glisilpafilo de Gosper (Gosper Glider Gun) dum ĝi ”pafas” glisilojn diagonale suben. La strukturoj funkcias per du partoj kiuj horizontale moviĝas kaj ŝanĝas sian direkton ĉiam kiam ili trafas unu la alian, aŭ la blokojn ĉe la rando. Ĉiam kiam ili trafas unu la alian, ili ankaŭ kreas glisilon. La strukturo estis trovita de Bill Gosper, kiu pruvis per la senfina kvanto da glisiloj ke GOL povas produkti senfine grandajn strukturojn. Unue Conway pensis ke tio ne eblus kaj promesis $50 al la unua persono kiu povis pruvi tion, aŭ la malon. Longe post doni la monon al Gosper li tamen konfesis ke li ja esperis ke senfinaj strukturoj eblus.
GOL kiel komputilo
Glisilpafiloj sufiĉe similas al fizikaj komputiloj kiam oni pensas pri la fundamentaj principoj. Komputiloj funkcias per transistoroj, kiuj fermas kaj malfermas elektrajn fluojn per elektro. Kiam du glisiloj renkontiĝas, ili povas detrui sin mem kaj tiel bloki la informojn. Oni do povas ŝalti fluojn de glisiloj per aliaj glisiloj. Laŭ tiu komparo oni povas krei transistorojn el glisilpafiloj kaj logikajn pordojn el tiuj transistoroj.
Logika pordo estas la bazo de komputila kalkulado. Ili konsistas el transistoroj kaj havas plej ofte unu aŭ du ŝnurojn kiuj iras enen kaj unu kiu iras eksteren. La stato de la ŝnuro eksteren dependas de la statoj de la ŝnuroj enen kaj tiel oni povas fari la plej bazan kalkuladon. Per ĝuste ordigi tiujn logikajn pordojn, oni povas adicii kaj subtrahi nombrojn kaj krei primitivan komputilan memoron. La bazo por komputilo!
La bildo supre estas abstrakta reprezento de KAJ-pordo (AND-gate). Kiam kaj A kaj B estas havas la valoron 1 (glisiloj eniras), la ŝnuro eksteren ekpafas glisilojn. Kiam unu aŭ du enirejoj havas la valoron 0, ankaŭ la ŝnuro eksteren iĝas 0 kaj ĝi ne elsendas glisilojn. Tio ĉi estas nur ekzemplo de pluraj pordoj kun malsamaj kondiĉoj kiuj kune kreas komputilon. Ekzakte la samaj pordoj estas uzataj en fizikaj komputiloj, sed ili uzas elektron kaj transistorojn.
Ĉi tiu skemo montras kiel oni povas ligi malsamajn specojn de logikaj pordoj por krei adiciilon. Oni povas enmeti nombrojn ĉe A kaj B per la duuma nombrosistemo kaj S kaj Cout montras la sumon de la enirejoj. Oni povas ligi Cin kaj Cout al tiuj de aliaj adiciiloj por adicii eĉ pli grandajn nombrojn.
GOL estas Turing-kompleta. Tio signifas ke la sistemo kapablas la saman kiel hipoteza Turing-maŝino. Oni povas do pruvi ke oni povas solvi ajnan matematikan problemon per la sistemo se oni havas senfine longan tempon. Tio signifas ke teorie, GOL povus solvi ajnan problemon kiun la plej bonaj komputiloj povas solvi. Praktike GOL neniam venkos komputilojn tamen, pro tio ke ni bezonas komputilojn por simuli ĉion krom la plej simplaj strukturoj.
Per nur kvar simplaj reguloj, GOL sukcesas simuli la plej diversajn aferojn. La eblecoj estas senfinaj kaj se oni rakontus pri la atingoj de GOL kiam ĝi unue estis priskribita, la homoj taksus onin freneza. Ĝi estas mirinda modelo de kiel etaj interagoj povas krei grandskalajn decidojn, kiel en insektaj kolonioj aŭ homaj socioj. Ĝi montras kiom fleksebla la koncepto de komputiloj estas kaj donas novan perspektivon pri inteligenteco. Eble la plej interesa parto estas la historio malantaŭ la ludo: ke von Neumann eksperimentadis kun memkopiantaj maŝinoj antaŭ la malkovro de DNA kaj ke Conway kaj li produktis tiom kompleksajn strukturojn antaŭ la vasta uzado de komputiloj. GOL eble ne estas la plej uzata parto de matematiko, sed ĝi certe estas unu el la plej belaj.
La ĉefpaĝo de la programo ”Golly” troveblas ĉi tie:
La GOL-Vikio, plena je strukturoj kaj sciindaĵoj, troveblas ĉi tie:
http://www.conwaylife.com/wiki/Main_Page
Por vidi kiel logikaj pordoj estas farataj el glisiloj, klaku ĉi tie:
https://www.youtube.com/watch?v=vGWGeund3eA