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

עריסטו

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

שְלִילַת מְגַלֶּה הַלּוּלָאוֹת הַמּהֻלָּל _______________________ אֵין תָּכְנִית שֶתֵּדַע מָה אֲחֶרֶת עוֹשָׂה. זוֹ עֻבְדָּה מוּצָקָה, וְלֹא סְתָם מְצוּצָה: תּוּכָל עַד מָחָר אֶת הַמֹּח לִשְבֹּר- לֹא תּוּכַל לְנַבֵּא אִם תָּכְנִית תַּעֲצֹר. נַנִּיחַ שֶP הִיא שִיטָה שֶכָּזֹאת שֶלְּתוֹך כָּל תָּכְנִית מְצִיצָה, לְגַּלּוֹת שֶאֵין שוּם לוּלָאָה אֵינְסוֹפִית מִסְתַּחְרֶרֶת; וְאִם אֵין שָם כְּלוּם- אָז 'טוֹב!' הִיא אוֹמֶרֶת. מְזִינִים אֶת הַקּוֹד וְאֶת כָּל הַנְּתוּנִים, וְP אָז תַּחֲקֹר בַּפְּרָטִים הַקְּטַנִּים וּתְחַשְבֵּן אִם הַכֹּל מִסְתַּדֵּר כָּרָאוּי (בְּנִגּוּד לְמַצָּב לוּלָאִי לֹא רָצוּי). הָאֱמֶת הִיא שֶP כָּזוֹ לֹא תִּתָּכֵן, כִּי אִם תִּכָּתֵב P, וְלִי תִּנָּתֵן, אֶשְתַּמֵּש בָּהּ לִצֹּר כֶּשֶל לוֹגִי מֻצְלָח שֶיִּשְבֹּר הֶגְיוֹנְךָ וְחוּשֶיךָ יִמְעַךְ. הַתַּכְסִיס הוּא פָּשוּט וְיוֹצֵא מִן הַכְּלָל. אַגְדִּיר עוֹד תָּכְנִית, בְּשֵם Q, לְמָשָל, שֶתִּקַּח כָּל תָּכְנִית, וּלְP אָז תִּקְרָא, שֶתִּקְבַּע אִם יֵש בָּהּ לוּלָאָה מַמְאִירָה; אִם יֵש, אָז Q תַּדְפִּיס 'אוּף!' וְתִפְרֹש; אַךְ אִם אֵין, אָז Q תַּחֲזֹר לָהּ לָרֹאש, וְתַתְחִיל מֵחָדָש, תִּסְתּוֹבֵב בְּלִי לַחֲדֹל, עַד יִגְוַע הַיְּקוּם וְיִקְפָּא וְיִבֹּל. הַתָּכְנִית הַזּוֹ, Q, לֹא תֻּשְאַר יְתוֹמָה; מַמְזֵר שֶכְּמוֹתִי- אַפְעִילָהּ עַל עַצְמָהּ! אֵיךְ Q תִּתְנַהֵג בְּמַצָּב שֶכָּזֶה? כְּשֶתִּקְרָא אֶת עַצְמָהּ- מָה בְּדִיּוּק תַּעֲשֶׂה? אִם P תְּגַלֶּה לוּלָאָה- Q תֵּצֵא; אַךְ P אֲמוּרָה לְדַוֵּחַ עַל זֶה. כָּךְ שֶאִם Q תֵּצֵא- אָז P תֹּאמַר 'טוֹב!' וְQ תֵּאָלֵץ לְהַתְחִיל שוּב לָסֹב! מָה שֶP לֹא תַּגִּיד, Q יָשָר מְעַקֶּמֶת; Q גוֹרֶמֶת לְP לָצֵאת דֵּי מְטֻמְטֶמֶת. כִּי אִם P צוֹדֶקֶת- יוֹצֵא שֶשִּקְּרָה; וְאִם מְשַקֶּרֶת- אֱמֶת הִיא דִּבְּרָה! כָּזֶה פָּרָדוֹקְס אֱלֶגָנְטִי יָצָא, פָּשוּט בִּגְלַל P, הַהֲלִיך הַמֻּמְצָא. אִם תַּנִּיחַ שֶP אֲמִתִּי- הִסְתַּבַּכְתָּ; בְּפַח הַיּוֹקְשִים שֶטָּמַנְתִּי- נִלְכַּדְתָּ! אָז אֵיך נֵחָלֵץ מִצָּרָה כֹּה סְבוּכָה? לֹא צָרִיךְ שֶאַגִּיד; תְּנַחֵש לְבַדְּךָ. מַסְקָנָה הֶכְרֵחִית, שֶבְּזֶה הָעוֹלָם, יְצוּר אֲגָדִי כְּמוֹ P- לֹא קַיָּם. לֹא תַּצְלִיחַ לִבְנוֹת מִין מִתְקָן שֶכָּזֶה שֶיּוּכַל לְנַבֵּא מָה מַחְשֵב יַעֲשֶׂה. זֶה בִּלְתִּי אֶפְשָרִי. וְלָכֵן אֲנָשִים מוֹצְאִים בָּאגִים לְבַד; מַחְשֵבִים הֵם טִפְּשִים!!
 

