שיחה:הבונה העסוק

כמי שלמד קורס בחישוביות, וכן שני קורסים בלוגיקה, אני חייב להגיד שלא הבנתי את הערך. לא הבנתי בדיוק מה סופרות שתי הפונקציות האלה. Harel - שיחה 23:04, 5 יולי 2006 (IDT)

זו רק ההתחלה של הערך. אני מקווה להרחיב בהמשך. יאיר ח. 07:29, 6 יולי 2006 (IDT)

הרבה יותר טוב עכשיו. Harel - שיחה 11:38, 7 יולי 2006 (IDT)

בעיה לא פתורה או בעיה לא פתירה?

יש הבדל גדול בין שתי המילים הללו. למיטב הבנתי, הבעיה איננה פתירה. גדי אלכסנדרוביץ' 11:48, 7 יולי 2006 (IDT)

כמו שכתוב בערך הבעיה לא ניתנת לפתרון (רקורסיבי) באופן כללי. כלומר הפונקציות האלו לא ניתנות לחישוב באופן כללי, ולפי משפטי אי השלמות של גדל גם בהכרח קיים n שעבורו לא ניתן להוכיח אם מכונה מסויימת עם n מצבים עוצרת או לא ולכן לא ניתן למצוא את ערכי הפונקציות הנ"ל אצלו. אבל ערכים מסוימים כן ניתן למצוא, והצליחו לחשב את הפונקציות עבור הערכים 1, 2 ו-3. אם תרצה אפשר לנסח את הבעיה באופן פתיר כ"למצוא עבור אלו ערכים ניתן לחשב את הפונקציות האלו ולחשב אותן". הניסוח הזה מוודא בעצם שחוקרי מדעי המחשב תמיד ישארו עם עבודה :). יאיר ח. 17:16, 7 יולי 2006 (IDT)

למה לערב את גדל? חשבתי שמתבססים על בעיית העצירה. אולי כדאי לשנות את הניסוח ל"איננה ניתנת לפתרון כללי". גדי אלכסנדרוביץ' 17:23, 7 יולי 2006 (IDT)

באמת עדיף להתבסס על בעיית העצירה (אבל יש קשר לגדל שנמצא עמוק בתוך תורת הרקורסיה). אין בעיה, זה ניסוח טוב. מבחינה יחצ"נית, כדי למשוך קוראים, עדיף קודם לומר שזו בעיה פתוחה ורק אח"כ להסביר למה היא אף פעם לא תיסגר. טכנית היא מהווה מחלקה של כמה בעיות פתוחות פתירות, ועוד רבות שאינן פתירות יאיר ח. 17:40, 7 יולי 2006 (IDT)

לסטודנטים למדעי המחשב

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

זה ממש, אבל ממש, חסר חשיבות. מ"ט עם סרט חד צדדי שקולה למ"ט עם סרט דו צדדי ולכן כל אחד מוזמן להגדיר אותה איך שבא לו. גדי אלכסנדרוביץ' 07:51, 9 יולי 2006 (IDT)

בקשר להוכחה ישירה - תמיד טוב שיהיה עוד מידע מעניין בערך. גדי אלכסנדרוביץ' 07:52, 9 יולי 2006 (IDT)

תודה. יאיר ח.

תזת צ'רץ'

"Double זו המכונה שבהתקבל סרט עם n אחדות רצופים עליו תחזיר סרט עם 2n אחדות. קיימת מכונה כזו לפי תזת צ'רץ'."

כזכור, אף אחד לא הוכיח (או יוכיח) את תזת צ'רץ', וגם לא ברור לי למה צריך להסתמך עליה. קיימת מכונה כזו כי ממש קל לתת תיאור פורמלי שלה, וחסל. גדי אלכסנדרוביץ' 12:07, 9 יולי 2006 (IDT)

זה סתם חוסר יכולת התכנות שלי. אם יש לך כוח וזמן כדי לתאר את המכונה הזו (כמכונת מצבים ולא כאלגוריתם)- באמת יהיה עדיף לכתוב כך. יאיר ח. 12:46, 9 יולי 2006 (IDT)

