האם ניתן להוכיח שאלגוריתם שקול למכונת טיורינג

[לפטופ3]

האם ניתן להוכיח שאלגוריתם שקול למכונת טיורינג

שלום ,
קצת סוטה מנושאי הפורום , אבל כבר שאלתי בפורומים הרלוונטיים ומעניין אותי לראות אילו תשובות אקבל כאן:

שלום ,

אני חייב להודות שאני מזועזע , לא פחות!
כפי שכולנו יודעים ב-1900 התכנסו מיטב המתמטיקאים ושם העלה הילברט 23 בעיות פתוחות.
אחת מהן , המכונה הבעיה העשירית , למצוא אלגוריתם שייקבע בהינתן משוואה דיופנטית , האם היא פתירה.

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

אני לא בקיא בהוכחת המשפט העשירי - כיצד מוכיחים שאין אלגוריתם שבהינתן משוואה דיופנטית האם היא פתירה. אבל לגבי ה-Entscheidungsproblem , אני מבין שההוכחה שאין אלגוריתם כנ"ל מתבססת על השערת צ'רץ' שכל מכונה חישוב סבירה שקולה למכונת טיורינג.
כלומר אם אני מבין נכון , למעשה בהוכחה מסתמכים על כך שהמודל של טיורינג תופס את כל מה שראוי להיקרא "אלגוריתם".

אבל במתמטיקה לא מסתמכים על "תיזות" , אלא על הוכחות חד משמעיות ולא על תחושות בטן! (אני בטוח שמדובר בהרבה יותר מ"תחושת בטן" ועדיין כפי שאני רואה זאת , במתמטיקה זה שחור ולבן - יש הוכחה או אין הוכחה , אין אמצע!)

אם כך , האם למעשה אין הוכחה שאין אלגוריתם? האם ההוכחה מוכיחה שאין מכונת טיורינג ומכך לפי תזת צ'רץ' מניחה שאין אלגוריתם? (כי אני למשל לא רוצה לקבל את התזה שלו ללא הוכחה).
אם כך , למעשה ה-Entscheidungsproblem לא הוכחה עד עצם הזה , ואולי גם הבעיה העשירית!!!

אשמח לתשובות מעמיקות.

תודה!

 

[izackv]

אני די חלש במתמטיקה, אז אם אפשר לחדד...

לטענתך במתמטיקה זה שחור או לבן. (בלי תחושות בטן)
אז איך מגדירים אקסיומה?
והאם כל האקסיומות מוכחות?
ומה הסיפור הזה של "אוקלידית"? החוקים קבועים תמיד או רק במערכת _הנחות_ נתונה?

 

[vinney]

זה לא תיזת צ'רצ', זה משפט טיורינג-צ'רצ'.

מדובר ברדוקציה של בעית העצירה. הרי את בעית העצירה ניתן לנסח כפסוק לוגי. אם אפשר היה לקבוע לכל פסוק לוגי שרירותי אם הוא אמת או שקר במערכת כלשהי, היינו פותרים את בעיית העצירה.

 

[לפטופ3]

לפי מה שהבנתי שלשום מהמרצה שלי זו תזת צ'רץ'

התזה של צ'רץ' (או לפי ויקיפדיה תזת צ'רץ' - טיורינג):
"בכל מודל סביר של חישוב, ניתן לקבל ולהכריע את אותן שפות. "מודל סביר" (מושג לא־פורמלי).
דוגמאות: מכונת טיורינג, תחשיב למבדא, Random Access Machine, פונקציה רקורסיבית." (מתוך ההרצאה שהועברה ע"י המרצה שלי שהוא פרופסור , שלשום).

לינק לערך בויקיפדיה:
http://he.wikipedia.org/wiki/תזת_צ'רץ'-טיורינג

עדיין לא למדנו על בעיית העצירה , אבל שמעתי עליה רבות. יכול להיות שאתה מתכוון למשהו דומה. שים לב שאני מתכוון לתזה של טיורינג-צ'רץ' ולא למשפט , ולמעשה זו בדיוק כל הפואנטה:
שמדובר בתזה , ולא במשהו מוכח!

 

