Gêm bywyd Conway

Oddi ar Wicipedia
Jump to navigation Jump to search
Un gwn gleider Gosper yn creu nifer o "gleiderau"

Mae'r Gêm Bywyd, sydd hefyd â'r enw symlach Bywyd, yn awtomatiaeth cellog a ddyfeisiwyd gan y mathemategydd Prydeinig John Horton Conway ym 1970.[1]

Mae'r gêm yn gêm sero chwaraewr, sy'n golygu bod ei esblygiad yn cael ei bennu gan ei gyflwr cychwynnol, does dim angen unrhyw mewnbwn pellach arno. Rhyngweithiwn â'r Gême Bywyd trwy greu cyflwr cychwynnol ac arsylwi sut mae'n esblygu. Gall chwaraewyr profiadol ceisio greu patrymau gyda nodweddion penodol.

Rheolau[golygu | golygu cod y dudalen]

Bydysawd y Gêm Bywyd yw grid orthogonal dau ddimensiwn anfeidrol o gelloedd sgwâr, Mae pob un ohonynt mewn un o ddwy cyflwr bosib, yn fyw neu'n farw, (neu'n boblog ac heb eu poblogi, yn y drefn honno). Mae pob cell yn rhyngweithio â'i wyth cymydog, sef y celloedd sydd wedi cysylltu'n llorweddol, yn fertigol neu'n groeslinol iddo. Ar bob cam mewn amser, mae'r trawsnewidiadau canlynol yn digwydd:

  1. Mae unrhyw gell fyw sydd â llai na dau gymydog byw yn marw, fel petai trwy danboblogi.
  2. Mae unrhyw gell fyw gyda dau neu dri chymydog byw barhau i fyw i'r genhedlaeth nesaf.
  3. Mae unrhyw gell fyw gyda mwy na thri chymydog byw yn marw, fel petai trwy orboblogi.
  4. Mae unrhyw gell farw gyda thri chymydog byw yn union yn dod yn gell fyw, fel petai trwy atgenhedlu.

Y patrwm cychwynnol yw hedyn y system. Mae'r genhedlaeth gyntaf yn cael ei chreu trwy gymhwyso'r rheolau uchod ar yr un pryd i bob cell yn yr hedyn; mae genedigaethau a marwolaethau yn digwydd ar yr un pryd. Weithiau gelwir y foment arwahanol pryd mae'r genedigaethau a'r marwolaethau hyn yn digwydd yn dic. Mae pob cenhedlaeth yn ffwythiant pur o'r un flaenorol. Mae'r rheolau yn parhau i gael eu gweithredu dro ar ôl tro i greu cenedlaethau pellach.

Gwreiddiau[golygu | golygu cod y dudalen]

Ddiwedd 1940, diffiniodd John von Neumann bywyd fel creadigaeth (fel bod neu organeb) a all atgenhedlu ei hun ac efelychu peiriant Turing. Roedd Von Neumann yn dychmygu rhyw declyn peirianyddol a fyddai’n defnyddio cydrannau electromagnetig yn arnofio ar hap mewn hylif neu nwy.[2] Nid oedd hyn yn realistig gyda'r dechnoleg a oedd ar gael ar y pryd. Dyfeisiodd Stanislaw Ulam awtomatiaeth cellog er mwyn efelychu teclynnau electromagnetig damcaniaethol von Neumann. Mewn sawl papur trafododd Ulam ddefnyddio cyfrifiaduron i efelychu ei awtomatiaeth cellog ar grid dau ddimensiwn. Ar yr un pryd, ceisiodd Von Neumann adeiladu awtomatiaeth cellog Ulam. Er ei fod yn llwyddiannus, roedd yn brysur gyda phrosiectau eraill a gadawodd rai manylion yn anorffenedig. Roedd ei awtomatiaeth yn gymhleth oherwydd roedd yn ceisio efelychu ei declyn peirianneg ei hun. Dros amser, darparwyd fersiynnau symlach gan ymchwilwyr eraill, a'u cyhoeddi mewn papurau a llyfrau.  

Dechreuodd John Conway wneud arbrofion ym 1968 gydag amrywiaeth o wahanol reolau awtomataidd cellog 2D,[3] ar ôl iddo cael ei ysgogi gan cwestiynnau rhesymeg fathemategol ac efelychiadau Ulam. Nod cychwynnol Conway oedd diffinio awtomatiaeth cellog diddorol ac anrhagweladwy. Felly, roedd e eisiau i rhai cyflyrau para am amser hir cyn iddynt marw, ac i rhaieraill fynd ymlaen am byth heb ganiatáu unrhyw ailadrodd, ac yn y blaen. Roedd yn her sylweddol ac yn broblem agored am flynyddoedd cyn i arbenigwyr ar awtomatiaeth cellog lwyddo i brofi bod Gêm Bywyd Conway wedi arddangos cyflwr a oedd yn 'fyw' yn yr ystyr y fodlonodd dau ofyniad cyffredinol Von Neumann.

