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

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

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

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

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

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

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

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

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

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

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

 

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

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