[vinney]

ההשערה אכן משתמשת במונחים לא מוגדרים

ולכן זאת השערה.

אבל מה שצ'ריצ' וטיורינג הוכיחו הוא שבמודל של מכונת טיורינג הבעיה בלתי פתירה.

אם יימצא מודל חישובי שונה, מן הסתם כל מחלקות השקילות החישובית יצטרכו להבנות מחדש, עבור אותו מודל. כמו שאמרו לך, אנחנו חיים בעולם שמבוסס על מספר אקסיומות, ברגע שמשנים אקסיומות המשפטים שמבוססים עליהם מתפרקים. למשל בגיאומטריה של אוקלידוס שכולנו מכירים שני קווים מקבילים לעולם לא נפגשים. אבל הפלא ופלא - בגיאומטריה של לובצ'בסקי האקסיומה הזאת לא מתקיימת.

כך שמבלי לדבר על מודל מסוים, אין משמעות לשאלה חישובית. ההשערה מדברת על כך שבכל מודל חישובי, המחלקות שקילות ישארו אותו דבר (לפחות מבחינת בעיות פתירות/בלתי פתירות).

המשפט אומר שבמודל של מכונת טיורינג, בעית ההחלטה (הdecision problem שממנה התחלתי) שקולה לבעית העצירה, ואנחנו יודעים שלבעית העצירה אין פתרון.

 

[לפטופ3]

זה בדיוק מה שמפריע לי!

"מה שצ'ריצ' וטיורינג הוכיחו הוא שבמודל של מכונת טיורינג הבעיה בלתי פתירה" - בדיוק! זו בדיוק הבעיה , מבחינתי לפחות. שההוכחה מתייחסת רק למודל החישובי של מכונת טיורינג.
כמובן שיש הוכחה פורמלית שבמודל של טיורינג הבעיה בלתי פתירה. אבל אין הוכחה שבמודל חישובי אחר , הבעיה אינה פתירה! וזו הפואנטה!

אני מכיר את כל "העניין" של האקסיומות , ואת העובדה שיש גיאומטריות לא אוקלידיות למשל כזו שאקסיומת המקבילים לא מתקיימת בה (אחת כזו משמשת בפיתוח תורת היחסות הכללית של איינשטיין). למעשה , אם אני לא טועה , אם בעבר הרחוק אקסיומות נחשבו ל"טענות בסיסיות נכונות ומובנות מאליהן" החל מתחילת המאה ה-20 אקסימות שימשו כ"כללי משחק" , לאו דווקא כאלו שמתארות נכון את המציאות/ אמיתות כלשהי.

"כך שמבלי לדבר על מודל מסוים, אין משמעות לשאלה חישובית." - יכול להיות באמת , אני מבין שלמעשה זו הבעיה המרכזית , שלא הייתה לפני מכונת טיורינג הגדרה פורמלית-מתמטית למושג אלגוריתם ושלמעשה מכונת טיורינג היא למעשה ההגדרה הפורמלית למושג אלגוריתם. כמובן שבמתמטיקה תמיד מתייחסים למודל/עולם,מבנה מסויים , אלא שלמעשה אני חושב שהשאלה הנכונה לשאול היא לא "האם ספציפית במודל של טיורינג הבעיה ניתנת לחישוב" , אלא :"האם קיים מודל חישובי כלשהו אשר בו הבעיה ניתנת לפתרון".
השאלה באמת , וזה מתייחס משפט הבא שלך "ההשערה מדברת על כך שבכל מודל חישובי, המחלקות שקילות ישארו אותו דבר (לפחות מבחינת בעיות פתירות/בלתי פתירות)" , האם העובדה שלא הוכיחו שלכל מודל חישובי יש את אותו כוח חישובי , מרמזת על כך שאולי כן קיים מודל חישובי שונה בכוחו מהמודלים המוכרים כיום.

הרי למעשה שכשהילברט חיפש אלגוריתם לפתרון הבעיה העשירית (נדמה לי שהוא אפילו לא השתמש במילה אלגוריתם) , עוד לא הייתה מכונת טיורינג , ולכן מבחינתנו כיום השאלה הנכונה לשאול היא "האם קיים מודל חישובי כלשהו שפתור את הבעיה" ולאו דווקא "האם מכונת טיורינג פותרת את הבעיה".



