משפט מייהיל-נרוד

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

למת הניפוח לשפות רגולריות

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

ביטויים רגולריים

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

פרדוקס המבחן האמריקאי

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

מיקסומיה – תורת הטבע השלמה

בשבועות האחרונים היה קשה להתעלם מפרסומת פייסבוק שחלחלה לה אט אט אל המעגלים שלי. בואו ניתן לה לדבר בעד עצמה: מי שילחץ על הלינק יגיע לאתר שכותרתו "מיקסומיה – תורת הטבע השלמה" ויש בו כל מני… דברים. הרושם המיידי שהתקבל … להמשיך לקרוא

שפות רגולריות – משפט קלייני

את הדיון שלי על שפות רגולריות התחלתי בהצגה של מושג האוטומט הסופי הדטרמיניסטי. האוטומט הזה היה מין מכונת חישוב תאורטית שמבצעת פעולה של זיהוי מתי מילה שייכת או לא שייכת לשפה כלשהי. הגדרתי את אוסף השפות הרגולריות בתור השפות שמתקבלות … להמשיך לקרוא

שפות רגולריות – תכונות סגור (חלק ב')

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

שפות רגולריות – תכונות סגור (חלק א')

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

אוטומטים אי דטרמיניסטיים ושאר מריעין בישין

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

אוטומטים ושפות רגולריות – מבוא

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

בעיית המטבעות

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

חישוב קוונטי – דברי סיום ופרידה

הפוסט הקודם שלי על האלגוריתם של שור היה המטרה המרכזית של סדרת הפוסטים שלי על חישוב קוונטי; הוא מייצג את השיא מבחינת הרמה הטכנית שאני רוצה להיכנס אליה, והוא תוצאה כל כך חשובה ומרכזית לכשעצמו שהוא מהווה מקום טוב לעצור … להמשיך לקרוא

חישוב קוונטי – האלגוריתם של שור

פרולוג, ובו סקירה מהירה של השור הנורא לפני שלוש וחצי שנים בערך, כשגילו של הבלוג היה חצי מגילו כיום, התחלתי סדרת פוסטים שכיניתי "פרוייקט תוצאות מפתיעות בסיבוכיות". המטרה שלי הייתה לקחת ארבע תוצאות ידועות בתורת הסיבוכיות שהופיעו במצגת של סקוט … להמשיך לקרוא

חישוב קוונטי – האלגוריתם של סימון

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

שערים ומעגלים קוונטיים – מבוא על קצה המזלג

הפוסט הזה הולך להתעסק בפרטי ה-Low level של חישוב קוונטי – הרכיבים הבסיסיים שבהם אנחנו משתמשים בחישוב כזה (שערים קוונטיים) ומה שאנחנו בונים באמצעותם (מעגלים קוונטיים). כשאני אומר Low-level הכוונה היא אך ורק לזה שאנחנו מתעסקים בפרטים הבסייסים שמהם מורכבים … להמשיך לקרוא

אלגוריתם גרובר

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

חישוב קוונטי – מה זה בדיוק

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

חישוב קוונטי – טלפורטציה, קידוד צפוף ושערים קוונטיים

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

קריפטוגרפיה קוונטית

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

חישוב קוונטי – עקרון אי הודאות של הייזנברג, פרדוקס EPR ומשפט בל

בפוסט הקודם שלי על חישוב קוונטי הצגתי פרוטוקול קטן וחביב שבאמצעותו אליס ובוב יכולים לעשות מה שנראה כמו "תקשורת מיידית בלי מגבלת מרחק" בעזרת המצב הקוונטי \(\left|00\right\rangle +\left|11\right\rangle \). בפוסט הזה אני רוצה לדבר קצת על ההשלכות הפיזיקליות של התכונות המוזרות … להמשיך לקרוא