אין שום סיבה לכתוב אותה בצורה מפורשת - זה סתם מעיק על הקורא. מספיק להגיד ש"קל לכתוב מכונה כזו במפורש", וגם על זה אפשר לוותר כי זה לא באמת מעניין אף אחד ומי שרוצה שיוכיחו לו את זה פורמלית, צריך לשלוח אותו לכתוב מכונה שמקבלת x ומחזירה x+1. בכל מקרה אין צורך לערב את התזה של צ'רץ' (שכאמור, אינה יכולה להוכיח כלום) בעניין. גדי אלכסנדרוביץ' 12:58, 9 יולי 2006 (IDT)

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

בתור מתמטיקאי קשה לי לדלג את כל הדילוגים האלו ולכן כתרפיה עצמית אני מוסיף שם "התזה של צ'רץ'", "התזה של צ'רץ'" בכל פעם, מתוך מחשבה שאם זה שגוי- אז גיליתי משהו עצום ואדיר ואם זה לא שגוי אז זה טיעון קביל ואין צורך לבנות מכונה בת 15 מצבים ולהתחיל לבדוק שהיא באמת פועלת. למי שעוסק בחישוביות התזה של צ'רץ' כנראה מאוד טבעית ומבוססת עמוק בתודעתו על בסיס של עשרות תרגילים טכניים ושחורים מהסוג של "בנה במפורש את המכונה שלוקחת X ומחזירה X+1", אבל למי שלא עוסק בתחום התזה מאוד מפתיעה. אגב- בלי קשר, צריך להוסיף את ההכללות למכונות שיכולות לכתוב m סימנים ולא רק אפס או אחד או שזה סתם העמסה טכנית של מידע? יאיר ח. 13:18, 9 יולי 2006 (IDT)

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

כמובן שגם ההכללה למכונות עם m סימנים מיותרת כאן. בערך על מכונת טיורינג צריך לציין את כל השקילויות הטריוויאליות הללו (ואם מישהו ממש נואש, להוכיח אותן בסוף הערך, אבל זה מיותר) וחסל. גדי אלכסנדרוביץ' 13:32, 9 יולי 2006 (IDT)

תודה. יאיר ח.

חישוב בעיית העצירה מתוך פונקצית ספירת האחדות

