80661 סמינריון בדרגות טיורינג

סמסטר הסתיו תשס"ה 2004

 

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

 

מורה הקורס: פרופ' עזריאל לוי

משרדו: בנין המתמטיקה, חדר 317.  שעות קבלה: יום שני 11.10, 3:30-2:30.

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

 

 

הודעות

 

 

נושא הסמינריון

 

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

כשנתונות הפונקציות G,F נניח שבמחשב שלנו מותקן באורח פלא מחשבון לפונקציה  F(שאיננה פונקציה חשיבה) , האם המחשב יוכל לחשב את הפונקציה G?

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

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

    

 

 

חומר הסמינריון

 

מבוא (pdf , ps).

שיטת ההמשכה הסופית (pdf , ps).

פעולת הקפיצה (pdf , ps).

מיקום קבוצות תוכניות בהירארכית סיגמה n פיי n (pdf , ps).

דרגות נל"ח לא ניתנות להשוואה (pdf , ps)

דרגת נל"ח נמוכה (pdf , ps).

 

חומר נלווה:

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

 

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

Degrees of Unsolvability של Joseph R. Shoenfiled בתוספת ההערות וההשלמות הבאות:

פרקים 3-1 (pdf , ps).

פרקים 5-4 (pdf , ps).

פרק 12 (pdf , ps).

פרק 13: פרק 14 (pdf , ps).

פרק 15: דרגת קבוצה מקסימלית (pdf , ps), דרגות וקבוצות מקסימליות (pdf , ps),

            קיום קבוצה מקסימלית (pdf , ps).

.

 

ביבליוגרפיה

Odifreddi, P.G., Classical Recursion Theory, 1992.

Shoenfield, Joseph R., Degrees of Unsolvability, 1971.

Rogers, Hartley Jr., Theory of Recursive Functions and Effective Computability, 1967.

Shoenfield, Joseph R., Recursion Theory, 1993.

Lerman, Manuel, Degrees of Unsolvability, 1983.

Soare, Robert, Recursively Enumerable Sets and Degrees, 1987.

Bell, J.L. & Machover, M., A course in Mathematical Logic, 1977 ,Ch. 6.

Shoenfield, Joseph R., Mathematical Logic, 1967, Ch. 7.

 

איך רואים את הטקסטים המתמטיים?

 

הטקסטים המתמטיים בעברית כתובים גם כקובצי Acrobat עם סיומת pdf וגם כקובצי Postscript עם סיומת ps.

התוכנה היותר נפוצה והיותר קלה להתקנה היא תוכנת Acrobat לקריאה ולהדפסה של קובצי pdf שאפשר להורידה כאן.

התוכנה החלופית היא צמד התוכנות Ghostscript ו-Ghostview, ובעזרת  Ghostview אפשר לקרוא ולהדפיס גם קובצי ps וגם קובצי pdf.

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

,כדאי להוריד ולהתקין את צמד התוכנות Ghostscript ו-Ghostview אם בתוכנת Acrobat הנך רואה את הטקסט העברי בצורה לא ברורה מספיק.

את תוכנת Ghostscript אפשר להוריד כאן, ואת תוכנת Ghostview אפשר להוריד כאן.

 

 

אם הנך נתקל בבעייה כלשהי בקשר עם אתר זה, אם אם יש לך עצה כלשהי, אנא כתוב לי.

 

כתב: עזריאל לוי

עידכון אחרון: 4.12.2004.