משהו נחמד שמצאתי

[johnny d]

זו כבר הגדרה סובייקטיבית.

 

[ron369]

לא שמעת על התזה של טיורינג,

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

 

[johnny d]

אתה שוב דבק לאקסיומות

אתה מדבר על Church–Turing thesis. ואכן מה שאני אומר סותר את התזה הנ"ל. גם התזה לשעצמה גם נכתבה על בסיס הנחות כלשהן. אני לא חושב שיש הבדל בין מודל חישוב לכל מרחב אחר, וזו התזה היחידה במדע שאני מכיר שמציגה מגבלה שכזו. לדוגמה: בעזרת לוגיקה מסדר ראשון לא ניתן לתאר או להוכיח דברים שניתן בעזרת לוגיקה מסדר שני. עצם ההנחה שהמח האנושי מוגבל לא אומרת שעוצמת התחשיבים מוגבלת גם היא.

 

[johnny d]

BTW

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

 

[ron369]

תן דוגמא אחת.

 

[johnny d]

בבקשה

http://en.wikipedia.org/wiki/Hypercomputer

 

[ron369]

תתכופף מהר! כי ירית לעצמך ברגל:

"Turing's writing made it clear that oracle machines were only mathematical abstractions, and could not, in fact, be physically realized " ​

על אילו משאבים טבעיים מדובר?

 

[johnny d]

ב1939 הוא האמין שזה בלתי ניתן למימו

היום הגישה שונה, וזה לא המודל היחידי

 

[ron369]

אבל יש הוכחה!

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

 

[johnny d]

אתה מצפה ממני להעביר לך

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

 

[vinney]

מה שג'וני מנסה להגיד לדעתי

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

 

[איתן333]

איפה ההוכחה מתבססת על מודל מסוים?

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

 

[vinney]

למשל

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

 

[ron369]

בהוכחה שלי מדובר על מכונת טיורינג?

היכן?

 

[vinney]

אני לא יודע איזו הוכחה אתה המצאת

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

 

[ron369]

ההוכחה שהמצאתי חמש-עשר הודעות

מעליך

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

 

[vinney]

אפשר להכליל הרבה דברים

זה לא יעשה אותם נכונים

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

 

[ron369]

זו הנקודה, כן, המצאתי

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

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

 

[vinney]

אדם יכול

ולא ממש המצאת

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

 

[ron369]

למען האמת,

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