בתשובה להפונז, 23/09/19 19:02
מהעשיתם ביום 20/9/19? 709624
easy • בתשובה להפונז יום ב', 23/9/2019, 19:52
לא. אין מחשב (קוונטי או קלאסי) שהוא מכונת טיורינג, ולו כי מכונת טיורינג היא בעלת סרט (זיכרון) אינסופי.
אם השאלה שלך היא אם מכונת טיורינג מסוגלת לחשב כל חישוב שמחשב קוונטי מסוגל לבצע, התשובה היא כן.
אם השאלה שלך היא אם מחשב קוונטי מסוגל לבצע חישוב בפחות צעדי חישוב (אסימפטוטית בגודל הקלט) מאשר מכונת טיורינג (דטרמיניסטית), התשובה היא שאנחנו לא יודעים.
מהעשיתם ביום 20/9/19? 709633
אח של אייל • בתשובה לeasy יום ב', 23/9/2019, 21:52
===> לא. אין מחשב (קוונטי או קלאסי) שהוא מכונת טיורינג, ולו כי מכונת טיורינג היא בעלת סרט (זיכרון) אינסופי.

תשובה קצת טהרנית.. לדעתי אפשר לכתוב בכיף‏1: מחשב קוואנטי ומחשב קלאסי שניהם שקולים למכונת טיורינג.

הסבר:

הדרך היחידה שבה מכונת טיורינג יכולה לנצל את הסרט האינסופי היא אם היא לעולם לא עוצרת. ויקי מספרת לי על הגרסא הזו של מכונת טיורינג, שהיא חסומה במשאבים: אוטומט חסום לינארית [ויקיפדיה]. בכל מקרה, בשפה בלתי פורמלית מקובל להגיד "מחשב א שקול למכונת טיורינג" או ש "שפת תכנות קוקוריקו שקולה למכונת טיורינג" והכוונה היא שהם יכולים ב*קירוב טוב* לחשב מה שכל מחשב (או שפת תכנות) אחרת יכולים לחשב. בקירוב טוב, דהיינו בהתעלם מכל מיני מגבלות זכרון, באגים, סיבוכיות וכו'. למשל בדיון 2762 גדי כותב: "חשוב לציין שגם המחשבים האמיתיים של ימינו, כמו זה שעל מסכו אתם קוראים מאמר זה, הוכחו כשקולים למכונת טיורינג – אין חישוב שניתן לבצע על מחשב מודרני, ואשר אינו ניתן לביצוע על מכונת טיורינג – ולהיפך. "

----
‏1 אלא אם כן אתה כותב מאמר פורמלי
מהעשיתם ביום 20/9/19? 709636
easy • בתשובה לאח של אייל יום ב', 23/9/2019, 22:25
זה פשוט לא נכון.
מכונת טיורינג, עבור אלגוריתם נתון (למעשה תיאור של מכונת טיורינג אחרת שמורצת על מכונת טיורינג אוניברסלית) לא מגבילה את גודל הקלט ויכולה להריץ את האלגוריתם על כל גודל של קלט, ובהנחה שהאלגוריתם תמיד עוצר, היא תעצור עבור קלט בכל גודל. לכל מחשב (קלאסי או קוונטי) יש מגבלה על גודל הקלט שהוא יכול להריץ, לפחות עבור אלגוריתמים מסויימים (אני מניח שחישוב זוגיות, למשל, ניתן לבצע במחשב קלאסי על כל גודל של קלט, אבל אלגוריתמים שדורשים שטח אחסון שתלוי בגודל הקלט, לא).
מהעשיתם ביום 20/9/19? 709637
אח של אייל • בתשובה לeasy יום ב', 23/9/2019, 23:35
הרשה לי לנסח את אחד המשפטים שכתבתי מחדש. אם יש לי מחשב עם משאבים של X ג'יגהבייט, אז היכולת העקרונית של מכונת טיורינג לרוץ על קלט של "יותר גדול מ X" היא ממש לא מעניינת. אם הפונז צריך לעבוד על קלט יותר גדול מ X אז הוא יקנה עוד דיסקים עד שזה יהיה לו יקר מדי או משעמם מדי.

בקריאה שניה של התגובה שלך אני לא חושב שיש ביננו הרבה מחלוקת, פשוט זה עניין של טעם. אם מישהו אומר לי "האם נכון להגיד שסרגל הוא ישר" אני לא אגיד לו "לא! ולו בגלל שישר זה צורה אידאלית שבכל רזולציה הנגזרת שלה היא אפס" - אלא אני אגיד לו "כן, עד כדי שגיאה קטנה"
מהעשיתם ביום 20/9/19? 709638
אח של אייל • בתשובה לאח של אייל יום ב', 23/9/2019, 23:37
*לישר יש נגזרת קבועה, לא אפס. וואטאבר
מהעשיתם ביום 20/9/19? 709645
צפריר כהן  (אתר) • בתשובה לאח של אייל יום ג', 24/9/2019, 6:03
תשובה טהרנית: הוא לא ישר. הוא קטע.
מהעשיתם ביום 20/9/19? 709655
הפונז • בתשובה לצפריר כהן יום ג', 24/9/2019, 10:57
קטעים איתכם.
מהעשיתם ביום 20/9/19? 709643
הפונז • בתשובה לאח של אייל יום ג', 24/9/2019, 5:22
אכן, זו הטרמינולוגיה שאני מכיר ולשם כיוונה השאלה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות