שיחה:תורת החישוביות/משפט הרקורסיה

אי השלמות של גדל

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

קיימות מספר הוכחות. הוכחה אחת יפה משתמשת במשפט הרקורסיה, ואותה חשבתי להציג כאן. ראה, למשל, [1]. ‏gran‏ - שיחה 19:59, 31 בינואר 2012 (IST)

בסדר, ההוכחה גם די מוכרת. עדיין אינני חושב שזה תת-נושא של משפט הרקורסיה (גם אם אפשר להוכיח בעזרתו, באופן דומה לכך שזה לא תת-נושא של סיבוכיות קולמוגורוב). מציע להקים דף אחר על חישוביות תיאוריות מתמטיות ולוגיות - אפשר להסביר שם מה כן רקורסיבי, לדוגמה. לגבי גדל, אפשר להוכיח שם את המשפט במספר דרכים, כולל דרך משפט הרקורסיה. Atavory - שיחה 20:22, 31 בינואר 2012 (IST)

אם לחדד, נראה לי שיש מקום לדף על חישוביות לתיאוריות מתמטיות ולוגיות. יש לפחות שתי אפשרויות: או שיופיע לפני משפט הרקורסיה, או אחרי סיבוכיות קולמוגורוב. במקרה הראשון, אפשר להשאיר את ההוכחות בשני הפרקים הרלוונטיים. במקרה השניה, אפשר לרכז את ההוכחות בדף החדש. הדבר היחידי שנראה לי שכדאי להמנע ממנו זה שלושה מקומות שונים שמגדירים את אותם הדברים פחות או יותר. מה דעתך? Atavory - שיחה 20:35, 31 בינואר 2012 (IST)

זה לא אמור להיות תת־נושא, אלא הדגמה של דברים שניתן לעשות בעזרת המשפט. בדיוק כמו שכריעות HP אינו תת־נושא. אני לא יודע בדיוק מה כוונתך בפרק "חישוביות לתיאוריות מתמטיות ולוגיות" אבל זה נשמע נושא מתקדם שיכול להיות מעניין. משפט גדל, כשלעצמו, אינו נושא בחישוביות, אבל אפשר להראות הוכחות שלו בשיטות שונות (משפט הרקורסיה / קולמוגורוב / וואטאבר). ‏gran‏ - שיחה 04:48, 1 בפברואר 2012 (IST)

תוכנת quine

משתמש:שואל/common.js, מי שיעתיק את הקוד לדף שלו ([[משתמש:שם משתמש/common.js]]) יראה הודעה עם הקוד הזה בכל פעם שהוא טוען דף.--שואל (שיחה) 19:36, 12 במרץ 2019 (IST)