johnny d

New member
משעשע, אבל אני עדיין לא קונה את זה.

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

johnny d

New member
תיקון

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

אמיתי ר

New member
אילו אקסיומות?

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

johnny d

New member
דוגמה :

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

ron369

New member
נו באמת

אם שור היה יודע שהאלגוריתם הקוונטי שלו בנוגע לפירוק מספרים לגורמיהם הראשוניים היה גורם לאנשים לחשוב שטיורינג טעה, אולי הוא היה שומר את הפלא לעצמו (וזה היה מאד חבל, כי מיד לאחר שהתברר שהנושא אפשרי, שמעתי שהתגלה אלגוריתם אחר בנושא, אולי אלגנטי יותר).
אתה צריך להבין, שלא משנה גם אם מדובר על המודל שלך, יש סתירה לוגית בנושא! אתה יכול לנסות להמציא מודלים, ואז להפעיל את הלוגיקה של טיורינג עליהם (כמו בשיר), ולראות מה קורה. למשל, נגדיר את המודל הבא: תכנית יכולה בכל שלב לבצע אינסוף חישובים. ונגיע לסתירה לוגית. נניח שקיימת P, שבהנתן תכנית Q, מחשבת אם Q עוצרת, ע"י השמה אינסופית וניסוי כל האפשרויות. נגדיר תכנית Z, שמקבלת תכנית Q, ומריצה את P על Z. אם P מחזירה "כן", Z לא תעצור. אם P מחזירה "לא", Z תעצור מייד. מריצים את Z על עצמה. אם Z עוצרת, אזי Z לא עוצרת, סתירה. אם Z לא עוצרת, אזי Z עוצרת, סתירה. והגענו לסתירה לוגית יפהפיה. מגניב, הא?
אגב, אם אתה רוצה, תראה בכך מעיל "הוכחה" שהמודל שלך לא קיים. ועוד אגב, אם הבנתי נכון את המודל שלך, הוא גם בעייתי במונחי קנטור, שטען בפשטות שלא קיימת פונקציה חד חד ערכית ועל בין הקבוצה [0,1] לבין Z (או N). היה עדיף אם היית בוחר פונקציה בין Q בתחום [0,1] לבין N, המוגדרת לכל n על ידי: ZZZ 1-(1/n).
 

johnny d

New member
שטויות

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

אמיתי ר

New member
למה שטויות? לא יפה...

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

johnny d

New member
הבסיס הלוגי לא חייב להיות נכון.

ראה את התגובה הברה שלי לרון
 

ron369

New member
וואלה

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

ron369

New member
(חשבתי שבסוף מחקתי את החלק בסוף../images/Emo4.gif)

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

johnny d

New member
כל מה שאמרתי זה

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

vinney

Well-known member
אז זה לא מכונה ../images/Emo13.gif

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

vinney

Well-known member
למה לא?

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

ron369

New member
../images/Emo6.gif

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