מכונות טיורינג דומות למכונות אוטומטיות סופיות/מצב סופי אבל יש להן היתרון של זיכרון בלתי מוגבל … הן מסוגלות לדמות מחשבים נפוצים; בעיה שמחשב נפוץ יכול לפתור (בהינתן מספיק זיכרון) תהיה ניתנת לפתרון גם באמצעות מכונת טיורינג, ולהיפך.
מה ההבדל בין RAM ל-TM?
מכונת טיורינג לא יכולה מכונת RAM יכולה לעשות חשבון ב-O(1) (תחת הגבלות מסוימות). מכונת טיורינג לא יכולה. מכונות טיורינג מדמות באופן פולינומי מכונות RAM, כלומר, עבור קבוע c כלשהו, ניתן לדמות כל מכונת RAM הפועלת בזמן O(nk) על ידי מכונת טיורינג הפועלת בזמן O(nck).
האם הקלטת של מכונת טיורינג אינה מוגבלת?
A Turing Machine (TM) היא מכונת מצבים המורכבת משני זיכרונות: קלטת ללא גבולות וטבלת בקרת מצבים סופית. הקלטת מכילה נתונים כסמלים. למכונה יש סט קטן מאוד של פעולות מתאימות, 6 בכלל (לקרוא, לכתוב, להזיז שמאלה, להזיז ימינה, לשנות מצב, לעצור) על הקלטת.
למה מכונת טיורינג היא חזקה?
כמה חזקות מכונות טיורינג? מכונות טיורינג יכולות לקבל כל שפה רגילה או נטולת הקשר. מכונות טיורינג יכולות לבצע חישובים אריתמטיים בסיסיים … התזה של טיורינג קובעת שכל חישוב שניתן לבצע ב"אמצעים מכניים" יכול להתבצע על ידי מכונת טיורינג (התעלמות מבעיות יעילות).
האם מכונות טיורינג יכולות לעבור לנצח?
turing(turingDescrip) לא יכול לעצור או לולאה לנצח; זה לא הגיוני בכל מקרה.
