נוסחת טאפר - הנוסחה שמציירת את עצמה

בואו ניגש ללב העניין. התבוננו בנוסחה הבאה:

\( \frac{1}{2}<\left\lfloor \mbox{mod}\left(\left\lfloor \frac{y}{17}\right\rfloor 2^{-17\left\lfloor x\right\rfloor -\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)},2\right)\right\rfloor \)

בלי פאניקה! הכל יוסבר.

ראשית, סימנים: \( \left\lfloor a\right\rfloor \) מסמל את הערך השלם התחתון של המספר \( a \), שמוגדר להיות המספר השלם הגדול ביותר שקטן או שווה ל-\( a \). למשל, \( \left\lfloor \frac{5}{3}\right\rfloor =1 \) ואילו \( \left\lfloor 2\right\rfloor =2 \). בנוסף, \( \mbox{mod}\left(a,n\right) \) מסמל את הערך שמתקבל כאשר לוקחים את המספר \( a \), מחלקים אותו ב-\( n \) ולוקחים את השארית. למשל, \( \mbox{mod}\left(3.3,2\right)=1.3 \). זה הכל.

המשוואה הזו מכילה שני משתנים - \( x,y \). שניהם יכולים לקבל כל ערך שהוא מספר ממשי. עכשיו משחקים את המשחק הבא: מסתכלים על המישור \( \mathbb{R}^{2} \) שהוא אוסף כל הנקודות \( \left(x,y\right) \) שהן מספרים ממשיים. לכל נקודה \( \left(x,y\right) \) כזו, אם כאשר מציבים את \( x,y \) בנוסחה אי השוויון שבה אכן מתקיים, צובעים את הנקודה \( \left(x,y\right) \) בצבע שחור; אם השוויון לא מתקיים, מותירים את הנקודה לבנה. כעת, אם נסתכל על התמונה שנקבל נראה שקיבלנו תמונה אינסופית שבה המוני נקודות פזורות פה ושם וקשה להבין מה קורה, אבל אם נצטמצם לריבוע קטן יחסית - באורך 17 וברוחב 105 - ונלך למקום המתאים, נראה את התמונה הבאה:

רגע, מה? זו תמונה של המשוואה שבעזרתה יצרנו את התמונה מלכתחילה! יש לנו כאן סוג של הפניה עצמית - משוואה שיודעת לצייר את עצמה. הזוי לחלוטין, ומתעלה אפילו על משפטי אי השלמות של גדל ותוכניות המחשב שיודעות להדפיס את הקוד של עצמן!

טוב, לא בדיוק.

הנוסחה הזו, שתוארה לראשונה על ידי ג’ף טאפר במאמר מ-2001, היא קסם במלוא מובן המילה. בהתחלה היא יוצרת רושם מדהים לחלוטין, של משהו בלתי אפשרי לגמרי שהגיע משום מקום, וזו תחושה נפלאה; אחר כך, כשמתחילים לחשוב על זה, מתברר מהר מאוד שהנוסחה משיגה את האפקט הזה על ידי תעלול לא מסובך במיוחד. זה מקלקל למדי את תחושת הפלא הראשונית, אבל מצד שני ההבנה של האופן שבו הקסם מתבצע היא תענוג בפני עצמו. כמובן שאני ממליץ לכולכם לחשוב על העניין בעצמכם; לא צריך הרבה יותר מאשר את הנוסחה שלעיל. יש רק פריט מידע אחד שטרם נתתי לכם - היכן בעצם מתחילה אותה תמונה מופלאה בתוך המישור?

ובכן, התמונה מתרחשת בנקודות עם קואורדינטת \( x \) בין 0 ל-105, דהיינו \( 0\le x\le105 \), וקואורדינטת \( y \) בין \( k \) ל-\( k+16 \), כלומר \( k\le y\le k+16 \). מיהו \( k \)? ובכן, מספר גדול לאין שיעור, שמתואר כאן עם רווחים כדי שיהיה קריא ולא יחרוג מגבולות השורה:

