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