שיחה:תורת החישוביות/שקילות מודלי חישוב: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
שואל (שיחה | תרומות)
שואל (שיחה | תרומות)
 
שורה 2:
 
הייתי רוצה לדעת אם אכן יש דרך נוספת, או שאני הוא שלא הבנתי כראוי. טענתי היא שאין צורך לשנות את אלפבית הקלט. אלא יש להשתמש במצבי בקרה מרובים, ולדוגמא: אם נדרש לכתוב על הסרט העליון 0 ועל השני 1 במהלך השלב הראשון, ובשלב השני להחזיר את הראש התחתון שמאלה ואת העליון ימינה ולכתוב על הסרט העליון את מה שכתוב כעת בסרט התחתון ולכתוב על התחתון את מה שכתוב כעת בסרט העליון (ולא משנים כרגע שאר השלבים) אני מגדיר:"כתוב על הסרט 0 ועבור למצב 01, אחר כך עבור למצב 01L והזז את הראש ימינה, כעת עליך לעבור למצב שנקבע מראש לפי הקלט הנתון כעת ולכתוב 1 במקום שבו אתה נמצא כעת".--[[משתמש:שואל|שואל]] ([[שיחת משתמש:שואל|שיחה]]) 23:06, 12 בפברואר 2019 (IST)
 
== מכונה מתקדמת בלבד ==
 
לא הבנתי את ההוכחה. אני רואה אפשרות לסמלץ כל מכונה רגילה באמצעות מכונה מתקדמת בלבד, ובתנאי שכשהיא עוברת למצב סופי היא עוצרת. בפונקציה שהוזכרה לדוגמא, שהמכונה צריכה לקרוא את כל מה שכתוב בסרט ולהוציא כפלט את האות האחרונה, אני קודם כל מגדיר את האלפבית כך שכל רצף חוקי הוא בעצם אות אחת (והרי מספר הרצפים החוקי סופי! שאם לא כן גם מכונה רגילה לא תוכל לתת כפלט את האות ה"אחרונה" שאינה קיימת), כעת פשוט נגדיר את פונקציית המעברים כך שלכך אות באלפבית שבזיכרון יש אות כנגד בפלט. למשל: אם התא הראשון מכיל את האות "רקםעק'י ום" אז הפלט הוא "ם" וכן הלאה. כך בעצם גם מכונה שיש לה שני תאים בלבד אחד למידע הקלט ואחד למקום שאיליו הראש עובר במצב הסופי, ויש לה תנועה קדימה בלבד, יכולה לעשות כל פונקציה שמכונה סטנדרטית יכולה לעשות.--[[משתמש:שואל|שואל]] ([[שיחת משתמש:שואל|שיחה]]) 20:40, 4 במרץ 2019 (IST)
חזרה לדף "תורת החישוביות/שקילות מודלי חישוב".