960 939 379 918 958 884 971 672 962 127 852 754 715 004 339 660 129 306 651 505 519 271 702 802 395 266 424 689 642 842 174 350 718 121 267 153 782 770 623 355 993 237 280 874 144 307 891 325 963 941 337 723 487 857 735 749 823 926 629 715 517 173 716 995 165 232 890 538 221 612 403 238 855 866 184 013 235 585 136 048 828 693 337 902 491 454 229 288 667 081 096 184 496 091 705 183 454 067 827 731 551 705 405 381 627 380 967 602 565 625 016 981 482 083 418 783 163 849 115 590 225 610 003 652 351 370 343 874 461 848 378 737 238 198 224 849 863 465 033 159 410 054 974 700 593 138 339 226 497 249 461 751 545 728 366 702 369 745 461 014 655 997 933 798 537 483 143 786 841 806 593 422 227 898 388 722 980 000 748 404 719

חלקכם כבר מנחשים, למראה המספר, שכאן בעצם מסתתרת החוכמה האמיתית - איכשהו הציור “מתחבא” בתוך המספר הזה. אבל איך?

לפני התשובה, הנה לכם משחק אינטראקטיבי - הזינו פנימה ערך של \( k \) (אפשר עם רווחים) וקבלו את התמונה עבור \( 0\le x\le105 \) ו-\( k\le y\le k+16 \):

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

485 848 307 199 443 192 292 484 775 523 195 446 750 165 771 267 770 474 169 193 207 700 51 005 067 907 907 541 020 178 059 194 196 266 956 625 065 918 178 608 930 545 615 357 634 623 847 182 313 037 176 237 950 246 743 833 022 219 851 353 244 464 297 196 422 052 599 618 366 926 759 595 937 669 170 337 031 986 392 318 882 323 798 450 346 890 393 645 210 909 095 498 636 458 859 695 483 157 512 356 430 020 530 323 399 745 167 547 408 250 078 493 473 637 808 923 733 333 196 160 087 525 223 963 972 079 179 702 470 428 441 062 803 798 996 831 022 016 431 226 755 561 007 151 709 067 404 979 608 249 899 531 206 486 163 294 240 248 539 016 274 762 746 088 450 590 994 298 169 153 574 985 192 777 454 048 087 559 586 719 989 59

ובכן, מה שטאפר עשה (בתור משהו שהוא בסך הכל קוריוז קצרצר בתוך מאמר רציני) היה לצייר את הנוסחה הזו, לחשב את הקידוד שמתאים לציור ולקבל את \( k \) שלנו. לכן קשה לומר שהנוסחה “מציירת את עצמה” - נכון לומר שהיא מציירת הכל, ולכן בפרט גם את עצמה, אבל זה פחות מעניין מתוכניות שמדפיסות רק את הקוד של עצמן או ממשפטי אי השלמות של גדל. כמובן, זה פותח פתח לאתגר חדש - לכתוב נוסחה שתכיל את \( k \) בצורה מפורשת וגם תצייר את עצמה, אבל זה יישאר כאתגר לקוראים בבית.

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

\( \left\lfloor \mbox{mod}\left(\left\lfloor \frac{y}{17}\right\rfloor 2^{-17\left\lfloor x\right\rfloor -\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)},2\right)\right\rfloor \)

נתחיל עם \( \left\lfloor \frac{y}{17}\right\rfloor \). בהנחה ש-\( k \) מתחלק ב-17 (והוא מתחלק - בדקו זאת!) הרי שלכל ערך \( k\le y\le k+16 \) נקבל ש-\( \left\lfloor \frac{y}{17}\right\rfloor =\frac{k}{17} \) (הסבירו לעצמכם למה). כלומר, ה-\( \left\lfloor \frac{y}{17}\right\rfloor \) הוא פשוט דרך מחוכמת להכניס את \( k \) לנוסחה בלי לכתוב אותו במפורש; ולמעשה, לא \( k \) הוא מה שמקודד את התמונה אלא \( \frac{k}{17} \) (מבחינה פילוסופית אפשר לטעון ששני המספרים הללו מקודדים את התמונה, אבל תכף נראה שיותר נכון לומר זאת על \( \frac{k}{17} \)). כדי לפשט לעצמי את החיים אסמן מעתה \( a=\frac{k}{17} \).

