שיחה:תורת החישוביות/שקילות מודלי חישוב

סימלוץ מ"ט מרובת סרטים

הייתי רוצה לדעת אם אכן יש דרך נוספת, או שאני הוא שלא הבנתי כראוי. טענתי היא שאין צורך לשנות את אלפבית הקלט. אלא יש להשתמש במצבי בקרה מרובים, ולדוגמא: אם נדרש לכתוב על הסרט העליון 0 ועל השני 1 במהלך השלב הראשון, ובשלב השני להחזיר את הראש התחתון שמאלה ואת העליון ימינה ולכתוב על הסרט העליון את מה שכתוב כעת בסרט התחתון ולכתוב על התחתון את מה שכתוב כעת בסרט העליון (ולא משנים כרגע שאר השלבים) אני מגדיר:"כתוב על הסרט 0 ועבור למצב 01, אחר כך עבור למצב 01L והזז את הראש ימינה, כעת עליך לעבור למצב שנקבע מראש לפי הקלט הנתון כעת ולכתוב 1 במקום שבו אתה נמצא כעת".--שואל (שיחה) 23:06, 12 בפברואר 2019 (IST)

מכונה מתקדמת בלבד

לא הבנתי את ההוכחה. אני רואה אפשרות לסמלץ כל מכונה רגילה באמצעות מכונה מתקדמת בלבד, ובתנאי שכשהיא עוברת למצב סופי היא עוצרת. בפונקציה שהוזכרה לדוגמא, שהמכונה צריכה לקרוא את כל מה שכתוב בסרט ולהוציא כפלט את האות האחרונה, אני קודם כל מגדיר את האלפבית כך שכל רצף חוקי הוא בעצם אות אחת (והרי מספר הרצפים החוקי סופי! שאם לא כן גם מכונה רגילה לא תוכל לתת כפלט את האות ה"אחרונה" שאינה קיימת), כעת פשוט נגדיר את פונקציית המעברים כך שלכך אות באלפבית שבזיכרון יש אות כנגד בפלט. למשל: אם התא הראשון מכיל את האות "רקםעק'י ום" אז הפלט הוא "ם" וכן הלאה. כך בעצם גם מכונה שיש לה שני תאים בלבד אחד למידע הקלט ואחד למקום שאיליו הראש עובר במצב הסופי, ויש לה תנועה קדימה בלבד, יכולה לעשות כל פונקציה שמכונה סטנדרטית יכולה לעשות.--שואל (שיחה) 20:40, 4 במרץ 2019 (IST)