» נושאי לימוד
» נושאי לימוד
יום שבת 6 ביוני 2020
מה זה מכונת טיורינג
דף ראשי  מכונת טיורינג  מה זה מכונת טיורינג גרסה להדפסה

מה זה מכונת טיורינג?

 

מכונת טיורינג היא מודל חישובי הבנויה בצורה הבאה:

המכונה מכילה בקר מרכזי שמכיל מספר סופי של מצבים (מצבי המכונה).

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

החלק השלישי של המכונה הוא הראש קורא- כותב, שיכול לזוז ימינה ושמאלה, לקרא ולכתוב.

 

 פעולות המכונה:

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

כותב סימן חדש במשבצת.

זז צעד אחד ימינה.

 זז צעד אחד שמאלה.

בכל מקרה עובר למצב חדש בבקר במרכזי.

 

 במקרה שהמכונה מנסה ללכת שמאלה, מעבר לקצה השמאלי, הראש נופל   והמכונה נתקעת. ז"א שהחישוב לא נגמר אלא נתקע.

 

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

 

מכונת טיורינג הינה חמישייה: S,h),(Q,S,d M=

כאשר: Q  -  קבוצת מצבים סופית של הבקר המרכזי.

S -  א"ב סופי (סימנים אפשריים בקלט).

S  ÎQ   מצב התחלתי.

Q Î h  מצב עצירה.

בסיום הפעולות נצפה שהראש שוב יהיה מימין לתוכן הפלט, ז"א, מימין לתוכן  הפלט.

d – פונקצית מעברים:

                   d:(Q – { h } ) x S  Q x (S È {R,L})

 

 

 

נבנה את המכונה:

 

 

 21-03-04 / 20:48  עודכן ,  31-12-03 / 20:25  נוצר ע"י שמרית דויטש  בתאריך 
 מכונת טיורינג - הקודםהבא - קונפיגורציה 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 2