עכשיו אנחנו כופלים את \( a \) ב-2 בחזקת מינוס משהו מפלצתי. עזבו לבינתיים את המשהו המפלצתי - נסמן אותו ב-\( t \). מהו \( a2^{-t} \)? זה סימון אחר ל-\( \frac{a}{2^{t}} \), כלומר אנחנו מחלקים את \( a \) בחזקה גדולה של 2. הדבר הזה שקול להזזה של הספרות של \( a \) בייצוג בינארי, או בנקודת מבט אחרת - הזזה של מיקום הנקודה העשרונית בייצוג בינארי של \( a \).

הרבה יותר קל להבין את זה אם חושבים על מספרים בבסיס 10 כפי שאנחנו רגילים. הביטו לרגע במספר \( a=531 \). מספר חביב וטוב לב ואהוב על הבריות. כעת נתעלל בו ונחלק אותו ב-10, וזה כואב, כי הוא לא מתחלק ב-10. מה שנקבל הוא את המספר \( 53.1 \), שזה כמו \( 513. \), רק אחרי שהנקודה זזה צעד אחד שמאלה. ואם נחלק ב-\( 10^{2} \) כלומר ב-100 נקבל \( 5.31 \), כלומר הנקודה זזה שני צעדים שמאלה. באופן כללי אם מחלקים מספר ב-\( 10^{t} \) , מה שיקרה הוא שהנקודה בייצוג העשרוני שלו תזוז \( t \) צעדים שמאלה. כעת, אם נחלק מספר ב-\( 2^{t} \), הנקודה תזוז \( t \) צעדים שמאלה בייצוג של המספר בבסיס 2. כך למשל המספר 13 מיוצג בבסיס 2 בתור \( 1101 \) (כי \( 13=1\cdot2^{0}+0\cdot2^{1}+1\cdot2^{2}+1\cdot2^{3} \)). אם נחלק אותו ב-\( 4=2^{2} \) נקבל את המספר “שלוש ורבע”, שבבסיס בינארי הוא \( 11.01 \) (כי \( 11 \) בבינארי זה 3 ו-\( .01=0\cdot\frac{1}{2}+1\cdot\frac{1}{4} \)).

יפה, אם כן, הנוסחה מבצעת חישוב שאסמן את התוצאה שלו בתור \( b=a2^{-t} \), שבסך הכל לוקחת את \( a \) ומזיזה את הנקודה בייצוג הבינארי שלו \( t \) צעדים שמאלה. אז מבצעים את החישוב הבא: \( \left\lfloor \mbox{mod}\left(b,2\right)\right\rfloor \). כלומר, גם לוקחים את \( b \) מודולו 2, וגם לוקחים ערך שלם תחתון. גם על שתי הפעולות הללו כדאי לחשוב במונחים של הייצוג הבינארי של המספר. ביצוע הפעולה \( \mbox{mod}\left(b,2\right) \) לוקח את \( b \) ופשוט זורק לזבל את כל הספרות שמשמאל לנקודה העשרונית, חוץ מאשר את הספרה הראשונה שמשמאל לה. כלומר, \( \mbox{mod}\left(101101.1101,2\right)=1.1101 \). למה זה נכון? ובכן, את \( 101101.1101 \) אפשר לכתוב גם כסכום שני מספרים: \( 101101.1101=101100+1.1101 \). המספר השמאלי מתחלק ב-2 והמספר הימני קטן מ-2. זה מספיק כדי לראות את נכונות הטענה גם באופן כללי, אבל אשאיר לכם להשלים את הפרטים.

כעת, מה עושה הערך השלם התחתון למספר? פשוט מאוד - מחסל את כל הספרות שמימין לנקודה העשרונית. למה? כי זה החלק השברי של המספר, וזה בדיוק מה שנפטרים ממנו כשלוקחים ערך שלם תחתון.

במילים אחרות, \( \left\lfloor \mbox{mod}\left(b,2\right)\right\rfloor \) לוקחת את המספר \( b \) ומחזירה ספרה בודדת מתוך \( b \) - בדיוק את זו שנמצאת מייד משמאל לנקודה העשרונית בייצוג של \( b \) בבסיס בינארי. מסקנה: \( \left\lfloor \mbox{mod}\left(a2^{-t},2\right)\right\rfloor \) היא פונקציה שלוקחת את \( a \) ומחזירה בדיוק את הספרה במקום ה-\( t \)-י בייצוג הבינארי של \( a \) (כשמתחילים את הספירה של המקומות מ-0). עד כדי כך פשוט.

