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