האמת שבמקום להתפלסף על כך אני צריך להגיש עבודה שמכילה תרגילים בסיסיים יחסית אודות מכונת טיורינג , אז אין לי זמן לחפור על זה לעומק , למרות שאני מאוד נהנה לקרוא את התשובות שלכם. כמו שהמרצה שלי אמר" "מדובר באחד מהרעיונות הכי גדולים המאה ה-20. אתם יכולים לצחוק על כך אבל זה נכון" (וכל הסטודנטים באמת התחילו לצחוק

).

 

[vinney]

שמע, חישוביות זה נושא מורכב

אנחנו פה מנפנפים ידיים ומדברים במושגים לחלוטין לא נכונים לעתים כי אנחנו לצורך העניין הדיוטות. קורס מבוא לחישוביות שעברתי, וזה שאתה עובר - אלה קורסים בסיסיים של תואר ראשון שמקנים אוסף של מושגים כללים להבנה בסיסית.

אתה אומר "תנו לי הוכחה שלכל מודל שהוא הטענה מתקיימת", אבל זה בלתי אפשרי. למה זה בלתי אפשרי? כי אנחנו לא יודעים מה אנחנו לא יודעים. אנחנו יכולים להתבסס רק על מה שכבר גילינו, או הנחנו. לכן, או שאנחנו מתבססים על עובדות שנגד עינינו, או שאנחנו מתבססים על הנחות יסוד שאימצנו. אנחנו לא יכולים להוכיח טענה בלי אחד מהשניים, ולעתים בלי שניהם ביחד.

לכן אין משמעות לטענה הכללית של "האם קיים מודל חישובי כלשהו שיפתור את הבעיה", כי הבעיה עצמה מנוסחת במושגים שמניחים בסיס כלשהו. הרי אם הילברט השתמש במושג "אלגוריתם" - איך הוא הגדיר אותו? הוא לא הגדיר אותו. לכן ההשערה של צ'רצ' לצורך העניין תקפה בדיוק כמו השאלה עצמה, כי היא משתמשת במושגים לא מוגדרים באותה המידה.

אבל ברגע שאתה מגדיר מה זה אלגוריתם - הגדרת בסיס, הגדרת מסגרת, ועכשיו אתה יכול להוכיח פתרון, וזה בדיוק מה שטיורינג עשה. הוא הגדיר מה זה "אלגוריתם", ההוכחה נבעה מזה.

 

[gadial22]

אני חושב שאתה נותן כאן אינטואיציה בעייתית מאו

"אנחנו לא יודעים מה אנחנו לא יודעים. אנחנו יכולים להתבסס רק על מה שכבר גילינו".

זו אמנם נשמעת כמו אינטואיציה טובה כדי להסביר את הבעיה, אבל תחשוב שניה מה קורה אם לוקחים את התשובה הזו ומחילים אותה על השאלה "איך אנחנו יכולים להיות בטוחים שלא קיימת מכונת טיורינג שפותרת את בעיית העצירה? הרי לא גילינו עדיין את כולן!"

ואכן, אולי יש איזו שהיא מכונת טיורינג שהיא ממש, ממש, ממש מתוחכמת ופותרת את בעיית העצירה באופן מדהים שלא חשבנו עליו? אז זהו, שלא; תורת החישוביות מוכיחה שמכונה כזו פשוט לא יכולה להתקיים, וזאת *למרות* שאנחנו לא יודעים מה אנחנו לא יודעים על כל הדברים השונים והמשונים שכן אפשר לפתור עם מכונות טיורינג.

אותו דבר אפשר לומר גם על המון הוכחות אי-קיום אחרות במתמטיקה. זה בדיוק הקסם - מתמטיקאים יודעים להוכיח דברים גם כשהם לא יודעים מה בדיוק הם לא יודעים.

 

[vinney]

אבל טיורינג עשה בדיוק את מה שאמרתי