Wrth dylunio'r gêm dewisodd Conway ei reolau yn ofalus, er mwyn i'r gêm bodloni'r meini prawf canlynol:

  1. Ni ddylai fod unrhyw dwf ffyrnig.
  2. Dylai fod patrymau cychwynnol bach yn bodoli gyda chanlyniadau anhrefnus, anrhagweladwy.
  3. Dylai fod potensial i creu adeiladwyr cyffredinol von Neumann (cyflyrau hunan-dyblygiedig).
  4. Dylai'r rheolau fod mor syml â phosibl, wrth gadw at y cyfyngiadau uchod.[4]

Ymddangosodd y gêm yn gyhoeddus yn gyntaf yn rhifyn Hydref 1970 o'r Scientific American, yng ngholofn "Gemau Mathemategol" Martin Gardner. Yn ddamcaniaethol, mae gan Gêm Bywyd Conway y bwer o beiriant Turing cyffredinol: gall unrhyw beth y gellir ei gyfrifo'n algorithmig cael ei cyfrifo o fewn Bywyd.[5][6][7] Ysgrifennodd Gardner, "Oherwydd tebygrwydd Bywyd â twf, cwymp ac addasiadau cymdeithas o organebau byw, mae'n perthyn i ddosbarth mwymwy poblogaidd o'r hyn a elwir yn 'gemau efelychu' (gemau sy'n debyg i brosesau bywyd go iawn)."[8]

Ers ei gyhoeddiad, mae Gêm Bywyd Conway wedi denu llawer o ddiddordeb, oherwydd y ffyrdd rhyfeddol y gall patrymau esblygu. Mae academyddion o amryw o feysydd, megis gwyddoniaeth gyfrifiadurol, ffiseg, bioleg, biocemeg, economeg, mathemateg, athroniaeth, a gwyddorau cynhyrchiol wedi defnyddio'r ffordd y gall patrymau cymhleth ymddangos trwy weithredu rheolau syml y gêm. Hefyd defnyddir y gêm i gyfleu'r syniad eithaf gwrth-reddfol y gall dyluniad a threfnymddangos ar ben eu hun yn absenoldeb dylunydd. Er enghraifft, mae'r gwyddonydd gwybyddol Daniel Dennett wedi defnyddio "bydysawd" Gêm Bywyd Conway i ddangos esblygiad posibl cysyniadau athronyddol cymhleth, megis ymwybyddiaeth ac ewyllys rydd, o'r set gymharol syml o ddeddfau penderfyniadol ffisegol sy'n rheoli ein bydysawd.[9][10][11]

Enghreifftiau o batrymau[golygu | golygu cod y dudalen]

Mae nifer o wahanol fathau o batrymau i'w cael yn y Gêm Bywyd, a gellir eu grwpio yn ôl eu hymddygiad. Mae mathau o batrymau cyffredin yn cynnwys: bywydau llonydd, nad ydynt yn newid o un genhedlaeth i'r llall; osgiladuron, sy'n dychwelyd i'w cyflwr cychwynnol ar ôl nifer penodol o genedlaethau; a llongau gofod, sy'n symyd eu hunain ar draws y grid.

Isod, dangosir enghreifftiau sy'n ymddangos yn aml[12][13] o'r tri math o batrymau uchod. Dangosir chelloedd byw yn ddu a chelloedd marw yn gwyn. Mae'r cyfnod yn cyfeirio at nifer y diciau y mae'n rhaid i batrwm itereiddio drwyddynt cyn i'r batrwm dychwelyd i'w ffurfwedd gychwynnol.

Bywydau llonydd
Bloc Game of life block with border.svg
Cwch-
gwenyn
Game of life beehive.svg
Torth Game of life loaf.svg
Cwch Game of life boat.svg
Twb Game of life flower.svg

Osgiladuron
Blinciwr
(cyfnod 2)
Game of life blinker.gif
Llyfant
(cyfnod 2)
Game of life toad.gif
Begwn
(cyfnod 2)
Game of life beacon.gif
Pylsar
(cyfnod 3)
Game of life pulsar.gif
Penta-
decathlon
(cyfnod 15)
I-Column.gif

Llongau ofod
Gleider Game of life animated glider.gif
Llong-
ofod
ysgafn
(LWSS)
Game of life animated LWSS.gif
Llong-
cofod
canolog
(MWSS)
Animated Mwss.gif
Llong-
ofod
trwm
(HWSS)
Animated Hwss.gif