כדי לחשב את בעיית העצירה מתוך $\ \Sigma (n)$ מספיק לחשב את נחשב פונקציה שחוסמת את (S(n מתוך $\ \Sigma (n)$ ואז נחשב מתוכה את בעיית העצירה כמו שמתואר בחל הקודם.
מתוך מכונה בת n מצבים אפשר לבנות מכונת ספירת צעדים, כך שבכל צעד שהמכונה המקורית עושה המכונה החדשה תכתוב 1 ותזוז ימינה. נסמן את מספר המצבים של מכונת ספירת הצעדים ב-k_n, זוהי פונקציה רקורסיבית. מספר האחדות שהמכונה יכולה לכתוב לפני שהיא עוצרת חסום על ידי $\ \Sigma (k_{n})$, כמו כל מכונה אחרת עם k_n מצבים, אך במקרה הזה, מספר האחדות המקסימלי שמכונה כזו כותבת (ועוצרת) הוא בדיוק $\ S(n)$. כלומר $\Sigma (k_{n})\geq S(n)$-ובוודאי $\ \Sigma (k_{n})$ ניתנת לחישוב מתוך $\ \Sigma (n)$, ולכן בעיית העצירה ניתנת לחישוב מתוך $\ \Sigma (n)$.

יש מקום לזה בערך?

קודם כל, אני לא בטוח שאין שגיאות בהוכחה הנ"ל, אבל אם היא נקייה- יש מקום להוכחה הזאת בערך או שהיא טכנית מדי? יאיר ח. 20:04, 12 יולי 2006 (IDT)

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

ההוכחה אמורה להופיע (אם בכלל) בהמשך להוכחה על החישוב של בעיית העצירה מתוך S (החלק האחרון בערך). הוספתי בערך עצמו בחלק הזה את העובדה שמכל פונקציה שחוסמת את S ניתן לחשב את בעיית העצירה, ועל העובדה הזו ההוכחה מתבססת. בהוכחה מחשבים בסופו של דבר פונקציה כזו. הדגשתי את מה שאני לא בטוח לגביו (הרקורסיביות של k_n). יאיר ח. 21:29, 12 יולי 2006 (IDT)

אני מבין שאני צריך לקרוא את כל הערך לפני שאגיב... אעשה זאת בקרוב. גדי אלכסנדרוביץ' 22:00, 12 יולי 2006 (IDT)

בעיה בערך

התחלתי לערוך את הערך, אך נתקעתי בנקודה עדינה ובעייתית:

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

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

עד כמה שאני מסוגל לראות, תיקון של העניין הזה ידרוש שינויים רציניים בחלק מהערך, ולכן אני מעדיף להעלות את הנקודה בדף השיחה קודם. אולי אני מפספס משהו. גדי אלכסנדרוביץ' 22:19, 12 יולי 2006 (IDT)

תרגום מילולי מדי שלי?

"a Busy Beaver (from the colloquial expression for "industrious person") is a Turing machine that, when given an empty tape, does a lot of work, then halts"

סביר מאוד שיש לי טעויות בערך, פשוט כי אף פעם לא למדתי את הנושא כמו שצריך, ולכן אם אתה מוצא משהו שגוי- תמחק אותו ותכתוב מחדש. יאיר ח. 22:26, 12 יולי 2006 (IDT)

כאמור, זו נקודה עדינה שקל לפספס. הסרט של מכונת הטיורינג מכיל, באופן עקרוני, רק את הסימן "הריק". אם כבר המשתמש הואיל בטובו לשים קלט על הסרט, הוא יכיל אותיות מא"ב הקלט (שהוא בד"כ 0 ו-1), אבל 0 לא משמש בתור הסימן "הריק". אם אין התנגדות אני אתקן. גדי אלכסנדרוביץ' 22:31, 12 יולי 2006 (IDT)

אין התנגדות. יאיר ח.

אם מסמנים מקום ריק כ-0 אז מה השתנה בעצם?

משהו לא ברור לי

ואני מניח שזו אשמתי. בהוכחה הישירה שפונקצית ספירת הצעדים לא ניתנת לחישוב, מה פשר "נכתבים על הסרט (S(2k אחדות, מה שדורש לפחות צעד אחד"? איך ייתכן שכל האחדות הללו נכתבים בצעד אחד? לא הנחנו שהמכונה נתונה כאורקל, אלא רק שהיא קיימת. עד כמה שאני מבין את זה, כדי לכתוב (S(2k אחדות על סרט שקודם הכיל רק אפסים חייבים (S(2k צעדים לפחות. אין חוכמות. אחרי זה אפשר פשוט לבצע עוד צעד אחד וזהו, בלי להסתבך עם הכפלות ומחיקות (שמבלבלות ללא ספק את הקורא). איפה אני טועה? גדי אלכסנדרוביץ' 22:57, 12 יולי 2006 (IDT)

קודם כל- תודה על ההגהה.

דבר שני-אתה צודק לגמרי (חוץ מזה שפספסת את "לפחות" לפני ה"צעד אחד"). מבחינת ההוכחה מה שחשוב זה שמתבצע צעד אחד, זה שאחריו יש עוד צעדים רבים זה כבר לא משנה. אחרי חישוב S פשוט אפשר לספור את הצעדים שמתבצעים במפורש וכבר לא צריך לנחש את מספרם. באמת יש (S(2k צעדים (ואפילו תיאורטית הרבה יותר) אבל אין שום דרך לגלות כמה בדיוק וזה גם לא רלוונטי, מה שחשוב זה שמתבצע לפחות צעד אחד.יאיר ח. 23:06, 12 יולי 2006 (IDT)

שיניתי ל"מספר צעדים". יאיר ח.

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

העניין היה עשוי להיות בעייתי אם (S(2k היה מוחזר לא באונארית אלא בבינארית, אבל מכיוון שיש רק שתי אותיות באלף-בית ואחת משמשת בתור סימן למקום ריק, זה לא נראה סביר במיוחד. גדי אלכסנדרוביץ' 23:39, 12 יולי 2006 (IDT)

המכונות האלו הן שהופכות את ההוכחה לטריוויאלית. (לכן באנגלית הם קוראים להוכחות "הוכחות טריוואילות לאי-הרקורסיביות..." או משהו כזה). נראה לי שה-Double כן הכרחי אחרת לא מגיעים למספר המצבים הזה (2k) אלא למספר אחר, אבל אם אפשר לפשט את ההוכחה- אז תמיד עדיף. יאיר ח. 23:50, 12 יולי 2006 (IDT)

בקריאה נוספת, Double אכן נראה לי הכרחי, ו-Clean נראה לי כמו דרך אחרת להגיד "בואו נעשה עוד לפחות צעד אחד". מילא. אני אנסה לשכתב קצת את החלק כדי שיהיה ברור למה Double הכרחי. גדי אלכסנדרוביץ' 00:13, 13 יולי 2006 (IDT)

עוד תהייה

בערך מגדירים את S בתור פונקציה שמחשבת את מספר הצעדים המקסימלי על סרט ריק. לכן לא ברור לי למה בהוכחת השקילות לבעיית העצירה פתאום מחשבים אותה גם עבור מכונה שמקבלת קלט שהוא לא בהכרח ריק. גדי אלכסנדרוביץ' 14:41, 13 יולי 2006 (IDT)

לא מחשבים את S על קלט לא ריק. להיפך- יוצרים מכונה חדשה M' (עם יותר מצבים) שכותבת את הקלט על הסרט הריק, חוזרת להתחלה, ורק אז פועלת כמו M על הסרט (שעכשיו הוא כבר לא ריק). מכונה זו יכולה לבצע לכל היותר (S(n+2k צעדים לפני שהיא עוצרת, כמו שהוסבר בערך. יאיר ח. 16:25, 13 יולי 2006 (IDT)

אה, אופס. התבלבלתי. גדי אלכסנדרוביץ' 16:26, 13 יולי 2006 (IDT)

כתבת: "על ידי ידיעת אלגוריתם שמחשב את בעיית העצירה..." אבל אין אלגוריתם כזה(לפחות לא במובן של "אלגוריתם" שנמצא בשאר הערך). זה מידע חיצוני שניתן לנו באורח פלא ולא על ידי אלגוריתם. בנוסף יש שמגדירים את "בעיית העצירה" לא רק כבעיה (שאלה) אלא ממש כקבוצת הזוגות הסדורים (קלט, מכונה שעוצרת על הקלט) או משהו כזה, ולכן אפשר לדבר על בעיית העצירה ישירות כאורקל ואין צורך באלגוריתם שמחשב אותה. יאיר ח. 16:37, 13 יולי 2006 (IDT)

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

"n מצבים פנימיים"? יאיר ח.

השימוש במילה "פנימי" בא להדגיש שמדובר במצב שאינו קשור לסרט או למיקום הראש עליו (העזרים ה"חיצוניים"). התרגלתי כבר לכתוב כך, אבל אני לא חושב שמדובר בניסוח פורמלי או מקובל, ואפשר לשנות אם זה צורם לך. גדי אלכסנדרוביץ' 09:13, 14 יולי 2006 (IDT)

שים לב לשינויים בערך

המשכתי בהגהה בערך והוספתי את השקילות בין בעיית העצירה ופונקצית ספירת האחדות, אחרי ששכנעתי את עצמי שההוכחה נכונה. יאיר ח. 13:14, 14 יולי 2006 (IDT)

איך שאני מבין את זה, המסקנה בסוף ההוכחת השקילות בין S לבעיית העצירה לא גוררת שS גדלה יותר מהר מכל פונקציה רקורסיבית אלא רק שעבור כל פונקציה רקורסיבית R קיימים אינסוף מקומות בהם S גדולה יותר מ-R (אבל אולי קיימים עוד אינסוף מקומות בהם S קטנה יותר מ-R). אני לא הצלחתי להוכיח את התוצאה החזקה יותר- ש-S גדלה יותר מהר מכל פונקציה רקורסיבית $\equiv$ שלכל פונקציה רקורסיבית R הפונקציה S גדולה ממש מ-R החל ממקום מסוים. יאיר ח. 13:42, 14 יולי 2006 (IDT)

ייתכן שאני מתבלבל, אבל מה שנראה לי הוא כזה: אם R רקורסיבית אבל קיימים אינסוף מקומות שבהם היא גדולה מ-S, ואנחנו רוצים לפתור את בעיית העצירה עבור מכונה עם r מצבים פנימיים וקלט k, אז נבנה מכונה עם r+2k מצבים כמתואר, אבל בנוסף למצבים הללו נוסיף עוד מצבים (שלא משנים את פעולת המכונה) כדי שנגיע לערך הקרוב ביותר שבו R גדול מ-S, ואז "ניצחנו" (=פתרנו את בעיית העצירה). גדי אלכסנדרוביץ' 14:35, 14 יולי 2006 (IDT)

יפה, לא חשבתי על זה. לפני שתוסיף את זה לערך- איך תדע שהגעת למקום שבו R כבר גדולה יותר מ-S? יאיר ח. 14:42, 14 יולי 2006 (IDT)

שאלה מצויינת שאין לי עליה תשובה, ואולי מפילה את כל הטיעון. אני צריך לקרוא יותר בנושא כדי לראות איך (והאם) הם מתמודדים איתה. גדי אלכסנדרוביץ' 14:50, 14 יולי 2006 (IDT)

אם קיימת פונקציה רקורסיבית שעוברת את S אינסוף פעמים אז נוצרת משפחה מוזרה ביותר של פונקציות (לא רקורסיביות), ככה שאינטואטיבית אני תומך בטענה. אם זה מעודד, גם באנגלית הם מצדדים בך... יאיר ח. 16:36, 19 יולי 2006 (IDT)

אני די משוכנע שאני צודק (בין היתר בהתבסס על ויקי האנגלית), אבל זה לא אומר כלום לגבי שיטת ההוכחה שניסיתי להשתמש בה, שנראית לי כעת שגויה. לרוע המזל, בזכות המלחמה שנפלה עלינו אין לי ספריה לחפש בה או מרצים לשאול בעתיד הקרוב. גדי אלכסנדרוביץ' 16:40, 19 יולי 2006 (IDT)

הוכחה אלטרנטיבית:
קודם כל ברור שאם n<m אז פלט של מכונה בת n מצבים שפועלת על הסרט הריק הוא קטן ממש מ$\ \Sigma (m)$ ומ- $\ S(n)$. ולכן עבור מכונה M כלשהי צריך למצוא דרך יעילה מספיק לכתוב אחדות על הסרט ולחזור אחרונה כך שמספר המצבים שכתיבת האחדות+ מספר מצבי המכונה יהיה קטן מהקלט. במקרה הזה נקבל שהפלט של המכונה M על הקלט m יהיה קטן ממש מ- $\ \Sigma (m)$.

כדי לבנות k אחדות על הסרט מספיק לבנות k/2 אחדות, ולהשתמש במכונה Double. לשם כך צריך k/2+C מצבים (k/2 כדי לכתוב את האחדות המקוריות ו-C אלו המצבים של המכונה Double). תהי M מכונה בת n מצבים. אם k מספיק גדול מתקיים:

n + k/2 +C < k

ולכן באמצעות n+ k/2 +C ניתן לכתוב k אחדות על הסרט, לחזור אחורה להפעיל על הסרט את המכונה M. הפלט של התהליך בהכרח קטן ממש מ- $\ \Sigma (k)$ וגם מ- $\ S(k)$, מ.ש.ל.

תקין? קצת עיגלתי פינות כדי לא להיכנס ממש לעבודה השחורה של בניית המכונות עצמן... יאיר ח. 15:39, 21 יולי 2006 (IDT)

לא ממש הבנתי מה עשית בהוכחה. נסה לנסח אותה כך שיהיה יותר ברור מה היעדים שלך בכל שלב, ומה הסימנים שאתה משתמש בהם. גדי אלכסנדרוביץ' 16:08, 21 יולי 2006 (IDT)

ניסיון שני. (שכתבתי את ההוכחה) יאיר ח. 11:23, 23 יולי 2006 (IDT)

אני עדיין לא מבין מה אתה מנסה לעשות. אני אנסה לחדד: אנחנו רוצים להראות שלא קיימת פונקציה רקורסיבית R שגדולה מהפונקציה S באינסוף מקומות. עכשיו תסביר לי איך אתה מוכיח את זה. אם ההוכחה שלך מתכתבת עם שלי לא הבנתי איך, ובהוכחה שלך אני כלל לא רואה התייחסות ל-R. גדי אלכסנדרוביץ' 11:30, 23 יולי 2006 (IDT)

אני הולך מכיוון קצת אחר: אני לוקח פונקציה רקורסיבית כללית, קורא למכונה שלה M ומראה שהחל מקלט מסוים k ניתן ליצור מכונה בת פחות מ-k מצבים שפועלת על הסרט הריק כמו ש-M פועלת על k, ואז התוצאה, הפלט של הפונקציה הרקורסיבית, חייבת להיות פחות מ- S(k). יאיר ח. 12:10, 23 יולי 2006 (IDT)

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

בעיות הבונה העסוק מוגדרות רק עבור מספר סופי של סימנים שאפשר לסמן על הסרט (אחרת אין בעיה ליצור מכונה בת שני מצבים, שנבצע כמה פעולות שנרצה ותעצור- המצב הראשון יכתוב מספר גדול והשני יפחית ממנו בכל צעד 1). נראה לי שעבור מספר סימנים m אפשר בדומה להוכחה המקורית שכתבתי (עם הלוגריתם) לכתוב את המספר n על ידי $\ o(n^{\frac {m-1}{m}})$ (אני מקווה שלא התבלבלתי בין הO-ים), ואז לבצע את אותו מהלך ובסופו של דבר לתוצאה דומה. יאיר ח. 12:53, 23 יולי 2006 (IDT)

מה הקשר לבעיות פתוחות במתמטיקה?

אני מצטטת מוויקי האנגלית :

Almost any open problem in mathematics could be solved in a systematic way given the value of S(n) for a sufficiently large n.

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

בתודה מראש, קסניה שיינרמן 89.0.37.132 12:47, 22 באוגוסט 2008 (IDT)

העניין הוא, בתמצית, שכל הוכחה אפשר לכתוב באופן סופי במערכת פורמלית המבוססת על שפה מסדר ראשון]. אפשר לבנות מכונת טיורינג שתממש את האלגוריתם הבא: כתוב את כל ההוכחות הסופיות במערכת האקסיומות הנתונה, ובדוק האם התקבלה הוכחה למשפט המבוקש. חיפוש ההוכחה הזו יארך לכל היותר S(n) פעולות, עבור n מתאים התלוי רק בגודל המערכת האקסיומטית. לכן, מי שמוכן לחכות S(n) מיקרו-שניות (עבור n גדול מאד), יכול לברר לכל בעיה מתמטית האם יש לה הוכחה (ואם כן, למצוא אותה). עוזי ו. - שיחה 13:40, 22 באוגוסט 2008 (IDT)

אבל איך בודקים האם התקבלה הוכחה? או שזה קשור ל ATP ?

89.0.37.132 14:42, 22 באוגוסט 2008 (IDT)

ראי הקצרמר הוכחה (לוגיקה מתמטית). עוזי ו. - שיחה 17:07, 22 באוגוסט 2008 (IDT)

ועוד משהו

כתוב בספרו של ריי קורצווייל, כי הבונה העסוק הוא פונקציה אינטליגנטית, כלומר, פונקציה הדורשת אינטליגנציה הולכת וגדלה, כדי לחשב אותה עבור ארגומנטים הולכים וגדלים. גם את זה אני לא בדיוק מבינה. אשמח לקבל הסבר. בתודה מראש, קסניה שיינרמן 89.0.37.132 12:54, 22 באוגוסט 2008 (IDT)

אני לא יודע למה הוא מתכוון כאן במלה "אינטליגנציה" - ברור שהחישוב הולך ונעשה קשה יותר (כי צריך למצוא הוכחה, עבור כל המכונות בגודל n שאינן עוצרות, שזה אכן כך). עוזי ו. - שיחה 13:42, 22 באוגוסט 2008 (IDT)