#computational_models #computer_science

מכונת טיורינג

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

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

דוגמה לתיאור של תנועה על גבי הבקר תיראה כך
Pasted image 20220711015917.png
עבור התו a בסרט נסמנו ב $✓$ ונזוז ימינה.

נשים לב שהמצבים בבקר הם בעצם קונפיגורציה למה שראינו בסרט, q.a מעיד על כך שקראנו עכשיו a בסרט.

הגדרה פורמלית

מכונת טיורינג הינה שביעייה $(Q, Σ, Γ, δ, q_{0}, a c c, r e j)$

$Q$ קבוצת המצבים
$Σ$ א״ב קלט סופי , בהכרח יתקיים $␣ \notin Σ$
$Γ$ א״ב סרט סופי $Γ = Σ \cup {␣, ✓}$
$δ : (Q / {a c c, r e j} \times Γ) \to Q \times Γ \times {L, R}$

קונפיגורצייה במכונת טיורינג

במקרה זה קונפיגורצייה היא מחרוזת מהצורה

u q σ v : (u, v \in Γ^{*}, q \in Q, σ \in Γ)

$u$ - תוכן הסרט משמאל לראש שלפניו יש אינסוף רווחים (אפשר להכניס מספר סופי של רווחים)
$q$ - מצב המכונה
$σ$ תוכן הסרט במיקום הראש
$v$ תוכן הסרט מימין לראש שאחריו יש אינסוף רווחים (אפשר להכניס מספר סופי של רווחים)

מושג הגרירה הפורמלי זהה למושג הגרירה של הקונפיגרציות על אוטומט מחסנית .

קבלה דחיה והכרעה

אנחנו נחזור למושגים האלה עוד הרבה מאוד בנושא של שפות שלא ניתן לחשב אותן באמצעות טיורינג אבל בהגדרה הפורמלית מתקיים

מכונה $M$ מקבלת את השפה $L$ אם לכל מחרוזת בשפה יש גרירת קליין מהמצב ההתחלתי למצב acc.
מכונה $M$ דוחה מחרוזת אם הגרירת קליין על אותה מחרוזת תוביל אותה למצב rej
מכונה $M$ מכריעה את השפה $L$ אם היא מקבלת כל מחרוזת בשפה ודוחה כל מחרוזת שאינה בשפה.

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

תכנון מכונות טיורינג

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

Pasted image 20220711023045.png

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

בעזרת פסאודו- קוד : דוגמה לסגנון הכתיבה

שימוש במכונת טיורינג לחישוב פונקציות

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

Pasted image 20220711023812.png|450
נשים לב שהמכונה תמיד עוצרת בצד שמאל של הפלט הסופי.

וריאציות על מכונת טיורינג

וריאציות שקולות למכונת טיורינג הבסיסים

מכונת טיורינג עם סרט ימינה בלבד

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

מודל Ts

במודל זה יש מצב תזוזה חדשה , שהיא להשאר במקום, הראש לא חייב לזוז ימינה או שמאלה. המצב החדש מסומן כ $S$ . פונקציית המעברים תיראה באופן הבא

Δ : (Q \times Γ) \to (Q \times Γ \times {R, L, S})

מודל or

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

Δ : (Q \times Γ) \to (Q \times (Γ \cup {R, L}))

נרצה להוכיח שקילות בינה לבין המודל $T S$ .

כיוון ראשון לכל מכונה ממודל OR קיימת מכונה שקולה ממודל TS.

נגיד את שתי המכונות $M_{O R}$ ו $M_{T S}$ כשביעיות. כל הרכיבי זהים פרט לפונקציית המעברים שבמקרה שלנו מחולקים לשתיים:
נשים לב שהחוסר תנועה הוא לא בין מצבים אלא רק בהקשר של ראש הסרט.
מעברי תנועה אם במודל or נזוז לכיוון מסויים ללא כתיבה , במודל TS נבצע תזוזה ונכתוב את אותו הדבר היכן שהיינו (אנחנו יודעים שזה אפשרי).
מעברי כתיבה אם במודל נכתוב על הסרט בלי תנועה של הראש אז במודל TS ננצל את הכוח שלנו לעצור במקום ונשתמש במצב $S$ ככה גם במודל השני לא נזוז.

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

Q_{O R} = Q_{T S} \cup {q^{L} : q \in Q_{T S}} \cup {q^{R} : q \in Q_{T S}}

