חוק 30

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

חוק 30 הוא חוק בינארי חד-ממדי של אוטומט תאי שהוצג על ידי סטיבן וולפרם בשנת 1983.‏[1] וולפרם תיאר אותו כ"חוק האהוב עליו בכל הזמנים"‏[2] ופירט עליו בספרו, "A New Kind of Science". לפי שיטת הסיווג של וולפרם, חוק 30 הוא חוק ברמה 3, המציג התנהגות כאוטית.

חוק זה מעורר עניין מיוחד, משום שהוא יוצר דוגמאות מורכבות ואקראיות לכאורה על ידי כללים פשוטים ומוגדרים היטב. לכן, וולפרם מאמין שחוק 30, ואוטומט תאי בכלל, הם המפתח להבנה כיצד חוקים פשוטים יוצרים מבנים והתנהגויות מורכבים בטבע. לדוגמה, דפוס צבע שמייצג חוק 30 מופיע על קונכייתו של מין של חלזון ימי הנקרא חרוטון ארסי. בנוסף, חוק 30 שימש כמחולל מספרים אקראיים בתוכנה שיצר וולפרם, Mathematica, והוצע גם לשימוש כצופן זרם בקריפטוגרפיה. עם זאת, בחינתו של חוק 30 כמייצר מספרים רנדומליים במבחן כי בריבוע הציגה תוצאות ירודות בהשוואה לחוקים אחרים המבוססים על אוטומט תאי.‏[3]

מערכת כללים[עריכת קוד מקור | עריכה]

בכל האוטומטים התאיים היסודיים של וולפרם, אינסוף מערכים חד-ממדיים של תַאֵי אוטומט תאי נלקחים בחשבון, כאשר כל תא נמצא במצב התחלתי כלשהו. במרווחי זמן בדידים, כל תא משנה ספונטנית את מצבו, בהתבסס על מצבו הנוכחי ומצבם של שני התאים השכנים לו. עבור חוק 30, מערכת הכללים שקובעת את המצב הבא של האוטומט הם:

דפוס נוכחי 111 110 101 100 011 010 001 000
מצבו החדש של התא האמצעי 0 0 0 1 1 1 1 0

מבנים ותכונות[עריכת קוד מקור | עריכה]

הדפוס הבא נוצר ממצב התחלתי שבו תא יחיד במצב "1" (שחור) מוקף בתאים במצב "0" (לבן).

CA rule30s.png

פה, הציר האנכי מייצג זמן (עם הירידה בציר האנכי הזמן עולה) וכל קטע בציר האופקי מייצג את מצבם של כל התאים במערך בנקודת זמן מסוימת במהלך התפתחות הדוגמה. מספר מוטיבים מופיעים במבנה, כמו הופעות תכופות של משולשים לבנים ורצועת דפוס קבועה בצדו השמאלי של המבנה; עם זאת, למבנה כולו אין דפוס שאפשר להבחין בו. מספר התאים השחורים בדור n נקבע על ידי הרצף:

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (סדרה A070952, באתר האנציקלופדיה המקוונת לסדרות של מספרים שלמים)

והוא בערך n.

קונכייה של חרוטון ארסי, שדפוס צבעה דומה לחוק 30

כפי שניתן לראות בתמונה הנ"ל, חוק 30 מייצר לכאורה אקראיות למרות העדר כל דבר שיכול להחשב במידה סבירה כקלט אקראי. סטיבן וולפרם הציע להשתמש בטור האמצעי כמחולל פסבדו אקראי; הוא עבר מבחני רנדומליות סטנדרטיים רבים, ווולפרם השתמש בחוק זה בתוכנה Mathematica ליצירת מספרים שלמים אקראיים. למרות שחוק 30 מייצר אקראיות בדפוסי קלט רבים, יש אינסוף דפוסי קלט שמביאים לדפוסים חוזרים. דוגמה טריוויאלית לדפוס כזה היא דפוס קלט המורכב מ-"0" בלבד. דוגמה טריוויאלית פחות, שמצא מתיו קוק, היא קלט המורכב מאינסוף חזרות על הדפוס '00001000111000', עם חזרות אפשריות שמופרדות על ידי שש "1". דוגמאות נוספות רבות נמצאו על ידי Frans Faase, ראו דפוסים חוזרים בחוק 30.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Wolfram, S. (1983). "Statistical mechanics of cellular automata". Rev. Mod. Phys. 55: 601–644. doi:10.1103/RevModPhys.55.601. 
  2. ^ On Starting a Long-Term Company, S. Wolfram, 2005.
  3. ^ Sipper, Moshe; Tomassini, Marco (1996). "Generating parallel random number generators by cellular programming". International Journal of Modern Physics C 7 (2): 181–190. doi:10.1142/S012918319600017X.