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