הוא התבסס על הנחות, והראה שהן יכולות להתקיים.

כל גילוי מתחיל מזה שאנשים באים עם תיאוריה מסוימת הדורשת הוכחה, אבל כל הוכחה באה תוך הסתמכות או על עובדות או על הנחות. או שניהם.

 

[gadial22]

נכון, אבל אתה צריך לשים לב להנחות שלו

הוא לא הניח שום ידע על מה שמכונות טיורינג יכולות לעשות או לא; למעשה, המאמר שלו הוא יצירת מופת של בריאת תיאוריה חדשה מכלום כמעט בלי שום הנחות מקדימות. יש לו רק התבססות על דברים סטנדרטיים במתמטיקה דוגמת הוכחה בדרך השלילה.

 

[vinney]

הוא דווקא כן הניח

הוא הניח סרט אינסופי, הוא הניח שמדובר בנתונים בדידים, וכו' וכד'.

 

[gadial22]

אלו לא באמת הנחות

אלו פשוט ההגדרות - זה המודל שטיורינג מתאר.

עדיין, אל תפספס את הנקודה העקרונית שלי כאן. גם אם "מניחים" סרט אינסופי ונתונים בדידים אנחנו עדיין לא יודעים כמעט בכלל מה המודל הזה יכול לעשות. בהקשר הזה כדאי מאוד להביא ציטוט של טיורינג מתוך מאמר מופתי אחר שלו:

The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are particularly subject. This is the assumption that as soon as a fact is presented to a mind all consequences of that fact spring into the mind simultaneously with it. It is a very useful assumption under many circumstancess, but one too easily forgets that it is false. A natural consequence of doing so is that one assumes that there is no virtue in the mere working out of consequences from data and general principles.

 

[vinney]

נכון, אלא לצורך העניין האקסיומות.

ב"הנחות" התכוונתי בדיוק לזה: קביעת דברים המגדירים את העולם שלך. אוקלידוס תיאר מודל גיאומטרי אחד, לובצ'בסקי תיאר מודל גיאומטרי אחר, ושניהם תקפים באותה מידה. אחד הניח שדרך שתי נקודות יעברו בדיוק שני ישרים שלעולם לא יפגשו, אחר הניח ששלושה.

אני לא אומר שההנחה היא מה המודל יכול לעשות, אני אומר שההנחה היא מה המודל.

אני טוען שאת השאלה העשירית אפשר לפתור רק בהנתן מודל מסוים כלפי אותו המודל. כרגע יש לנו פתרון בהנתן המודל של טיורינג, ולפטופ3 שואל למה אי אפשר לפתור את השאלה עבור מודל כלשהו.

אני טוען שאי אפשר לקבוע אם מודל כלשהו יביא לתשובה חיובית או שלילית תמיד, מבלי לדעת מה המודל. אם אני מבין נכון - זה גם מה שאתה אומר.

 

[gadial22]

שוב, אני חושב שאתה מפספס את הנקודה שלי

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

אני אקח את המשפט שלך ואעשה עליו וריאציה שמתאימה להקשר שלנו:

"אני טוען שאת השאלה העשירית אפשר לפתור רק בהנתן מכונת טיורינג מסויימת כלפי אותה המכונה."

האם הטיעון הזה נכון? האם אכן לא ניתן להגיד משהו על *כל* מכונות הטיורינג? אפשר גם אפשר.

אולי גם אפשר לומר משהו על *כל* המודלים, אבל אנחנו לא רואים כרגע דרך טובה לעשות את זה, בעיקר בגלל שלאף אחד לא ברור מה המילה העברית הזו "מודל", אומרת בדיוק (אני קצת משקר - אפשר לתת הגדרה כללית למודל אבל הבעיה היא שהיא תתפוס גם מודלים שהם לא סבירים).

 

[vinney]

לא הבנתי

מה זה "כל מכונות טיורינג"? מכונת טיורינג זה מודל חישובי מסוים. מה המשמעות ל"כל מכונות טיורינג"? ככל הידוע לי יש רק מודל אחד שנקרא "מכונת טיורינג".