כעת נותר רק להבין מהו \( t \). ובכן, \( t=17\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right) \). בואו ננסה להבין את זה.

ראשית \( \left\lfloor x\right\rfloor \) ו-\( \left\lfloor y\right\rfloor \) פירושם שלמרות שהנוסחה יכולה לקבל ערכים ממשיים כלשהם של \( x,y \), היא מתעניינת רק בערכים השלמים שלהם; הנקודות \( \left(3.5,2.7\right) \) ו-\( \left(3,2\right) \) יהיו צבועות באותו הצבע, ולמעשה אם \( \left(3,2\right) \) צבועה בשחור, כך גם כל נקודה אחרת מהצורה \( \left(3.a,2.b\right) \) עבור מספרים כלשהם \( a,b \). נשאר רק להבין את \( 17\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right) \).

הנוסחה הזו בוודאי מוכרת לכל מי שקצת תכנת בחייו והתעסק עם מערכים דו ממדיים. בקצרה, מערך הוא אוסף תאי זכרון רצופים במחשב, שלכל אחד יש אינדקס (שמתחיל במקרה שלנו מ-0). אם \( A \) הוא מערך, אז \( A\left[4\right] \) מסמן את התא החמישי במערך (מתחילים מאפס!) וכן הלאה. כעת, מערך דו ממדי הוא מערך שבו לכל תא יש שתי קואורדינטות, למשל \( A\left[3\right]\left[5\right] \) מסמן את התא בעמודה מס’ 3 ושורה מס’ 5 (למתמטיקאים שביניכם, זו פשוט מטריצה בעוד שמערך הוא וקטור, אם כי במטריצות נהוג לתת את אינדקס השורה קודם וכאן עשיתי ההפך כדי להתאים לנוסחה של טאפר).

כעת, מערכים דו ממדיים מאוחסנים בזכרון של המחשב בתור מערכים רגילים, חד ממדיים; כאשר התוכנית נתקלת בגישה למערך מהצורה \( A\left[3\right]\left[4\right] \) היא מתרגמת את הפניה הזו לכתובת במערך החד ממדי המקורי. איך עושים את זה? ובכן, הרעיון הוא לאחסן את המערך הדו-ממדי “עמודה עמודה”. נניח שאורך כל עמודה במערך הדו-ממדי היא \( 6 \), אז עמודה מס’ 0 אוחסנה בתאי הזכרון 0-5; עמודה מס’ 1 בתאי הזכרון 6-11; עמודה 2 ב-12-17, ועמודה 3 ב-18-23, כאשר תא מס’ 4 בעמודה (כלומר, התא בשורה 4) הוא התא הרביעי מביניהם, דהיינו 22. כעת, את החישוב שעשינו אפשר לתאר בתור \( 22=3\cdot6+4 \), ובאופן כללי אם אורך כל עמודה במערך הוא \( s \) ואנחנו רוצים לגשת לתא \( A\left[x\right]\left[y\right] \), אז ניגש אל התא \( x\cdot s+y \).

נחזור אל \( t=17\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right) \). כאן הנוסחה היא אותו הדבר: ספציפית, \( s=17 \), כלומר במערך שלנו אורך כל עמודה הוא 17 (זהו גובה התמונה). כמו כן \( \mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right) \) בעצם בא לנטרל את \( k \) מתוך \( y \): הרי אמרנו ש-\( k\le y\le k+16 \), כלומר אפשר לכתוב \( y=k+y^{\prime} \) כאשר \( 0\le y^{\prime}\le16 \); אז \( y^{\prime}=\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right) \).

כעת הכל ברור - אני מקווה! מה שקורה הוא ש-\( a \) (שהוא, כזכור \( \frac{k}{17} \)) הוא מערך דו ממדי של ביטים שמקודד כמערך חד ממדי. ה”קידוד” הוא בדיוק הייצוג הבינארי של \( a \), ומה שנוסחת טאפר עושה הוא לדגום אותו ביט-ביט. הביטים שנוסחת טאפר קוראת יהיו 0 או 1, ולכן השוואה לחצי תצליח רק כשהביט הוא 1.

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

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