תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
מ הגהה
Atavory (שיחה | תרומות)
מ ←‏מבוא: קישורים פנימיים
שורה 6:
[[קובץ:Turing Machine.png|ממוזער|250px|איור של "מכונת טיורינג" עם סרט זיכרון אינסופי]]
ניתן לחשוב על מכונת טיורינג כעל [[w:מכונת מצבים|מכונת מצבים]] פשוטה (בקר / "אוטומט") שבכל צעד חישוב יכול לשנות את מצבו בהתאם לקלט שלו. למכונה יש גישה ל'''סרט זיכרון''' - סרט אינסופי של תאים, ובכל תא כתובה אות יחידה. למכונה יש "ראש קורא/כותב" הממוקם על אחד תאי הזיכרון. בכל צעד, בהתאם למצב הנוכחי של המכונה ולאות הכתובה בתא עליו מצביע הראש הקורא/כותב, המכונה יכולה להחליט מה לעשות: לאיזה מצב חדש לעבור, איזו אות לכתוב בתא הזיכרון עליו עומד הראש הקורא/כותב, והאם להזיז את הראש (צעד אחר ימינה או שמאלה).
 
{{חלון מידע|להרחבה בנושא מכונות מצבים, ראו [[אוטומטים ושפות פורמליות]].}}
 
==הגדרה==