אולי גם אפשר לומר משהו על כל המודלים. מה שאני טוען הוא שאנחנו צריכים או הנחות או ידע כדי לעשות את זה. אתה לא סותר את דבריי, רק מחזק. אתה אומר שאי אפשר גם לשלול דברים על כל המודלים, אבל שלילה זה בסך הכל עוד סוג של טענה.

 

[sudoer]

את הבעיה העשירית הכרתי פעם לעומק

וההוכחה, ארוכה, מסובכת, נעשו שלבים שונים על ידי כמה אנשים שונים כדי בכלל להגיע לרעיונות, ומתיאסביץ' בסוף כתב ספר. יופי. בכל מקרה, התשובה היא שאין אלגוריתם כזה עבור שלמים. יש כמה שדות אחרים שמעליהם דווקא יש פתרון (כמו כל שדה סופי אבל לא רק) - יש מאמר לא רע בויקיפדיה.

לגבי הבעיה הנוספת שהזכרת, אם אתה לא מאמין לטיורינג אתה יכול לקרוא גם את המאמרים המקוריים או ההוכחה של צ'רץ'.
הערך בויקיפדיה
מאמר ראשון

אתה יכול לגגל את המאמרים ב references ולהגיע למקורות עצמם.

בהצלחה

 

[לפטופ3]

הנה הסבר ממש ממש מפורט על הבעיה העשירית:

תודה רבה לך על התשובה. אני לא בטוח אם אתה הבנת לגמרי מה הבעיה שלי:

קודם כל לגבי הבעיה העשירית:
בבלוג של ד"ר גדי אלכסנדרוביץ' "לא מדויק" ממש בשבועות האחרונים , הוא דן בסדרת פוסטים שעוסקים בהוכחת הבעיה העשירית של הילברט. בדיוק לפני כמה ימים הוא פרסם עוד פוסט המשך לפוסטים האחרונים לגבי הבעיה:
http://www.gadial.net/2013/01/01/hilbert_tenth_recursive_diophantine_equivalence/

לגבי "אם אתה לא מאמין לטיורינג אתה יכול לקרוא גם את המאמרים המקוריים או ההוכחה של צ'רץ'": מתמטיקה אינה מתבססת על אמונה. מתמטיקה מתבססת על הוכחות. זה לא שאני לא מאמין לטיורינג , מה שמוכח אני לא מתיימר כרגע לשבור את הראש ולנסות להבין. מה שמטריד אותי הוא החלק שלא מוכח , אלא משמש כתזה.
"אתה יכול לקרוא גם את המאמרים המקוריים או ההוכחה של צ'רץ'" - זה בדיוק העניין! שאין הוכחה לתזה. זה לא שאני לא מאמין להוכחה , העניין הוא שאין הוכחה!!!

אני כרגע עמוס מאוד בלימודים , ואין לי זמן להתעסק בזה.
אם יש לך את המקורות , לינקים וכו' או שאתה יכול להוסיף עוד מידע על כל אחד מהדברים שהזכרת , אני יותר מאשמח

תודה!

 

[vinney]

נראה לי שהפרופסור בילבל אותך

או שלא הבנת אותו נכון. אם לא דיברתם על בעיית העצירה, כנראה שאתה רק בתחילת נושא החישוביות, והוא ניסה לתת לכם רקע היסטורי.

אתה צריך להבין שבמתמטיקה מוכיחים, אבל מתבססים על אקסיומות. ומה זה אקסיומה? "סמוך עליי אחי, שני ישרים מקבילים לא נפגשים". זה אקסיומה. אוקלידוס אמר לך לסמוך עליו - ואתה סומך עליו. או, אם קוראים לך לובצ'בסקי, לא סומך עליו ואומר "אבל הנה אחי, נפגשים! הלכה המערכת שלך, בוא נבנה חדשה".

יש איזשהו בסיס שממנו מתחילים שאי אפשר להוכיח. ועל זה מתבססים. ברגע שהבסיס הזה נשמט - הכל מתפרק.

ההשערה אומרת - "תשמטו את הבסיס - וואלה, לא יתפרק". המשפט אומר "על הבסיס הזה - אין פתרון. תביאו לי בסיס אחר - נראה מה קורה".