Y pulsar [14] yw'r osgiladur cyfnod 3 mwyaf cyffredin. Mae mwyafrif yr osgiliaduron sy'n ymddangos yn naturiol yn gyfnod 2, fel y blinciwr a'r llyffant, ond gwyddwn bod osgiliaduron sawl cyfnod yn bodoli,[15] a sylwir ar osgiliaduron cyfnodau 4, 8, 14, 15, 30 ac ychydig o rai eraill yn ymddangos o amodau cychwynnol ar hap.[16] Gelwir patrymau sy'n esblygu am gyfnodau hir cyn sefydlogi yn Methuselahs. Y Methuselah cyntaf a ddarganfuwyd oedd yr R-pentomino. Mae Diehard yn batrwm sy'n diflannu yn y pen draw, yn hytrach na sefydlogi, ar ôl 130 cenhedlaeth. Tybir taw hwn yw'r hiraf posib ar gyfer patrymau â saith neu lai o gelloedd.[17] Mae Acorn yn cymryd 5206 cenhedlaeth i gynhyrchu 633 o gelloedd, gan gynnwys 13 o gleiderau sy'n dianc.[18]

Yr R-pentomino
Diehard
Acorn

Yn wreiddiol tybiodd Conway na all unrhyw batrwm dyfu am gyfnod amhenodol - hy, ar gyfer unrhyw cyflwr cychwynnol â nifer meidraidd o gelloedd byw, ni all y boblogaeth dyfu y tu hwnt i ryw derfyn uchaf meidraidd. Pan ymddangosodd y gêm yn gyntaf, cynigiodd Conway wobr o hanner cant o ddoleri i'r person cyntaf a allai brofi neu wrthbrofi'r rhagdybiaeth cyn diwedd 1970. Enillwyd y wobr ym mis Tachwedd gan dîm o Sefydliad Technoleg Massachusetts, dan arweiniad Bill Gosper; mae'r "gwn gleider Gosper" yn cynhyrchu ei gleider cyntaf ar y 15fed genhedlaeth, a gleider arall bob 30ain genhedlaeth o hynny ymlaen. Am nifer o flynyddoedd, y gwn gleider hwn oedd yr un hysbys lleiaf.[19] Yn 2015, darganfuwyd gwn o'r enw "gwn gleider Simkin", sy'n rhyddhau gleider bob 120fed genhedlaeth, sydd â llai o gelloedd byw ond sy'n cael ei wasgaru ar draws ardal mwy.[20]

Gwn gleider Gosper

Yn ddiweddarach, canfuwyd patrymau llai sydd hefyd yn tyfu'n anfeidrol. Mae'r tri phatrwm a ddangosir isod yn tyfu'n anfeidrol. Mae'r ddau gyntaf yn gadael blociau bywyd llonydd 2x2 wrth iddo teithio ar draws y grid.[21] Dim ond deg cell fyw sydd gan y cyntaf, y profwyd taw hwn yw'r lleiafrif.[22] Mae'r ail yn ffitio mewn sgwâr 5x5, ac mae'r drydedd ond un gell yn uchel.

Game of life infinite1.svg     Game of life infinite2.svg




Game of life infinite3.svg

Roedd darganfyddiadau diweddarach yn cynnwys gynnau eraill, sy'n llonydd, ac sy'n cynhyrchu gleiderau neu longau gofod eraill; trenau pwff, sy'n symud trwy adael llwybr o sbwriel ar ôl; a rhacanau, sy'n symud ac yn allyrru llongau gofod.[23]

Mae'r animeiddiad isod yn dangos enghraifft o drên pwff:


Amhenderfynadwyedd[golygu | golygu cod y dudalen]

Mae nifer o batrymau yn y Gêm Bywyd yn y pen draw yn gyfuniad o fywydau llonydd, osgiliaduron, a llongau gofod; a gelwir patrymau eraill yn anhrefnus. Gall patrwm aros yn anhrefnus am amser hir iawn nes iddo setlo i rhyw gyfuniad o rhain.

Mae Bywyd yn amhenderfynadwy, sy'n golygu ni fodoler algorithm all penderfyni os os ymddangosir rhyw batrwm o ystyried rhyw batrwm cychwynnol. Mae hyn yn ganlyniad o'r broblem stopio: y broblem o benderfynu a fydd rhaglen benodol yn gorffen rhedeg neu'n parhau i redeg am byth o ystyried rhyw fewnbwn cychwynnol.[24]

Hunan-ddyblygu[golygu | golygu cod y dudalen]

Ar 18 Fai 2010, cyhoeddodd Andrew J. Wade batrwm hunan-adeiledig, a elwir yn "Gemini". Mae'n creu copi ohono'i hun tra'n ddinistrio ei riant.[25][26] Mae'r patrwm hwn yn ddyblygu mewn 34 miliwn o genedlaethau, ac yn defnyddio tâp cyfarwyddiadau wedi'i greu allan o gleiderau yn osgiladu rhwng dau cyflwr sefydlog. Mae'r rhain, yn eu tro, yn creu copïau newydd o'r patrwm, ac yn dinistrio'r copi blaenorol. Mae Gemini hefyd yn llong ofod, a hi yw'r llong ofod gyntaf a adeiladwyd yn y Gêm Bywyd sy'n llong ofod oblique, hynny yw llong ofod nad yw'n orthogonal neu'n yn groeslin yn unig.[27][28] Ym mis Rhagfyr 2015, adeiladwyd fersiynau croeslin o Gemini.[29]