מה שנעשה פה בעצם זה נבנה מעבר ביניים במודל or על כל מעבר ב ts שהוא גם תזוזה וגם כתיבה, למשל אם נזוז ימינה ונכתוב אות מסויימת אז ממצב q1 למצב q2 אז במכונה החדשה, נבצע תזוזה ימינה ונגיע ל $q_{2}^{R}$ ולאחר מכן נכתוב על הסרט ונעבור למצב המקורי. כלומר הגדרנו עכשיו את פונקציית המצבים כך שעל כל מצב שמבצע תזוזה ימינה או שמאלה נעשה שני מעברים, אחד תזוזה ואחד כתיבה, אם התנועה היא $S$ אז לא צריך לשנות כלום.

מודל מרובה סרטים

במכונת טיורינג מרובת סרטים:

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

מודל 2D

מודל זה מאפשר סרט שהוא דו מימדי, השקילות באה לידי ביטוי בכך שאפשר למספר את התאים בסדר של אכלסונים לסרט חד מימדי ופשוט תזוזה למעלה תהווה תזוזה מתאימה בסרט החד מימדי.
Pasted image 20220711121444.png

מודל לא דטרמינסטי

המודל הזה כמעט זהה למודל הרגיל אלא שיש הבדל במושגי הקבלה והדחייה.
קבלה של מחרוזת במודל הלא הדטרמניסטי מבקשת שיהיה קיים חישוב של המכונה שמגיע למצב acc
דחייה של מחרוזת במודל הלא דטרמינסטי מבקש שכל חישוב של המכונה מגיע למצב rej.

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

סגירות במודל הלא דטרמינסטי

המודל הלא דטרמינסטי סגור ל

שרשור
סגור קלין
prefix
dropout

התזה של צרץ׳ טיורינג

סגירות

השפות הכריעות סגורות תחת

איחוד
חיתוך
משלים
סגור קלין

השפות הקבילות סגורות תחת

איחוד
חיתוך
שרשור
סגור קלין

Pasted image 20220712133840.png

היחס בין שפה כריעה לשפה קבילה

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

Pasted image 20220711173855.png ֿ

מכונת טיורינג ותוכניות מחשב

כל תוכנית מחשב ניתנת למימוש במכונת טיורינג. לכן, כל שפה שהינה כריעה על ידי מחשב היא גם כריעה על ידי מכונת טיורינג.
וכמו כן, כל שפה שהינה קבילה על ידי מחשב היא גם קבילה על ידי מכונת טיורינג.
אנחנו נתמקד בשפת התכנות simple
Pasted image 20220711174203.png

הזרימה היא כמו שאנחנו מכירים רצים שורה שורה, פרט לפקודת goto שמאפשרת קפיצה לשורה אחרת. עצירה על ידי פעולה stop. ויש פעולה guess שמאפשר בחירה באופן לא דטרמינסטי

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

דקדוק כללי

בדקדוק כללי גם בצד שמאל של כלל היצירה וגם בצד ימין יכול להיות או נעלם או נעלם עם מחרוזת לא ריקה.
Pasted image 20220711175338.png

למשל נבנה את $a a a a$ עם הדקדוק הנ״ל

\begin{matrix} S \to [S] \to [[S ∥ S]] \to [[a ∥ a]] \to [a a []] \to [a a] \to a a [a] \to a a a a [] \to a a a a \end{matrix}

דקדוק כללי לשפה ${a^{n} b^{n} c^{n}}$

\begin{matrix} S \to S^{'} [ \\ S^{'} \to a S^{'} b C | ε \\ C b \to b C \\ C] \to] c \\ ] \to ε \end{matrix}

דקדוק כללי ומכונת טיורינג

שפה הינה קבילה אם"ם יש דקדוק כללי שיוצר אותה.

ההירכייה של חומסקי

Pasted image 20220711181557.png
כלומר מכונת טיורינג מקבלת את כל השפות הנ״ל

התזה

מודל מכונת הטיורינג מגלם את המושג האבסטקרטי של "אלגוריתם". כלומר, כל אלגוריתם שניתן לתיאור כתהליך מכניסטי שבו:

התהליך מתבצע כסדרה של צעדים,
כל צעד מצריך כמות סופית של "עבודה",

ניתן גם לתיאור כמכונת טיורינג.

בפרט, אין מודל מכניסטי/אוטומטי חזק יותר ממכונת טיורינג.