את הראשון לא ניתן להוכיח (לפחות בינתיים), את השני - כן, אבל עבור כל בסיס (קבוצה מוגדרת של אקסיומות) בנפרד.

טיורינג נתן את ההוכחה למערכת החישובית שאנחנו עובדים בה כרגע. כך שזה מוכח. אם אתה טוען שיש מערכת חישובית שעבורה הבסיס שעליו התבסס טיורינג לא מתקיים - אתה קודם כל צריך להראות את המערכת הזאת (חישוב קוואנטי? אולי, לא חקרתי לעומק), ואז לנסח את המשפטים מחדש עבור המערכת הזאת ולראות אם הם תקפים.

לא מן הנמנע שבמערכת שלא שקולה למכונת טיורינג (ולא שקולה לכל תת-מערכת של מכונת טיורינג), יהיה פתרון לבעית ההכרעה. יכול להיות, אבל נכון לעכשיו, לפחות ככל הידוע לי, אין מערכת שלא שקולה למכונת טיורינג או למערכת החלקית לה.

 

[לפטופ3]

קרא את מה שעניתי לך למעלה

,בנוסף |שמאל

תודה לך לך התשובה.
" אתה צריך להבין שבמתמטיקה מוכיחים, אבל מתבססים על אקסיומות. ומה זה אקסיומה? "סמוך עליי אחי, שני ישרים מקבילים לא נפגשים". זה אקסיומה. אוקלידוס אמר לך לסמוך עליו - ואתה סומך עליו. או, אם קוראים לך לובצ'בסקי, לא סומך עליו ואומר "אבל הנה אחי, נפגשים! הלכה המערכת שלך, בוא נבנה חדשה".

יש איזשהו בסיס שממנו מתחילים שאי אפשר להוכיח. ועל זה מתבססים. ברגע שהבסיס הזה נשמט - הכל מתפרק. "

זה לגמרי ברור לי , קרא את התגובה של אליך למעלה , עניתי על זה.

אני חושב שחלקכם קצת פספסתם את את הנקודה שלי ,אבל אין לי זמן כל כך לפרט שוב כי יש לי עבודה בחישוביות להגיש

, אבל בחלק השני של התשובה שלך שמעליי אתה נתת סוג של תשובה (כל החלק שמתחיל במשפט "טיורינג נתן את ההוכחה למערכת החישובית שאנחנו עובדים בה כרגע......." ועד הסוף").

ברור לי לחלוטין למה התכוונת בחלק השני , עניתי לך על זה לך בתגובה שלי למעלה (עד שכתבתי את תגובתי למעלה כבר הספקת להגיב שוב גם פה

).

אני שמח שקיבלתי תגובות יפות פה בפורום , למרות שהשאלה שלי חורגת מנושאי הפורום.
אני יותר מאשמח לקבל עוד תגובות , לא יודע עד כמה יהיה לי זמן להשיב במפרט אם בכלל , אם אין ספק שיש פה חבר'ה מביני עניין!
תודה.

 

[gadial22]

חישוב קוונטי לא רלוונטי

המודל הסטנדרטי של חישוב קוונטי (זה שבו קיים אלגוריתם יעיל לפירוק לגורמים) הוא טיורינג-שלם, דהיינו ניתן לסמלץ אותו עם מכונת טיורינג (לא בהכרח ביעילות, אבל זה לא רלוונטי לדיון הזה).

באופן כללי, אין מודל חישובי שנחשב סביר כיום ואין הוכחה שניתן לסמלץ אותו עם מכונת טיורינג. מודלים "קלאסיים" כמו פונקציות רקורסיביות, תחשיב למבדא ומכונות רגיסטרים הם שקולים למכונת טיורינג. גם כל שפת תכנות מקובלת כיום שקולה למכונת טיורינג. זה לא מוכיח שמחר לא יהיה מודל שחזק יותר ממכונת טיורינג, אבל זו הסיבה שבגללה ניסוח פורמלי של טענות חישוביות מתייחס תמיד למכונת טיורינג ולא ל"חישובים" באופן כללי.