Ar 23 Tachwedd 2013, adeiladodd Dave Greene yr ddyblygwr cyntaf yng Ngêm Bywyd Conway sy'n creu copi cyflawn ohono'i hun, yn cynnwys y tâp cyfarwyddiadau.[30]

Cyfeiriadau[golygu | golygu cod y dudalen]

  1. Gardner, Martin (October 1970). "Mathematical Games – The fantastic combinations of John Conway's new solitaire game "life"". Scientific American 223 (4): 120–123. doi:10.1038/scientificamerican1070-120. ISBN 978-0-89454-001-1. https://archive.org/details/ahaahainsight00gard. Adalwyd 2011-06-26.
  2. Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. p. 1179. ISBN 978-1-57955-008-0.
  3. Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. p. 877. ISBN 978-1-57955-008-0.
  4. Conway, private communication to the 'Life list', 14 April 1999.
  5. It is a model and simulation that is interesting to watch and can show that simple things can become complicated problems.Paul Chapman (11 November 2002). "Life Universal Computer". Cyrchwyd 12 July 2009.
  6. Berlekamp, E. R.; Conway, John Horton; Guy, R. K. (2001–2004). Winning Ways for your Mathematical Plays (arg. 2nd.). A K Peters Ltd.
  7. Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. p. 877. ISBN 978-1-57955-008-0.
  8. Gardner, Martin (October 1970). "Mathematical Games - The Fantastic Combinations of John Conway's New Solitaire Game 'Life'". Scientific American (223): 120–123. https://web.stanford.edu/class/sts145/Library/life.pdf.
  9. Dennett, D. C. (1991). Consciousness Explained. Boston: Back Bay Books. ISBN 978-0-316-18066-5.
  10. Dennett, D. C. (1995). Darwin's Dangerous Idea: Evolution and the Meanings of Life. New York: Simon & Schuster. ISBN 978-0-684-82471-0.
  11. Dennett, D. C. (2003). Freedom Evolves. New York: Penguin Books. ISBN 978-0-14-200384-8.
  12. "Census Results in Conway's Game of Life". The Online Life-Like CA Soup Search. Archifwyd o y gwreiddiol ar 2009-09-10. Cyrchwyd July 12, 2009.
  13. "Spontaneous appeared Spaceships out of Random Dust". Achim Flammenkamp (1995-12-09). Cyrchwyd July 10, 2012.
  14. Stephen A. Silver. "Pulsar". The Life Lexicon. Cyrchwyd March 4, 2019.
  15. Game of Life Status page, Jason Summers, retrieved 2012-02-23.
  16. Achim Flammenkamp (2004-09-07). "Most seen natural occurring ash objects in Game of Life". Cyrchwyd 2008-09-16.
  17. Stephen A. Silver. "Diehard". The Life Lexicon. Cyrchwyd March 4, 2019.
  18. Koenig, H. (February 21, 2005). "New Methuselah Records". Cyrchwyd January 24, 2009.
  19. Stephen A. Silver. "Gosper glider gun". The Life Lexicon. Cyrchwyd March 4, 2019.
  20. The Hunting of the New Herschel Conduits, ConwayLife forums, April 28th, 2015, posts by Michael Simkin ("simsim314") and Dongook Lee ("Scorbie").
  21. "Block-laying switch engine". LifeWiki. Cyrchwyd July 12, 2009.
  22. Stephen A. Silver. "Infinite Growth". The Life Lexicon. Cyrchwyd March 4, 2019.
  23. Stephen A. Silver. "Rake". The Life Lexicon. Cyrchwyd March 4, 2019.
  24. Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your Mathematical Plays. Academic Press, 1982
  25. "Universal Constructor Based Spaceship". Conwaylife.com. Cyrchwyd 2012-06-24.
  26. "Gemini – LifeWiki". Conwaylife.com. Cyrchwyd 2012-06-24.
  27. Aron, Jacob (16 June 2010). "First replicating creature spawned in life simulator". New Scientist. https://www.newscientist.com/article/mg20627653.800-first-replicating-creature-spawned-in-life-simulator.html
  28. "Gemini – LifeWiki". Conwaylife.com. Cyrchwyd 2013-10-16.
  29. "Demonoid". LifeWiki. Cyrchwyd 18 June 2016.
  30. "Geminoid Challenge". Conwaylife.com. Cyrchwyd 2015-06-25.