מכונת טיורינג לא-דטרמיניסטית
מתוך ויקיפדיה, האנציקלופדיה החופשית
מכונת טיורינג לא-דטרמיניסטית (Non-deterministic Turing machine) היא מודל מופשט ווריאציה למכונת טיורינג.
מכונת טיורינג לא-דטרמיניסטית מורכבת מהרכיבים הבאים:
- סרט המחולק לתאים הנמצאים זה אחר זה. בכל תא יש סמל יחיד מתוך אלפבית סופי כלשהו. אלפבית זה כולל סמל "ריק", ועוד סמל אחד לפחות. הסרט ניתן להארכה לימין ולשמאל ללא הגבלה, כלומר למכונת טיורינג יש סרט בכל כמות שתזדקק לה. תאים שטרם נכתב בהם דבר נחשבים לכאלה שמכילים את הסמל "ריק".
- ראש שמסוגל לקרוא ולכתוב את תוכנו של תא, ולזוז ימינה או שמאלה לאורך הסרט.
- רשימת מצבים סופית. אחד מהמצבים מסומן כמצב ההתחלתי.
- אוגר מצב, שבו נשמר מצבה הנוכחי של המכונה. בתחילת פעולת המכונה, מצבה הנוכחי הוא המצב ההתחלתי.
- טבלת פעולה, שמורה לראש מה לכתוב בתא, לאן לזוז (תא אחד ימינה או תא אחד שמאלה), ולאיזה מצב חדש לעבור, כל זאת בהתאם למצב הנוכחי (כפי שהוא רשום באוגר המצב) ולסמל שנקרא מהתא הנוכחי. אם אין בטבלה התייחסות לצירוף של המצב והסמל הנוכחיים, המכונה עוצרת. בניגוד למכונת טיורינג דטרמיניסטית בה לכל זוג של מצב וסמל יש לכל היותר פעולה אחת בטבלה, במכונת טיורינג לא-דטרמיניסטית לכל זוג של מצב וסמל ייתכנו מספר פעולות. המכונה תבחר את המצב המתאים לה ביותר באופן לא-דטרמיניסטי כאשר מצב כזה מוגדר כמצב שיביא את המכונה לבסוף למצב מקבל.
כל מרכיביה של מכונת טיורינג הם סופיים, מלבד הסרט שאינו מוגבל באורכו.
[עריכה] בחירת מצב באופן לא-דטרמיניסטי
כשעומדות בפני מכונת טיורינג לא-דטרמיניסטית מספר פעולות אפשריות, המכונה תבחר באפשרות שתאפשר לה להגיע לבסוף למצב מקבל - אם קיימת פעולה כזו.
ניתן להסתכל על אפיון זה בשני דרכים:
- המכונה מנחשת ובוחרת צעד אקראי, ובמזל בוחרת בצעד הנכון - אם קיים.
- כשהמכונה מגיעה להתפצלות אפשרית - היא פועלת בכל הדרכים במקביל. כלומר יוצרת עץ חישוב במקום מסלול חישוב יחיד שיש למכונת טיורינג דטרמיניסטית. אם אחד הענפים הגיע למצב מקבל - אזי המכונה הגיעה למצב מקבל וניתן לעצור.
[עריכה] שקילות למודל הדטרמיניסטי
מבחינת יכולת חישוב, על אף שנראה כי מכונת טיורינג לא-דטרמיניסטית חזקה יותר ממכונת טיורינג דטרמיניסטית, הוכח כי יכולת החישוב של המכונות שקול. כל חישוב שניתן לבצע במודל הדטרמיניסטי, ניתן לבצע גם במודל הלא-דטרמיניסטי, ולהיפך. מכאן שיכולת החישוב של מכונת טיורינג לא-דטרמיניסטית שקולה לכל מחשב.
כאמור שקילות זו מוכחת מבחינת החישוביות, אך נושא הסיבוכיות פחות ברור. קבוצת הבעיות שניתן לפתור באמצעות מכונת טיורינג לא-דטרמיניסטית בפרק זמן פולינומי נקראת NP, ואילו קבוצת הבעיות שניתן לפתור באמצעות מכונת טיורינג דטרמיניסטית בפרק זמן פולינומי נקראת P. השאלה האם P=NP (האם כל בעיה שניתן לפתור בזמן פולינומי באופן לא-דטרמיניסטי ניתן לפתור בזמן פולינומי גם באופן דטרמיניסטי) היא שאלה פתוחה, כלומר כזו שאין לנו הוכחה לנכונותה או דוגמה להפרכתה.
קיים אלגוריתם המאפשר מעבר בין מכונת טיורינג דטרמיניסטית ללא-דטרמיניסטית, ולהיפך.
[עריכה] לקריאה נוספת
- דוד הראל, אלגוריתמיקה - יסודות מדעי המחשב, האוניברסיטה הפתוחה, 1991
- שמואל וינוגרד, מכונת טיורינג, בכתב העת "מחשבות"
