Fork me on GitHub

אי שלמות ואי כריעות בשפות פורמליות
ד"ר אסף חסון, אוניברסיטת בן-גוריון בנגב

יובל אדם
Young man, in mathematics you don't understand things.
You just get used to them.
- John von Neumann

תוכן עניינים

1 פרולוג
2 הגדרות
3 תחשיב היחסים
4 קומפקטיות ומסננים
5 מסננים והלמה של צורן
6 מכפלות
7 משפט Los והוכחת קומפקטיות
8 עקביות
9 מערכות היסק ויכיחות
10 מערכות היסק - המשך
11 מכונות טיורינג
12 מכונות טיורינג - המשך
13 פונקציות חשיבות
14 פונקציות חשיבות - המשך
15 הצפנות
16 חשיבות
17 מניה רקורסיבית
18 פונקציות יציגות
19 פונקציות יציגות
20 הוכחת משפטי אי השלמות של גדל
21 תורת רקורסיה
22 תורת רקורסיה - המשך
23 תורת רקורסיה - המשך
24 תורת רקורסיה - המשך

1 פרולוג

2 הגדרות

הערות:
  1. בכל שפה לתחשיב פסוקים נניח שיש סימן יחס דו מקומי מיוחס ≈ אשר תמיד מתפרש כיחס השוויון
  2. כמוסכמה: אם אומרים ש L שפה לתחשיב הפסוקים בד"כ לא נציין במפורש את סימן השוויון למרות שבמובלת נניח שהוא שם
  3. בקורס הזה לא ניתקל בכך, אבל ניתן לעבוד בתחשיב ללא שוויון. יש משפטים שיותר קל להוכיח בתחשיב שכזה. בכל מקרה, תמיד אפשר לעבור בין תחשיב עם שוויון לתחשיב ללא שוויון וחזרה.

3 תחשיב היחסים

דברים שצריך בשביל העבודה:
הכנה לשיעור הבא:

4 קומפקטיות ומסננים

משפט #. משפט הקומפקטיות: תהי Γ קבוצת פסוקים סגורה תחת ∧ (כלומר אם ϕ 1 , ϕ 2 ∈ Γ אז גם ϕ 1 ∧ ϕ 2 ∈ Γ ) אזי Γ ספיקה אם ורק אם כל ϕ ∈ Γ ספיק.
טענה #. תהי Γ קבוצת פסוקים אזי קיימת קבוצת פסוקים Γ ⊆ Γ ′ כך ש-
  1. Γ ′ סגורה תחת ∧
  2. Γ ≡ Γ ′ כלומר כל מודל של Γ הוא מודל של Γ ′ ולהיפך
הוכחה: תהי Γ ′ קבוצת הפסוקים המתקבלת מ Γ באופן הבא: לכל 1 ≤ k ∈ N ולכל ϕ 1 ,..., ϕ k ∈ Γ , ב Γ ′ יהיה הפסוק > ⋀ i=1 k ϕ i . נשים לב ש Γ ′ סגורה תחת ∧ . מדוע? יהיו ψ 1 , ψ 2 ∈ Γ ′ לפי ההגדרה של Γ ′ יש מספרים טבעיים 1 ≤ k 1 , k 2 ופסוקים ϕ 1 1 ,..., ϕ k 1 1 ו- ϕ 1 2 ,..., ϕ k 2 2 כך ש- > ψ 1 = ⋀ i=1 k 1 ϕ i 1 ו- > ψ 2 = ⋀ i=1 k 2 ϕ i 2 אז > ψ 1 ∧ ψ 2 = ⋀ i=1 k 1 + k 2 Θ i כאשר Θ i = { ϕ i 1 i ≤ k 1 ϕ i- k 1 2 i> k 1 מכיוון ש- Θ i ∈ Γ לכל i גמרנו. Γ ′ היא המועמדת שלנו לספק את הטענה ונותר להראות ש Γ ≡ Γ ′ . מספיק להראות שאם M | = Γ אז M | = Γ ′ . יהי ψ ∈ Γ ′ ונניח כמו קודם ψ = > ⋀ i=1 k ϕ i עבור ϕ i ∈ Γ כלשהו.
אזי: Va l M ( ψ ) = Va l M ( ⋀ ϕ i )= t ∧ ( Va l M ( ϕ 1 ),...Va l M ( ϕ k ) )=TRUE מתקיים אמ"ם לכל 1 ≤ i ≤ k Va l M ( ϕ i )=TRUE . כיוון ש M | = Γ אז M | = ϕ i לכל i ולכן M | = ψ .
הגדרה #. קבוצת פסוקים Γ נקראת ספיקה מקומית אם כל תת קבוצה סופית שלה היא ספיקה.
משפט #. (משפט הקומפקטיות - נוסח שקול) קבוצת פסוקים Γ היא ספיקה מקומית אם ורק אם היא ספיקה.
הוכחה: נוכיח שמשפט הקומפקטיות גורר את הנוסח הזה. תהי Γ קבוצת פסוקים ספיקה מקומית. תהי Γ ′ כמובטח בטענה, כלומר Γ ′ ≡ Γ ו Γ ′ סגורה תחת ∧ . מספיק להראות לפי משפט הקומפקטיות שכל פסוק ב Γ ′ הוא ספיק. יהי ψ ∈ Γ ′ אז > ψ = ⋀ i=1 k ϕ i לאיזה ϕ 1 ,..., ϕ k ∈ Γ . לפי ההנחה Γ ספיקה מקומית. לכן { ϕ 1 ,..., ϕ k } קבוצת פסוקים ספיקה. לכן יש מודל M | = ϕ i לכל 1 ≤ i ≤ k לפי מה שהראנו בהוכחת הטענה M | = ψ . לכן Γ ′ סגורה תחת חיתוך וכל ψ ∈ Γ ′ ספיק. לפי משפט הקומפקטיות עבור Γ ′ יש M | = Γ ′ אבל Γ ≡ Γ ′ לכן M | = Γ ′ .
נוכיח את הכיוון השני (שהנוסח הזה גורר את משפט הקומפקטיות). נניח Γ מקיימת את ההנחות כלומר Γ ′ סגורה תחת ∧ וכל פסוק בה ספיק. יספיק להראות בעזרת הנוסח השקול ש Γ ספיקה מקומית. נוכיח באינדוקציה על k שכל קבוצת פסוקים מגודל k ב- Γ היא ספיקה. עבור k=1 - נתון. נניח ש { ϕ 1 ,..., ϕ k } ⊆ Γ והראנו עבור כל קבוצת פסוקים מגודל k-1 שהיא ספיקה. כיוון ש Γ סגורה תחת חיתוך ϕ 1 ∧ ϕ 2 ∈ Γ . Δ ={ ϕ 1 ∧ ϕ 2 , ϕ 3 ,..., ϕ k } היא קבוצה בגודל k-1 ולכן לפי הנחת האינדוקציה היא ספיקה. אם M | = Δ אז M | = ϕ i לכל i ≥ 3 וכן M | = ϕ 1 ∧ ϕ 2 . אבל M | = ϕ 1 ∧ ϕ 2 ⇐ ⇒ M | = ϕ 1 ∧ M | = ϕ 2 ולכן M | = { ϕ 1 ,..., ϕ k } כנדרש. כלומר Γ ספיקה מקומית וע"ס הנוסח השקול - ספיקה.
הגדרה #. תהי I קבוצה (בד"כ אינסופית אבל לא בהכרח). מסנן (filter) על I זו קבוצה F ⊆ P (I) (כלומר אוסף של תת קבוצות של I ) כך שמתקיים:
  1. ∅ ∖ ∈ F
  2. אם J ∈ F ו- J ⊆ J ′ אז J ′ ∈ F
  3. אם J, J ′ ∈ F אז J ∩ J ′ ∈ F
אם בנוסף לכל J ⊆ I אם J ∖ ∈ F אז I \ J ∈ F - אז F נקרא על מסנן.
דוגמאות:
טענה #. תהי I קבוצה לא ריקה. F מסנן על I אזי קיים על מסנן F ⊆ F ′ . במילים אחרות כל מסנן על I ניתן להרחבה לעל מסנן. (הוכחה בשיעור הבא).

5 מסננים והלמה של צורן

הגדרה #. תהי I קבוצה (לא ריקה) אז מסנן F על I זה אוסף של תת קבוצות של I כך ש:
  1. ∅ ∖ ∈ F
  2. אם U 1 , U 2 ∈ F אז U 1 ∧ U 2 ∈ F
  3. אם U ∈ F ו- U ⊆ V אז V ∈ F
F הוא על-מסנן אם לכל V ⊆ I אם V ∖ ∈ F אז I \ V ∈ F .
למה #. הלמה של צורן - תהי ( I, ≤ ) קבוצה סדורה חלקית. V ⊆ I תקרא שרשרת אם לכל v 1 , v 2 ∈ V או v 1 ≤ v 2 או v 2 ≤ v 1 . אז נניח שלכל שרשרת V ⊆ I יש חסם מלעיל, כלומר קיים w ∈ I כך ש- w ≥ V (כלומר w ≥ v לכל v ∈ V ). אזי ב ( I, ≤ ) יש איבר מירבי, כלומר קיים u ∈ I כך שלכל u ∖ =v ∈ I מתקיים u ∖ ≤ v .
טענה #. תהי I קבוצה לא ריקה ו- F מסנן על I . אזי קיים על-מסנן F ⊆ U . במילים אחרות, כל מסנן F על I ניתן להרחבה לעל-מסנן.
הוכחה: תהי H קבוצת כל המסננים על I . לאינטואיציה: F ∈ P ( P (I) ) אז H ⊆ P ( P (I) או H ∈ P ( P ( P (I) ) ) . על H אפשר להגדיר סדר חלקי ע"י הכלה. כלומר, ל- F 1 , F 2 ∈ H נאמר ש F 1 ≤ F 2 אם לכל V ∈ F 1 מתקיים גם V ∈ F 2 . אפשר לכתוב גם F 1 ⊆ F 2 . נרצה להשתמש בלמה של צורן, לכן עלינו להראות שאם V ⊆ H שרשרת אז ל V יש חסם מלעיל ב H . נגדיר F V = > ⋃ V ={U ⊆ I:U ∈ F,forsomeF ∈ V} . נראה ש F V הוא מסנן.
  1. ברור כי ∅ ∖ ∈ F V
  2. נניח ש U 1 , U 2 ∈ F V . קיימים F 1 , F 2 ∈ V כך ש U 1 ∈ F 1 וגם U 2 ∈ F 2 . כיוון ש- V שרשרת, ב.ה.כ F 1 ⊆ F 2 . לכן U 1 ∈ F 2 לכן גם U 1 ∩ U 2 ∈ F 2 ולכן U 1 ∩ U 2 ∈ F V .
  3. אם U ∈ F V ו- U ⊆ W אז לפי הגדרה קיים איזה F ∈ V כך ש- U ∈ F . לכן גם W ∈ F ולכן W ∈ F V .
הראנו שלכל שרשרת ב H יש חסם מלעיל, כי ברור F V ∈ H ו- F ⊆ F V לכל F ∈ V כלומר F V חסם מלעיל ל- V . לפי הלמה של צורן, ב- H יש איבר מירבי, נסמנו U . נראה ש U על מסנן. נניח בשלילה שהוא לא. כיוון ש- U ∈ H הוא מסנן ולכן הנחת השלילה מבטיחה שיש קבוצה U ⊆ I כך ש- U ∖ ∈ U ו- I \ U ∖ ∈ U . נשים לב כי במקרה זה U U = U ∪ {W ⊆ I:U ∩ V ⊆ W,forsomeV ∈ U } הוא מסנן וזאת תהיה סתירה למירביות של U כי U ∖ ⊆ U U . מדוע U U הוא מסנן?
  1. נוכיח ש ∅ ∈ U U . אם ∅ ∈ U U הרי שהיא מהצורה U ∩ V לאיזה V ∈ U . אבל אז V ⊆ I \ U ואז I \ U ∈ U בסתירה.
  2. U U סגורה כלפי מעלה מעצם הגדרתה.
  3. נראה כי אם U 1 , U 2 ∈ U U אז גם U 1 ∩ U 2 ∈ U U . ב.ה.כ U 1 ∖ ∈ U . לכן U ∩ V ⊆ U לאיזה V ∈ U . לכן U ∩ V ∩ U 2 ⊆ U 2 ∩ U 1 עבור V הזו. אם U 2 ∈ U אז V ∩ U 2 ∈ U ולכן U ∩ ( V ∩ U 2 ) ∈ U U וכך גם U 1 ∩ U 2 . אחרת U ∩ V 2 ⊆ U 2 לאיזה V 2 ∈ U . ואז U ∩ ( V ∩ V 2 ) ⊆ U 1 ∩ U 2 וגם U ∩ ( V ∩ V 2 ) ∈ U U . קיבלנו U U ∈ H ו- U ∖ ∈ U U סתירה. לכן U על מסנן.
(הרחבה) אם F מסנן על I נגדיר H F ⊆ H אוסף המסננים המכילים את F . באופן טריויאלי לכל שרשרת ב- H F יש חסם מלעיל ב- H F (כי כל שרשרת כזו היא שרשרת של איברים שגדולים מ- F ולכן אם יש לה חסם ב H הרי שהוא חסם ב H F . לכן H F מקיימת את הלמה של צורן, לכן יש איבר מירבי גם ב H וראינו שאלו על מסננים.
מסקנה #. לכל קבוצה אינסופית I יש על מסנן F על I כך שאם |I \ U|< ℵ 0 אז U ∈ F .
הגדרה #. מכפלות: תהי Γ קבוצה לא ריקה כלשהי ו- { M γ } γ ∈ Γ אוסף של קבוצות לא ריקות. אז המכפלה > ∏ γ ∈ Γ M γ זה אוסף כל הפונקציות f: Γ → > ⋃ γ ∈ Γ M γ המקיימות f( γ ) ∈ M γ . הערה: אם Γ ={1,...,n} ו- M i = M j לכל i,j אז > ∏ i=1 n M = M n .
משפט #. אקסיומת הבחירה: אם Γ לא ריקה ו- M γ ∖ = ∅ לכל γ ∈ Γ אז > ∏ γ ∈ Γ M γ ∖ = ∅ .

6 מכפלות

הגדרה #. מכפלות: תהי Γ קבוצה לא ריקה כלשהי ו- { M γ } γ ∈ Γ אוסף של קבוצות לא ריקות. אז המכפלה > ∏ γ ∈ Γ M γ זה אוסף כל הפונקציות f: Γ → > ⋃ γ ∈ Γ M γ המקיימות f( γ ) ∈ M γ . הערה: אם Γ ={1,...,n} ו- M i = M j לכל i,j אז > ∏ i=1 n M = M n .
דוגמה: אם M γ = M לכל M אז > ∏ γ ∈ Γ M = M Γ זה פשוט אוסף כל הפונקציות מ Γ ל M .
 
הגדרה #. אם Γ לא ריקה ו- M γ ∖ = ∅ לכל γ ∈ Γ . תהי M = ∏ M γ . ל x ‾ , y ‾ ∈ M נגדיר x ∼ F y עבור על מסנן F על Γ אם { γ ∈ Γ : x ‾ ( γ )= y ‾ ( γ )} ∈ F .
טענה #. בסימונים של ההגדרה האחרונה ∼ F הוא יחס שקילות.
הוכחה:  
  1. { γ ∈ Γ : x ‾ ( γ )= y ‾ ( γ )}= Γ ∈ F
    1. { γ ∈ Γ : x ‾ ( γ )= y ‾ ( γ )}={ γ ∈ Γ : y ‾ ( γ )= x ‾ ( γ )}
    2. נניח ש x ∼ F y ו- y ∼ F z אז U = { γ ∈ Γ : x ‾ ( γ )= y ‾ ( γ )} ∈ F וגם V = { γ ∈ Γ : y ‾ ( γ )= z ‾ ( γ )} ∈ F לכן U ∩ V ∈ F אבל U ∩ V ⊆ { γ ∈ Γ : x ‾ ( γ )= z ‾ ( γ )} ∈ F .
הגדרה #. תהי Γ קבוצה לא ריקה ולכל γ ∈ Γ יהי M γ מבנה לשפה L . יהי F על מסנן (לא ראשי) על Γ אז העל מכפלה של { M γ } γ ∈ Γ ביחס ל F שתסומן M= ( > ∏ γ ∈ Γ M γ )/F היא המבנה המוגדר כלהלן:
  1. העולם של העל מכפלה הוא ( > ∏ γ ∈ Γ M γ )/ ∼ F כלומר אוסף מחלקות השקילות של היחס ∼ F על המכפלה ( > ∏ γ ∈ Γ M γ )
  2. לכל קבוע אישי c ∈ L נפרש [ ( c M γ ) γ ∈ Γ ] מחלקת השקילות של הסדרה ( c M γ ) γ ∈ Γ ביחס ל ∼ F .
  3. לכל סימן יחס n-מקומי R ∈ L . נאמר ש [ a 1 ‾ ,..., a n ‾ ] ∈ R M אם { γ ∈ Γ :( a 1 ‾ ( γ ),..., a n ‾ ( γ ) ) ∈ R M γ .
  4. לכל סימן פונקציה n-מקומי F נאמר ש F M [ ( a 1 ‾ ,..., a n ) ‾ ]=[b] אם { γ ∈ Γ : F M γ ( a 1 ‾ ( γ ),..., a n ‾ ( γ ) )=b( γ )} ∈ F . הערה: הנ"ל מוגדר היטב. כלומר אם [b]=[d] אז { γ ∈ Γ : F M γ ( a 1 ‾ ( γ ),..., a n ‾ ( γ ) )=b( γ )} ⏟ ∈ F ∩ { γ ∈ Γ :d( γ )=b( γ )} ⏟ ∈ F ⏟ ∈ F ⊆ { γ ∈ Γ : F M γ ( a 1 ‾ ,..., a n ‾ ( γ ) )=d( γ )} ⏟ ∈ F כי [b]=[d] כלומר b ∼ F d וזאת בדיוק ההגדרה.
משפט #. יהיו M =( > ∏ γ ∈ Γ M γ )/F ו- ϕ ( x 1 ,..., x n ) נוסחה ו- s השמה ל M . אזי מתקיים Va l M ( ϕ ,s )=TRUE אם ורק אם לכל השמות ( s γ ) γ ∈ Γ (עם s γ השמה ל M γ ) כך ש [ ( s γ ) γ ∈ Γ ] ∼ F [s] מתקיים ש { γ ∈ Γ :Va l M ( ϕ , s γ )=TRUE} ∈ F .
הוכחה: באינדוקציה על יצירת הנוסחאות. נתחיל משמות עצם:
  1. אם ϕ נוסחה אטומית R( t 1 ( x 1 ,..., x n ),..., t m ( x 1 ,..., x n ) ) אז אם ורק אם Va l M ( R( t 1 ,..., t n ),s ) = TRUE ⇐ ⇒ ( Va l M ( t 1 ,s ),...Va l M ( t m ,s ) ) ∈ R M ⇐ ⇒ { γ ∈ Γ :( Va l M ( t 1 ,s )( γ ),...,Va l M ( t n ,s )( γ ) ) ∈ R M γ } ∈ F אם ורק אם לפי מה שהראנו עבור שמות עצם [ Va l M ( t i ,s ) ]=[ (Va l M ( t i , s γ )( γ ) ) γ ∈ Γ ] לכל 1 ≤ i ≤ m . לכן, { γ ∈ Γ :( Va l M ( t 1 , s γ ),...,Va l M ( t m , s γ ) ) ∈ R M γ } ∈ F ⇐ ⇒ { γ ∈ Γ :( Va l M γ ( t 1 , s γ ),...,Va l M γ ( t m , s γ ) ) ∈ R M γ } ∈ F וזה מה שהיינו צריכים .

7 משפט Los והוכחת קומפקטיות

משפט #. משפט Los תהי L שפה לתחשיב הפסוקים, Γ קבוצה לא ריקה, לכל γ ∈ Γ מבנה M γ לשפה L . יהי F על מסנן על Γ ו- s השמה עבור M =( > ∏ γ M γ /F ) ו- ϕ (x) נוסחה ב L . אזי Va l M ( ϕ , s ‾ )=TRUE אם ורק אם לכל השמה s ל- > ∏ γ M γ המקיימת s ‾ (x)=[ s(x) ] מתקיים: { γ ∈ Γ :Va l M γ ( M γ ,s( γ ) )=TRUE} ∈ F (כאשר s( γ )(x) זה הקואורדינטה ה γ של s(x) ).
תזכורת: כיצד מגדירין ("לכבוד פסח" - א. חסון, חג שמח) מבנה לשפה L על > ( ∏ γ ∈ Γ M γ /F) ?
תרגיל:
  1. להוכיח כי זה מוגדר היטב, כלומר F M היא אכן פונקציה. ז"א עבור a 1 ‾ ,..., a n ‾ ∈ M קיים b יחיד כך ש F M ( a 1 , ‾ ..., a n ‾ )=b .
  2. אם [ a 1 ]= a 1 ‾ ,...,[ a n ]= a n ‾ אז F M ( a 1 ‾ ,..., a n ‾ )=[ F M ( a 1 ( γ ),..., a n ( γ ) ) γ ∈ Γ ]
הוכחה: ראשית נראה: אם t שם עצם ב L , s ‾ ,s השמות כבניסוח המשפט אז Va l M ( t, s ‾ )=[ (Va l M γ ( t,s( γ ) ) ) γ ∈ Γ ] באינדוקציה על יציאת t .
הוכחנו עבור שמות עצם. כעת נוכיח את המשפט באינדוקציה על יצירת הנוסחה.
מסקנה #. נניח ש Γ לא ריקה ו M γ מבנים לשפה L לכל γ ∈ Γ ו- F על מסנן על Γ , אזי לכל פסוק ψ ב L מתקיים ( > ∏ γ ∈ Γ M γ )/F | = ψ אם ורק אם { γ ∈ Γ : M γ | = ψ } ∈ F .
מסקנה #. משפט הקומפקטיות: תהי Γ קבוצה פסוקים בשפה L . נניח שלכל ψ 1 , ψ 2 ∈ Γ גם ψ 1 ∧ ψ 2 ∈ Γ ולכל ψ ∈ Γ קיים מודל M ψ | = ψ אזי Γ ספיקה כלומר קיים M | = Γ .
הוכחה: לכל ψ ∈ Γ נבחר מבנה M ψ | = ψ . תהי U ⊆ P ( Γ ) הקבוצה המקיימת קיים ψ ∈ Γ כך ש: V ∈ U ⇐ ⇒ { γ ∈ Γ : M γ | = ψ } ⊆ V .
טענה #. U מסנן על Γ .
הוכחה: לכל ψ ∈ Γ מהנחתנו M ψ | = ψ לכן { γ ∈ Γ : M γ | = ψ } ∖ = ∅ . לכן U ∖ = ∅ . ברור ש U סגורה כלפי מעלה. נניח ש v 1 , v 2 ∈ U אזי קיימים ψ 1 , ψ 2 ∈ Γ כך ש- { γ ∈ Γ : M γ | = ψ i } ⊆ V i וזה גורר..... V 1 ∩ V 2 ∈ U .
יהי F על מסנן שמרחיב את U . לפי המסקנה מתקיים ( > ∏ γ ∈ Γ M γ ) /F | = ψ אם ורק אם { γ ∈ Γ : M γ | = ψ } ∈ F . אבל מהגדרת U לכל ψ ∈ Γ הקבוצה { γ ∈ Γ : M γ | = ψ } ∈ U ולכן ל- F . מש"ל.

8 עקביות

משפט #. תהי ( P, ≤ ) קס"ח, אזי קיים יחס R על P (דו-מקומי) כך ש-
  1. R יחס סדר קווי
    1. לכל a,b ∈ P אם a ≤ b אז R( a,b ) .
    במילים אחרות, קיים סדר קווי R על P שמרחיב את ≤ .
משפט #. הערה: המשפט עבור קבוצה סופית P איננו קשה. ההוכחה באינדוקציה על |P| . עבור |P|=1 אין מה להוכיח. נניח שהוכחנו עבור כל P עם |P|=n ונוכיח עבור n+1 : תהי ( P, ≤ ) קס"ח עם n+1 איברים. כיוון ש P סופית יש לה איבר מינימלי a . תהי Q=P \ {a} . אז ( Q, ≤ ) קס"ח עם n איברים ולפי הנחת האינדוקציה יש R סדר קווי על Q שמרחיב את ≤ על Q . עתה לא קשה לבדוק שאם נגדיר R( a,b ) לכל b ∈ Q נקבל את המבוקש.
הוכחה: (מקרה כללי) תהי L שפה לתחשיב היחסים שבה:
  1. לכל p ∈ P יש קבוע אישי c p
  2. יחס דו מקומי R
בלבד. נגדיר קבוצת פסוקים T P ב L באופן הבא:
  1. c p ∖ = c q לכל p ∖ =q ∈ P
  2. R יחס סדר קווי
  3. לכל p,q ∈ P אם p ≤ q אזי יהיה פסוק R( c p , c q ) .
טענה #. T P ספיקה (מקומית).
הוכחה: ממשפט הקומפקטיות יספיק להוכיח ש T P ספיקה מקומית. תהי T 0 ⊆ T P סופית. בה"כ האקסיומה (2) " R יחס סדרי קווי" שייכת ל T 0 . בנוסף נשים לב שב T 0 מופיעים רק מספר סופי של קבועים, נאמר: c P 1 ,..., c p n . נביט בקבוצה P 0 ={ p 1 ,..., p n } ⊆ P . אז ( P 0 , ≤ ) קס"ח סופית. לכן לפי ההערה יש יחס R P 0 שהוא סדר קווי על P 0 המרחיב את ≤ על P 0 . ברור שאם נפרש את R ב P 0 ע"י R P 0 כנ"ל ו- c p i ע"י p i אז נקבל מודל של T 0 .
יהי M | = T P , בפרט R M סדר קווי על M . יהי N ≤ M המבנה שעולמו הוא הקבועים של M (כלומר a ∈ N ⇐ ⇒ a= c p M לאיזה p ∈ P ). נגדיר יחס סדר חלקי ≤ N על N ע"י p ≤ q ⇐ ⇒ c p N ≤ c q N לכל p,q ∈ P . אז ( P, ≤ )= ∼ ( N, ≤ N ) פשוט ע"י p mapstochar → c p N . לכן בה"כ ( P, ≤ )=( N, ≤ N ) . עתה R M | N (צמצום) סדר קווי על N . (לפי M | = (2) מתקיים כי R M סדר קווי וצמצום של כזה הוא נשאר קווי). כיוון ש- M | = (3) אז אם p ≤ q אזי p( c p , c q ) היא אקסיומה ב(3) ולכן M | = R( c p , c q ) ולכן N | = R( c p , c q ) .
משפט #. תהי L={G} עבור יחס דו מקומי G . T G התורה שאומרת כי העולם הוא גרף. אזי אין פסוק ψ ב L כך ש M | = ψ אם ורק אם M גרף קשיר.
הוכחה: נניח בשלילה שיש פסוק ψ כזה. נוסיף לשפה קבועים אישיים חדשים c 1 , c 2 . יהי ϕ n הפסור שאומר שאין מסילה באורך קטן מ n בין c 1 ל c 2 : ¬ ( ∃ x 1 ,..., x n )[ G( c 1 , x 1 ) ∧ ⋀ i=1 n-1 ( G( x i , x i+1 ) ∨ x i = x i+1 ) ∧ G( c 2 , x n ) ] נשים לב ש Γ ={ c 1 , c 2 } ∪ ψ ∪ { ϕ n } n=1 ∞ עיקבית מקומית. אם Γ 0 קבוצה סופית של פסוקים מן הקבוצה הנ"ל יש n מירבי כך ש ϕ n ∈ Γ 0 . ברור שאם נמצא M | = ϕ n ∧ ψ ∧ ( c 1 ∖ = c 2 ) אז M | = Γ 0 . אבל ברור שלכל n יש גרך המקיים את ϕ n ∧ ψ ∧ ( c 1 ∖ = c 2 ) (פחות מ n קודקודים, בפרט אין מסילה מ c 1 ל c 2 ). ולכן Γ ספיקה סופית. לפי קומפקטיות Γ עקבית. אבל זה לא ייתכן: אם M | = Γ אז M | = ψ ולכן בין c 1 ל c 2 יש מסילה ובהכרח אורכה סופי, נאמר n . מצד שני M | = ϕ n ולכן אין מסילה באורך n בין c 1 ל c 2 וזוהי סתירה להנחת השלילה.
הערה:
  1. באופן דומה אפשר להוכיח כי אין פסוק ψ בשפה L={ ≤ } כך ש M | = ψ אם ורק אם { ≤ } סדר טוב (כלומר ≤ סדר שווי בלי סדרה אינסופית יורדת).
  2. אותה הוכחה בדיוק תעבוד אם ננסה למצוא קבוצת פסוקים Γ כך ש M | = Γ אם ורק אם M גרף קשיר/ M סדור היטב (סדר טוב).
תזכורת:
אם Γ קבוצת פסוקים אז Γ | = ψ אם לכל מבנה M : אם M | = Γ אז M | = ψ .
מסקנה #. אם Γ | = ψ אז קיימת קבוצת פסוקים Γ 0 ⊆ Γ סופית כך ש Γ 0 | = ψ .
הוכחה: נביט בקבוצה Γ ∪ { ¬ ψ } . מהנחתנו קבוצה זו איננה ספיקה. מקומפקטיות יש Γ 1 ⊆ Γ ∪ { ¬ ψ } סופית כך ש Γ 1 איננה ספיקה. ברור ש ¬ ψ ∈ Γ 1 כי אחרת Γ 1 ⊆ Γ ו Γ עקבית. (אם Γ איננה עקבית מקומפקטיות יש Γ 0 ⊆ Γ שאינה ספיקה ו Γ 0 | = ϕ לכל פסוק ϕ ). לכן Γ ⊇ Γ 0 = Γ 1 \ { ¬ ψ } סופית ומקיימת Γ 0 | = ψ (כי אחרת יש מודל M | = Γ 0 ו- M ∖ | = ψ כלומר M | = ¬ ψ כלומר M | = Γ 1 בסתירה לבחירת Γ 1 ). במילים אחרות ליחס | = יש טבע סופי.
שאלה מרכזית: בהינתן שפה L וקבוצת פסוקים Γ ב L , כיצד אפשר לדעת/לבדוק ביחס לפסוק ψ כלשהו האם Γ | = ψ ? בתור התחלה נשים לב שאם ψ ∈ Γ אז בוודאי Γ | = ψ . ולכן רצוי שנוכל לענות על השאלה האם ψ ∈ Γ ? נניח שהגדרנו מתי קבוצת פסוקים Γ היא חשיבה, כלומר ניתן לענות על השאלה מתי פסוק ψ שייך ל Γ . נניח ש Γ קבוצת פסוקים חשיבה ונניח ש ψ 1 , ψ 2 ∈ Γ אז Γ | = ψ 1 ∧ ψ 2 . נניח ש ψ 1 ∈ Γ ו Γ | = ψ 1 → ψ 2 אז Γ | = ψ 2 . באופן כללי יותר אם הראנו למשל ψ 1 ו- ψ 1 → ψ 2 נגררים לוגית ע"י Γ אז ניתן להראות Γ | = ψ 2 .

9 מערכות היסק ויכיחות

בעיה מרכזית: נתונה קבוצת פסוקים Γ ורוצים לדעת עבור פסוק ψ האם Γ | = ψ .
מקרה פרטי: Γ = ∅ , כלומר רוצים לדעת האם פסוק ψ אמיתי לוגית או לא. המקרה הפרטי מנביע את המקרה הכללי. מדוע? בהינתן קבוצת פסוקים Γ ו ψ כלשהו, אם Γ | = ψ אז יש Γ 0 ⊆ Γ סופית כך ש Γ 0 | = ψ (משפט הקומפקטיות) ולכן ( > ⋀ ϕ ∈ Γ 0 ϕ ) → ψ אמיתי לוגית ואת זה אנחנו יודעים לבדוק.
שאלה: מתי פסוק הוא אמיתי לוגית?
  1. אנחנו יודעים שכל טאוטולוגיה היא אמיתית לוגית.
  2. אם ϕ אמיתי לוגית אז ∀ x ϕ אמיתי לוגית. אפשר לרשום גם: ϕ → ∀ x ϕ אמיתי לוגית.
  3. אם ∀ x ϕ (x) אמיתי לוגית אז ϕ (t) אמיתי לוגית לכל שם עצם t . אפשר לרשום גם: ∀ x ϕ (x) → ϕ (t) אמיתי לוגית.
  4. אם ϕ → ψ אמיתי לוגית ו ϕ אמיתי לוגית אז ψ אמיתי לוגית. (בכל מערכות ההיסק שנעבוד איתן זה יהיה כלל ההיסק היחיד. זה נקרא כלל הניתוק או Modus Poneus)
סימון: בהינתן שפה L מסדר ראשון נסמן Def( L ) אוסף הנוסחאות בשפה L .
הגדרה #. מערכת היסק (לשפה L ) זה זוג סדור langle A , I rangle כאשר:
  1. A ⊆ Def( L ) (אולי ריקה) שנקראת קבוצת האקסיומות הלוגיות
  2. > I ⊆ > ⋃ i=1 ∞ F i כאשר F n זה אוסף הפונקציות f:De f n ( L ) → Def( L ) ו- I נקראת אוסף כללי ההיסק.
הערה: תמיד נדרוש כי:
  1. אם ϕ ∈ A אז ϕ אמיתי לוגית. במקרה זה נאמר כי האקסיומות הלוגיות תקפות.
  2. אם f ∈ I ו- { ϕ 1 ,..., ϕ n } ∈ dom(f) אז { ϕ 1 ,..., ϕ n } | = f( ϕ 1 ,..., ϕ n ) . במקרה זה נאמר כי כללי ההיסק נאותים.
סימון: אם נרצה לומר ש ψ מתקבל מ ψ 1 ,..., ψ n על ידי אחד מכללי ההיסק נרשום ψ 1 ,..., ψ n ψ ולא צריך יהיה להסביר באיזה כלל היסק מדובר.
הגדרה #. בהינתן מערכת היסק langle A , I rangle וקבוצת נוסחאות Γ נאמר שנוסחה ψ יכיחה (כלומר, ניתנת להוכחה) מ Γ ,ונסמן Γ ⊢ ψ , אם קיימת סדרת נוסחאות ϕ 1 ,..., ϕ k לאיזה k ∈ N כך ש:
  1. ψ = ϕ k
  2. לכל 1 ≤ i ≤ k או:
    1. ϕ i אקסיומה לוגית. או:
    2. ϕ i ∈ Γ . או:
    3. ϕ i מתקבל מנוסחאות קודמות בסדרה ע"י אחד מכללי ההיסק. במקרה שלנו יש j 1 , j 2 <i כך ש ϕ i מתקבל מ- ϕ j 1 ו- ϕ j 2 ע"י כלל הניתוק.
    הסדרה ϕ 1 ,..., ϕ k המקיימת את התנאים הנ"ל נקראת הוכחה של ψ מ- Γ .
שאלה: האם קיימת מערכת היסק חשיבה (כלומר שבה אפשר להכריע מתי נוסחה היא אקסיומה לוגית, ומתי נוסחה מתקבלת מנוסחאות קודמות ע"י אחד מכללי ההיסק) כך שכל נוסחה אמיתית לוגית יכיחה (מ- ∅ ).
מעכשיו כל מערכת היסק שנדון בה תכיל את כלל הניתוק ככלל יחיד ואת כל הטאוטולוגיות כאקסיומות לוגיות (אולי גם אקסיומות לוגיות נוספות).
טענה #. תהי T תורה (קבוצת פסוקים ספיקה) כלשהי ו ψ נוסחה כך ש- T ⊢ ψ אזי T ∪ { ψ } ספיקה.
הוכחה: יהי M | = T נראה באינדוקציה על אורך ההוכחה של ψ מ- T ש- M | = ψ . אם ל- ψ הוכחה באורך 1 אז או ש- ψ אקסיומה לוגית ולכן אמיתי לוגית ולכן מסופק ב- M , או ש- ψ ∈ T ובוודאי ש- M | = ψ (כי M | = T ). נניח ש- ϕ 1 ,..., ϕ k הוכחה של ψ מ- T ואפשר להניח ב.ה.כ ש- ψ = ϕ k מתקבל מאיזה ϕ j 1 , ϕ j 2 עם j 1 , j 2 <k ע"י כלל הניתוק. לפי הנחת האינדוקציה M | = ϕ j 1 וגם M | = ϕ j 2 . מכיוון שכלל הניתוק הוא נאות, בפרט { ϕ j 1 , ϕ j 2 } | = ψ ולכן M | = ψ .
משפט #. משפט ההיסק: תהי Γ קבוצת נוסחאות ו- ψ נוסחה כלשהי, אז Γ ∪ { ψ } ⊢ φ אם ורק אם Γ ⊢ ( ψ → φ ) ( φ נוסחה).
(ההוכחה היא באינדוקציה על אורך ההוכחה, ונראה זאת עוד מעט).
הגדרה #. קבוצת נוסחאות Γ תקרא עקבית אם היא לא מוכיחה סתירה. (סתירה היא המקבילה של טאוטולוגיה - כלומר הצבה של פסוקים מתחשיב היחסים בסתירה של תחשיב הפסוקים).
הערות #. אם Γ אינה עקבית אז Γ ⊢ ψ לכל נוסחה ψ .
הוכחה: מהנחתנו Γ ⊢ σ לאיזו סתירה σ . אז Γ → ψ היא טאוטולוגיה ( σ מתקבלת ע"י הצבה של פסוקים מתחשיב היחסים בפסוק Σ ( P 1 ,..., P n ) של תחשיב הפסוקים ו- Σ ( P 1 ,..., P n ) → P היא טאוטולוגיה של תחשיב הפסוקים). כיוון ש Γ ⊢ σ מכלל הניתוק Γ ⊢ ψ .
מסקנה #. (ממשפט ההיסק) לכל תורה T ולכל נוסחה ϕ או ש- T ∪ ϕ עקבית או ש- T ∪ ¬ ϕ עקבית.
הוכחה: נניח ש- T ∪ ϕ ו- T ∪ ¬ ϕ שתיהן אינן עקביות. לפי ההערה יש סתירה σ כך ש- T ∪ ϕ ⊢ σ ו- T ∪ ¬ σ ⊢ σ . לפי משפט ההיסק T ⊢ ϕ → σ ו- T ⊢ ¬ ϕ → σ . אבל: ( ϕ → σ ) → ( ( ¬ ϕ → σ ) → σ ) זו טאוטולוגיה. שימוש כפול בכלל הניתוק יתן לנו הוכחה של σ מ- T . בסתירה להנחה ש- T ספיקה ולטענה הקודמת.
מסקנה #. לכל תורה T יש קבוצת פסוקים T ⊆ T ′ כך שלכל פסוק ψ או T ′ ⊢ ψ או T ′ ⊢ ¬ ψ .
הגדרה #. תורה T המקיימת לכל פסוק ψ או T ⊢ ψ או T ⊢ ¬ ψ נקראת שלמה.
הוכחה: (של המסקנה) תהי T אוסף כל קבוצות הפסוקים המכילות את T ביחס לסדר ההכלה. קל לבדוק שאם { T i } שרשרת עולה של תורות ב- T אז ⋃ T i ∈ T . למה? קומפקטיות (צריך לנמק). לכן לפי הלמה של צורן יש T ⊆ T ′ ∈ T מירבית. לפי המסקנה הקודמת T ′ עונה על הדרישות.

10 מערכות היסק - המשך

הגדרה #. קבוצת פסוקים עקבית T היא שלמה אם לכל פסוק ψ או ש- T ⊢ ψ או ש- T ⊢ ¬ ψ .
ראינו שאם T קבוצת פסוקים עקבית ומירבית כזו ביחס להכלה אז T שלמה.
טענה #. לכל קבוצת פסוקים עקבית T יש קבוצת פסוקים שלמה T ⊆ T ′ .
הוכחה: הלמה של צורן. כדי להשתמש בלמה של צורן יספיק להראות שאם { T i } שרשרת (ביחס להכלה) של קבוצות פסוקים עקביות אז גם T ˜ = ⋃ T i עיקבית. מדוע? אם T ˜ ⊢ σ לאיזו סתירה σ אז יש סדרה ϕ 1 ,..., ϕ k ∈ T ˜ שהיא הוכחה של σ מ- T ˜ . כל ϕ i הוא או אקסיומה לוגית או שייך לאיזה T j i או נובע מאיברים קודמים בסדרה ע"י כלל הניתוק. קיים j מירבי כך שלכל i כנ"ל או ϕ i אקסיומה לוגית או ϕ i ∈ T j או ϕ i מתקבל מכלל הניתוק. ז"א ש ϕ 1 ,..., ϕ k הוכחה של σ מתוך T j . אבל T j עקבית - סתירה.
משפט #. קיימת מערכת היסק (שבה כלל הניתוק הוא כלל ההיסק היחיד) וכך שמערכת ההיסק "חשיבה" ומתקיים ש T עקבית אם ורק אם T ספיקה.
מסקנה #. [משפט השלמות] נקבע מערכת היסק כנ"ל. תהי T קבוצת פסוקים עקבית, ψ פסוק כלשהו אזי T ⊢ ψ אם ורק אם T | = ψ .
הוכחה: אם T ⊢ ψ הראנו ש T | = ψ (שיעור שעבר). בכיוון השני, אם T | = ψ אבל T ∖ ⊢ ψ אז T ∪ ¬ ψ עקבית. לפי המשפט יש M | = T ∪ ¬ ψ בסתירה להנחה.
הערות #. המשפט הנ"ל שקול לטענה: קיימת מערכת היסק "חשיבה" כך שלכל ϕ אמיתי לוגית מתקיים ∅ ⊢ ϕ .
הוכחה: נניח את המשפט ונוכיח את הטענה. ∅ | = ϕ מתקיים כי ϕ אמיתי לוגית ומן המסקנה ∅ ⊢ ϕ . בכיוון השני, נניח את הטענה ונוכיח את המשפט. תהי T תורה עקבית. עלינו להראות (בעזרת הטענה) של T יש מודל. נניח שלא. ז"א מקומפקטיות יש תת קבוצה סופית T 0 ⊆ T שאין לה מודל. יהי > ψ = ⋀ ϕ ∈ T 0 ϕ . אז ψ שיקרי לוגית. אז ¬ ψ אמיתי לוגית. אז T ⊢ ¬ ψ . אבל T ⊢ ψ אז T איננה עקבית.
הערות #. ממשפט השלמות נובע ש T שלמה אם ורק אם T | = ϕ או T | = ¬ ϕ לכל פסוק ϕ .
דוגמאות לתורות שלמות:
  1. יהי M מבנה כלשהו לשפה L . התורה של M היא Th( M )={ ψ : M | = ψ } . מהגדרת האמת, אם M ∖ | = ϕ אז M | = ¬ ϕ . כלומר ϕ ∖ ∈ Th( M ) ואז ¬ ϕ ∈ Th( M ) .
משפט #. (לוונהיים-סקולם היורד): יהי M מבנה אינסופי לשפה (בת מניה) L . תהי A ⊆ M (בעולם של M ) אזי קיים A ⊆ M ′ ≺ M וכך ש- | M ′ |=|A|+| L | .
מסקנה #. נניח ש T תורה בשפה בת מניה ול T יש מודל יחיד עד כדי איזומורפיזם בעוצמה ℵ 0 . אזי T שלמה (סוג של קריטריון Vaught).
הוכחה: נניח שלא. אזי יש פסוק ϕ כך ש T 1 =T ∪ ϕ ו- T 2 =T ∪ ¬ ϕ עקביות. אזי קיימים M 1 | = T 1 ו- M 2 | = T 2 . מהמשפט אנחנו יודעים (נשתמש ב ∅ =A ⊆ M i ) שיש M i ′ ≺ M i כך ש ℵ 0 =| M i ′ | עבור i=1,2 . אבל M i | = T ולכן M i ′ | = T . לכן M 2 ′ = ∼ M 1 ′ (זאת ההנחה). לפי משפט האיזומורפיזם M 2 ′ | = ϕ ⇐ ⇒ M 1 ′ | = ϕ אבל M 1 | = ϕ → M 1 ′ | = ϕ וגם M 2 | = ¬ ϕ → M 2 ′ | = ¬ ϕ - סתירה.
מסקנה #.  
  1. תהי T ≈ התורה בשפה הריקה (ז"א שוויון בלבד) שאומרת שהעולם אינסופי. זו תורה שלמה.
  2. תהי L ={ ≤ } ו- DLO היא התורה של סדר קווי צפוף ללא קצוות. אז DLO תורה שלמה.
  3. הגרף המקרי (שנתנו אקסיומטיזציה שלו בתרגיל 1 שאלה 2) הוא קטגורי ב ℵ 0 (כלומר כל מודל אחר של התורה בעוצמה ℵ 0 איזומורפי לו) לפי תרגיל 2 שאלה 5.

11 מכונות טיורינג

תזכורת:
C - מחלקת הפונקציות החשיבות:
הגדרה #. יהיו S א"ב סופי עם תו מיוחד B , ו- Q קבוצה סופית (זרה ל S ) שנקרא לה "קבוצת המצבים הפנימיים" עם מצב התחלתי q 0 . פקודה זו רביעייה langle r,q,x, q ′ rangle כאשר r ∈ S , q, q ′ ∈ Q , x ∈ {L,R} ∪ S . מכונת טיורינג זו רביעיה M=langle I,S, q 0 ,Q rangle כאשר I קבוצה סופית, חסרת סתירות של פקודות. (הערה: I חסרת סתירות אם rqx q ′ ,rqy q ′ ′ ∈ I אז y=x ו- q ′ = q ′ ′ .)
נחשוב בצורה גרפית על מ"ט כעל סרט אינסופי המחולק לאינסוף תאים. בכל תו של הסרט כתובה אחת מאותיות הא"ב כאשר על B נחשוב כעל תו המייצג תא ריק. למכונה יש ראש קורא שנמצא תמיד על אחד התאים. הראש הקורא יכול לזהות מהו התו הכתוב בתא בו הוא נמצא. לפי המצב הפנימי של המכונה ולפי הנקרא, יכול הראש הקורא לזוז ימינה ושמאלה תא אחד או לכתוב תו אחר בא"ב באותו התא, ולעבור למצב פנימי חדש. על פקודה נחשב כאומרת: אם הראש הקורא רואה תו r והמצב הפנימי הוא q אז אם x ∈ {L,R} זוז ימינה או שמאלה תו אחד ועבור למצב פנימי q ′ . אם x ∈ S כתוב בתא הנוכחי x ועבור למצב פנימי q ′ . לומר ש I היא סדרת פקודות חסרת סתירה זה פשוט לומר ש I היא פונקציה חלקית: S × Q → Q × ( S ∪ {L,R} ) .
הגדרה #.  
  1. מצב m של מכונת טיורינג T שו שלשה ( n,q,h ) כאשר:
    1. n ∈ Z מציין את מיקום הראש הקורא ביחס למיקום ההתחלתי n=0 .
    2. q ∈ Q המצב הפנימי של המכונה
    3. h: Z → S פונקציה המתארת מה כתוב בכל תא של הסרט.
  2. בהינתן מ"ט T ומצב m של המכונה נגדיר את המצב העוקב ל m לפי המכונה T להיות m (T) =( n * , q * , h * ) כאשר:
    1. m=( n,q,h ) ויש פקודה rqx q ′ ∈ I כך ש r=h(n) ו- q הוא אותו מצב פנימי
    2. אם (א) מתקיים אז n * ={ n x ∈ S n+1 x=R n-1 x=L
    3. אם (א) מתקיים אז q * = q ′
    4. אם (א) מתקיים אז h * (m)={ h(m) m ∖ =n y m=n כאשר y=h(n) אם x ∈ {L,R} ו- y=x אם x ∈ S .
  3. ריצה של מ"ט T זו סדרה של מצבים m 0 , m 1 , m 2 ,... המקיימת:
    1. m 0 =( 0, q 0 , h 0 ) לאיזו h 0
    2. לכל i>0 מתקיים m i = m i-1 (T) .
  4. ריצה של מ"ט T נקראת סופית (או מסתיימת) אם היא מהצורה m 0 , m 1 ,..., m n לאיזה n ∈ N ו- M n (T) אינו מוגדר.
 
הגדרה #. בהינתן מ"ט T ומספר טבעי n נגדיר פונקציה (חלקית) f T n = N n → N באופן הבא: n=0 , q= q 0 , והסרט נראה כך: ...BB 1...1 ⏟ 1+ x 1 B 1...1 ⏟ 1+ x 2 B...B 1...1 ⏟ 1+ x n BB... מתקיים m= f T n ( x 1 ,..., x n ) אם ריצה של T עם המצב ההתחלתי הנ"ח מסתיימת (אחרת לא מוגדר) ו- m היא מספר האחדות על הסרט בתום הריצה.
 
הגדרה #. פונקציה f: N n → N נקראת חשיבה ע"י מ"ט אם קיימת מ"ט T כך ש f T n =f , כלומר f מוגדרת בדיוק באותו התחום בו f T n מוגדרת ובכל מקום שהן מוגדרות f T n ( x 1 ,..., x n )=f( x 1 ,..., x n ) .

12 מכונות טיורינג - המשך

הגדרה #. תהי f: N k → N פונקציה f נקראת חשיבה (ע"י מכונת טיורינג) אם קיימת מכונה T כך שלכל ( n 1 ,..., n k ) ∈ N k הריצה של T על סרט מהצורה ...BB 1...1 ⏟ 1+ n 1 B 1...1 ⏟ 1+ n 2 B...B 1...1 ⏟ 1+ n k BB... מסתיימת אם ורק אם f( n 1 ,..., n k ) מוגדר ובמקרה זה מספר האחדות על הסרט בתום הריצה הוא f( n 1 ,..., n k ) .
תזכורת: סימנו, בהינתן מ"ט T את הפונקציה f T n להיות הפונקציה שעבור קלט כנ"ל מחזירה את מספר האחדות בריצה סופית של המכונה (על הקלט).
טענה #. לכל מכונת טיורינג T יש מכונת טיורינג T * כך ש:
  1. f T n = f T * n לכל n
  2. בא"ב של T * יש שני תווים מיוחדים S,E כך שבכל ריצה מסתיימת של T * (על קלט תקני) הסרט לאחר הריצה נראה כך: ...BBS111...1EBB...
  3. המכונה מעולם לא עברה במהלך הריצה את התא המסומן ב S שמאלה
  4. פרט ל S,E ל- T * יש רק את התווים {1,B} .
הוכחה:  
  1.  
  2. לכל מצב פנימי q ∈ Q(T) יהיה במכונה T * מצב פנימי q * . כל פקודה rqx q ′ ∈ I(T) נחליף בפקודה r q * x( q ′ ) * . נוסיף ל T * את הפקודות הבאות:
    נותר להבטיח שכל האחדות צמודות ושהמכונה יודעת מה לעשות במקרה שהיא נתקלת ב S או ב E בשלב הריצה. נטפל קודם בחלק השני, לכל מצב פנימי q * נוסיף פקודות:
    נטפל כעט בלהבטיח שכל האחדות צמודות. נניח שכל ריצה מסתיימת של T מסתיימת במצב פנימי q ˆ (שאינו מופיע במהלך הריצה של T ). נוסיף פקודות:
  3. הטיפול דומה לזה של הסעיף הקודם, פרט לטיפול במה קורה כאשר פוגשים S . כל פעם שהמכונה פוגשת S היא תיכנס ל"תת מכונה" שמזיזה את כל הסרט שעד E ימינה בתו אחד, כותבת B במקום הראשון שמימין ל- S וחוזרת לריצה של T . הדבר היחיד שצריך להשתכנע: יש מכונה Sh שבהינתן קלט מן הצורה ...BBS...EBBB... מעתיקה את כל הקלט בהזזה של תא אחד ימינה. נוסיף לא"ב שלנו תו מיוחד B * , המכונה תרוץ באופן הבא:
    1. תסרוק עד שתגיע ל E
    2. לכל תו α בא"ב המקורי (כלומר שאינו B * ) יהיה מצב פנימי q α . סדרת הפקודות:
      מעתיקה את התו α תו אחד מימין למקומו המקורי. צריך טיפול נפרד בתווים S,E אבל אין בעיה.
  4. אם בא"ב שלנו יש n תווים נבנה מכונה T * שבה התו ה- i בא"ב של T ייוצג ע"י n -יה של תאים 11...1 ⏟ i BB...B ⏟ n-i . קל לבדוק שכל פקודה מהצורה "זוז ימינה" או "זוז שמאלה" ב T ניתן לתרגם בקלות לפקודה "זוז n תווים ימינה/שמאלה" ב T * . פקודה מהצורה "כתוב את התו ה i בא"ב בתא הנוכחי" תתרגם לסדרה של n פקודות כתיבה "כתוב במקום ה n -יה שאתה נמצא בתחילתה את ה n -יה 11...1 ⏟ i BB...B ⏟ n-i . כנ"ל לגבי הקריאה. לא קשה לבדוק: אם נייצג את התו 1 בא"ב של T ע"י 1 BB...B ⏟ n-1 אז f T * n = f T n לכל n .
מעכשיו נניח שכל מכונת טיורינג שנעבוד איתה מקיימת את התנאים 2,3,4 . לפי 1 אם מה שמעניין אותנו זה מחלקת הפונקציות הניתנות לחישוב ע"י מכונת טיורינג הרי שהנחה זו אינה משנה את המחלקה. בנוסף נניח שלכל מכונת טיורינג יש מצב מסיים יחיד שאינו מופיע במהלך הריצה. עוד אפשר להניח שבסיום הריצה הראש הקורא נמצא תו אחד מימין ל- S .
טענה #. נניח ש- f: N → N ו- g: N → N חשיבות טיורינג אז גם f ○ g חשיבה טיורינג.
הוכחה: תהינה T f , T g מכונות כך ש f T f ′ =f וגם g T g ′ =g . לכל מצב פנימי של f במכונה החדשה יהיה מצב פנימי q * . אז המכונה של ההרכבה תהיה:
  1. רשימת הפקודות של T g .
  2. מוחקים את S , וכותבים במקומו 1 , מוחקים את E , חוזר להתחלה ועובר למצב פנימי q 0 *
  3. רשימת הפקודות של T f עם השינוי שכל פקודה מהצורה *q ★ q 1 משתנה לפקודה מהצורה * q * ★ q 1 * .
טענה #. משפחת הפונקציות החשיבות טיורינג סגורה תחת אופרטור "מיזער": μ x 1 ( g( x 1 ,..., x n ) ) = { a (*) undefined else כאשר * הינו תנאי שנגדיר בשיעור הבא....

13 פונקציות חשיבות

ראינו שהפונקציות הבאות חשיבות טיורינג:
הגדרה #. f: N k → N m חשיבה טיורינג אם f( x 1 ,..., x k ) = ( f 1 ( x 1 ,..., x k ),..., f m ( x 1 ,..., x k ) ) וכל אחת מהפונקציות f i עבור 1 ≤ i ≤ m חשיבה טיורינג.
ברור שזה לא מספיק כדי לתאר את כל הפונקציות החשיבות טיורינג משום שכל הפונקציות המתקבלות מן הרשימה הנ"ל על ידי מספר סופי של הרכבות הן פונקציות שלמות. כלומר מוגדרות על כל N k עבור k מתאים. לא קשה להשתכנע שיש פונקציות חשיבות טיורינג שאינן שלמות, למשל: 1 q 0 L q 2 ,B q 2 L q 1 ,* q 1 L q 1 (מכונה שלא עוצרת על חלק מהקלטים - על 0 במקרה הזה).
טענה #. תהי g( x 1 ,..., x n ): N k → N פונקציה כלשהי. נגדיר h( x 2 ,..., x k ) = μ x 1 ( g( x 1 ,..., x k ) )={ t g( t, x 2 ,..., x k )=0 ∧ ( ∀ z<t )( g( z, x 2 ,..., x k )>0 ) undefined else אזי אם g חשיבה טיורינג גם h חשיבה טיורינג. μ נקרא אופרטור ה"מיזער".
הוכחה: (רעיון) תהי T מכונת טיורינג המחשבת את g (כלומר f T k =g ). "מטה רעיון" - נריץ את T על הקלט 0, x 2 ,..., x k . אם המכונה לא עוצרת זה אומר ש g לא מוגדרת ב ( 0, x 2 ,..., x k ) ולכן גם h( x 2 ,..., x k ) לא מוגדרת כנדרש. אם הריצה מסתיימת נבדוק האם היא הסתיימה ב 0 . אם כן, נחזיר 0 ואז h( 0, x 2 ,..., x k )=0 כנדרש. אם לא, נחזור על אותה פעולה עם הקלט 1, x 2 ,..., x k וכו'. אם המכונה הנ"ל תעצור אי פעם, זה יהיה הטבעי הקטן ביותר t עבורו g( t, x 2 ,..., x k )=0 , בפרט g( t ′ , x 2 ,..., x k ) מוגדרת לכל t ′ <t . מתי הריצה לא מסתיימת? בדיוק אם אחד מהבאים מתקיים:
  1. קיים t כך ש g( t, x 2 ,..., x k ) לא מוגדר ו g( t ′ , x 2 ,..., x k )>0 לכל t ′ <t .
  2. הסעיף הקודם לא מתקיים ו g( t, x 2 ,..., x k )>0 לכל t . ואילו במקומות בהם h לא מוגדרת כך שקיבלנו שיוויון.
ביתר פירוט: נבנה מכונה הפועלת באופן הבא. המכונה מסמנת את סוף הקלט ב S . בשלב הראשון המכונה T * תעתיק את הקלט x 2 ,..., x k מימין ל S ותוסיף 1B בהתחלה. בשלב הבא T * תחקה את הריצה של T על 0, x 2 ,..., x k כאשר היא מקפידה (וזה הרי T עושה ממילא) לא לזוז משמאל ל S . אם השלב הזה בריצה הסתיים במקום כלשהו על הסרט מימין ל S יהיה כתוב E (כי כך T עובדת). אם בין S ל E לא מופיע התו 1 , אז T * תחזור עד להתחלת הקלט של T * (משמאל ל S ) תמחק את כל הקלט ותעצור. אם בין S ל E מופיע התו 1 המכונה תחזור לתחילת הקלט של T * , תכתוב 1 לפני ה B הראשון ותתחיל מההתחלה.
הגדרה #. פונקציה f: N k → N m תיקרא חשיבה/רקורסיבית אם היא מתקבלת מן הפונקציות {x+y,x ⋅ y, C < ( x,y ), Π k n ( x 1 ,..., x n ),1,0} על ידי מספר סופי של הרכבות והפעלה של האופרטור μ x . במילים אחרות, משפחת הפונקציות החשיבות זו המשפחה/אוסף הקטנ/ה ביותר של פונקציות מ N k ל N m שמכיל/ה את הפונקציות הנ"ל וסגור/ה תחת הרכבה והאופרטור μ x .
משפט #. פונקציה f: N k → N m חשיבה אם ורק אם היא חשיבה טיורינג.
הוכחנו שכל פונקציה חשיבה היא חשיבה טיורינג. תרגיל: הפונקציה n mapstochar → n! היא חשיבה טיורינג. הוכח שהפונקציה חשיבה. שאלה כמעט זהה: מדוע הפונקציה f(m)={ n m= 2 n 0 m=1orelse חשיבה?
הגדרה #. תהי A ⊆ N m אזי χ A = N m → N זו הפונקציה המוגדרת על ידי χ A (x) = { 1 x ∈ A 0 else . χ A נקראת הפונקציה המציינת של A .
הגדרה #. יחס A ⊆ N m נקרא חשיב אם χ A פונקציה חשיבה.
טענה #. משפחת היחסים החשיבים סגורה תחת פעולות בוליאניות, כלומר תחת איחודים, חיתוכים והשלמה.
הוכחה:  
יוצא, למשל, כי היחס A( x,y )=( x ≤ y ) חשיב. זה פשוט איחוד היחסים החשיבים C < ( x,y ) ו- x=y .
טענה #. (הגדרה לפי מקרים): תהיינה f 1 ,..., f n פונקציות חשיבות k -מקומיות, ו- A 1 ,..., A n ⊆ N k זרות וחשיבות, כך ש ⋃ i=1 n A i = N k . אזי הפונקציה f(x) = { f 1 (x) x ∈ A 1 ⋮ ⋮ f n (x) x ∈ A n חשיבה.
הוכחה: ∑ i=1 n f i (x) ⋅ χ A i (x) וזו פונקציה חשיבה כי χ A i חשיבות, f i חשיבות והחיבור והכפל חשיבים.

14 פונקציות חשיבות - המשך

הגדרה #. יהי A ⊆ N k+1 יחס חשיב, k+1 מקומי. נגדיר אופרטור: μ x<z ( A( x, y ‾ ) ) = { t t<z ∧ μ x ( χ A ( x, y ‾ ) )=t z else .
טענה #. אם A ⊆ N k+1 יחס חשיב אז הפונקציה h( z, y ‾ ) ≡ μ x<z ( A( x, y ‾ ) ) חשיבה.
הוכחה: פשוט לפי המשפט על הגדרה לפי מקרים [אבל צריך מעט להיזהר כי מה הם המקרים?]. לחילופין אפשר נשים לב ש- h( z, y ‾ ) = μ x ( χ A ( x, y ‾ ) ⋅ C = ( x,z ) ) כאשר C = ( x,z )=0 ⇐ ⇒ x=z , וברור שזו פונקציה חשיבה. נשים לב h( z, y ‾ ) תמיד מוגדרת, כלומר פונקציה שלמה.
מסקנה #. אם A ⊆ N k+1 יחס חשיב אז היחס B( z, y ‾ ) ≡ ( ∃ x<z )( A( x, y ‾ ) ) הוא חשיב.
הוכחה: ( z, y ‾ ) ∈ B ⇐ ⇒ C < ( h( z, y ‾ ),z )=1 . לכן זו פשוט הפונקציה χ B ולפי הטענה האחרונה זו פונקציה חשיבה. מדוע C < ( h( z, y ‾ ),z )= χ B ? כיוון ששתי הפונקציות מקבלות רק ערכים 0,1 יספיק להראות שלכל ( z, y ‾ ) מתקיים χ B ( z, y ‾ )=1 ⇐ ⇒ C < ( h( z, y ‾ ),z )=1 . לפי הגדרה χ B ( z, y ‾ ) = 1 ⇐ ⇒ ( ∃ x<z )( A( x, y ‾ ) ) ⇐ ⇒ h( z, y ‾ )<z .
במילים אחרות המסקנה אומרת שמשפחת היחסים החשיבים סגורה תחת כימות חסום. הערה חשובה מאוד: משפחת היחסים החשיבים איננה סגורה תחת כימות (שאינו חסום).
מטרה: לבנות פונקציה חשיבה β : N 2 → N כך שלכל סדרה סופית a ‾ =langle a 1 ,..., a n rangle של מספרים טבעיים קיים c a ‾ ∈ N (קוד הסדרה) המקיים:
  1. β ( c a ‾ ,0 )=n
  2. לכל i ≤ β ( c a ‾ ,0 ) מתקיים β ( c a ‾ ,i )= a i
  3. (מסיבות טכניות נרצה גם) β ( c a ‾ ,i )< c a ‾ לכל i ≤ β ( c a ‾ ,0 ) .
טענה #. (טענת עזר 1) קיימת פונקציה חשיבה Pr: N 2 → N שהיא חח"ע ועל. [יהיה שימושי לשים לב ש Pr שנמצא מקיימת Pr( x,y ) ≥ max{x,y} ].
הוכחה: Pr( x,y ) יהיה המקום של הזוג ( x,y ) במספור הזוגות:
0
1
2
3
4
5
6
0
0
1
3
6
10
15
↙
1
2
4
7
11
16
↙
⋮
2
5
8
12
17
↙
⋮
3
9
13
18
↙
⋮
4
14
19
↙
⋮
5
20
↙
⋮
6
↙
⋮
לא קשה לבדוק שהפונקציה הזאת היא פשוט 1 2 ( x+y ) ⋅ ( x+y+1 )+x . לפי התיאור הזה ברור ש:
  1. Pr( x,y ) חשיבה
  2. מקיימת Pr( x,y ) ≥ x וגם Pr( x,y ) ≥ y
  3. לפי התיאור הגרפי היא חח"ע ועל (הוכחה יותר אלגברית - מכירים ממבוא ללוגיקה).
 
טענה #. (טענת עזר 2 - משפט השאריות הסיני) יהי n ∈ N , m 1 ,..., m n מספרים טבעיים זרים בזוגות. יהיו k 1 ,..., k n מספרים טבעיים כלשהם (בד"כ מניחים k i < m i אבל זה לא חשוב). אזי קיים b ∈ N כך ש b ≡ m i k i לכל 1 ≤ i ≤ n .
הוכחה: ניקח d > = ∏ i=1 n m i . לכל b<d נגדיר b ‾ =langle bmod m 1 ,...,bmod m n rangle . יש d n-יות כאלה. לכן אם נראה שההעתקה b mapstochar → b ‾ חח"ע אזי היא בהכרח על (כהעתקה בין שתי קבוצות מגודל d ). נניח ש b ‾ 1 = b ‾ 2 כלומר b 1 ≡ m i b 2 לכל i , כלומר b 1 - b 2 ≡ m i 0 , בפרט m i | b 1- b 2 (בה"כ b 1 > b 2 ) לכל 1 ≤ i ≤ n . לכן b 1 - b 2 מחלק את המכפלה המשותפת הקטנה ביותר של ה m i . כיוון שה m i זרים בזוגות המכפלה המשותפת הקטנה ביותר היא d . אבל b 1 - b 2 <d וזו סתירה.
טענה #. (טענת עזר 3) לכל n ∈ N המספרים {1+i ⋅ ( n! ) } i=1 n זרים בזוגות.
הוכחה: נניח בשלילה ש p ראשוני מחלק את 1+i( n! ) ומחלק את 1+j( n! ) לאיזה i>j . לכן: p|( i-j ) ⋅ ( n! ) . כיוון ש p ראשוני הוא מחלק או את i-j או את n! . כיוון ש i-j<n בהכרח p מחלק את n! . אבל p אמור לחלק את 1+i( n! ) וזה לא ייתכן.
טענה #. תהי γ ( z,y,i )=Rem( z,1+y( i+1 ) ) כאשר Rem( t 1 , t 2 ) היא השארית של t 1 בחלוקה ב- t 2 . אזי:
  1. γ ( z,y,i ) חשיבה. מדוע? יספיק להראות ש Rem( t 1 , t 2 ) חשיבה. אבל Rem( t 1 , t 2 )= μ z ( t 2 | t 1 -z ) והיחס t 2 | t 1 הוא חשיב, למשל ע"י ( ∃ x< t 2 )( x ⋅ t 2 = t 1 ) .
  2. לכל סדרה סופית langle a 1 ,..., a n rangle של טבעיים יש y,z כך שלכל 0<i ≤ n מתקיים γ ( z,y,i )= a i . מדוע? נבחר k>n כלשהו ונבחר y=k! . לפי טענת עזר 3 קיים z כך ש γ ( z,y,i )= a i לכל i ≤ n .
  3. (טכני) γ ( z,y,i ) ≤ z לכל z,y,i .
הפונקציה β ( b,i ) המבוקשת תהיה γ ( P r L (b),P r R (b),i ) כאשר P r L (b)= Π 1 ( P r -1 (b) ) ו- P r R (b)= Π 2 ( P r -1 (b) ) . הדבר היחיד שנותר לוודא P r L ,P r R הן פונקציות חשיבות.

15 הצפנות

חזרה: אם A( x,y ) יחס חשיב אז ( ∃ x<z )A( x, y ‾ ) יחס חשיב. ( μ x<z )A( x, y ‾ ) = { t μ x ( χ A ( x, y ‾ ) )=t,t<z z else פונקציה שלמה. הפונקציה גם חשיבה כי היא שווה ל μ x ( χ ¬ A ( x, y ‾ ) ⋅ C=( x,z ) ) .
נאמר ש β : N 2 → N מצפינה סדרות סופיות אם לכל סדרה סופית langle a 1 ,..., a n rangle יש a ‾ ∈ N כך ש β ( a ‾ ,0 )=n ולכל 1 ≤ 1 ≤ n מתקיים β ( a ‾ ,i )= a i .
טענה #. הפונקציה ( x,y ) mapstochar → Pr (x+y ) 2 +( x+y ) 2 +x היא חח"ע ועל מ N 2 ל N .
 
טענה #. לכל m 1 ,..., m k זרים בזוגות ולכל a 1 ,..., a k טבעיים יש b ∈ N כך ש b ≡ m i a i לכל i .
 
טענה #. לכל n ∈ N המספרים 1+n!,1+2( n! ),...,1+n( n! ) זרים בזוגות.
 
טענה #. נגדיר γ ( z,g,i )=Rem( z,1+y( i+1 ) ) מקיימת:
  1. γ חשיבה
  2. לכל סדרה סופית langle a 1 ,..., a n rangle קיימים z,y כך שלכל 1 ≤ i ≤ n מתקיים a i = γ ( z,y,i )
  3. γ ( z,y,i ) ≤ z
לגבי 2 ניקח את max{ a i ,n } i=1 n <k וניקח y=k! . לפי טענה 3 מתקיים כי 1+y( i+1 ) זרים בזוגות. לפי הטענה השניה יש z שעונה על הדרישה. ביתר דיוק, יש z כך שלכל i מתקיים z ≡ i+y( i+1 ) a i . אבל בעצם a i =Rem( z,1+y( i+1 ) ) כי a i <1+y( i+1 ) .
 
טענה #. הפונקציה β ( y,i )= γ ( P r L (y),P r R (y),i ) היא פונקצית זיווג חשיבה כאשר P r L (y)= Π 1 P r -1 (y) ו P r R (y)= Π 2 P r -1 (y) .
הוכחה: מטענה 4 ברור כי β ( y,i ) מצפינה סדרות סופיות. בהינתן סדרה סופית langle a 1 ,..., a n rangle טענה 4 סעיף (2) מבטיחה t 1 , t 2 ∈ N כך ש γ ( t 1 , t 2 ,i )= a i לכל 1 ≤ i ≤ n . נחליף את הסדרה בסדרה langle n, a 1 ,..., a n rangle , נמצא t 1 , t 2 כמובטח ונגדיר y=Pr( t 1 , t 2 ) אז β ( y,0 )= γ ( t 1 , t 2 ,0 )=n וגם β ( y,i )= γ ( t 1 , t 2 ,i )= a i . נשאר רק לוודא ש β חשיבה. מספיק לוודא ש P r -1 (y) היא חשיבה ומלאה/שלמה. הפונקציה שלמה כי Pr היא על. הפונקציה חשיבה פשוט כי Π 1 ( P r -1 (y) ) = μ t 1 [ ( ∃ t 2 )Pr( t 1 , t 2 )=y ]= μ t 1 ( ( ∃ t 2 <y )Pr( t 1 , t 2 )=y )
מעתה ועד עולם נקבע פונקציה β כנ"ל.
הגדרה #. נאמר ש x מצפין סדרה סופית אם אין x ′ <x כך ש β ( x ′ ,0 )= β ( x,0 ) ולכל i ≤ β ( x,0 ) מתקיים β ( x ′ ,i )= β ( x,i ) .
טענה #. היחס θ (x) האומר " x מצפין סדרה סופית" הוא חשיב.
הוכחה: θ (x)= ¬ ( ∃ x ′ <x )[ i ≤ β ( x,0 ) → β ( x ′ ,i ) ]= β ( x,i ) .
מטרתנו, כזכור, להוכיח שבהינתן מכונת טיורינג T ו n ∈ N הפונקציה f T n חשיבה. נקבע אחת ולתמיד מכונת טיורינג T ו n ∈ N ונראה כיצד למצוא פונקציה חשיבה שזהה ל f T n . נזדקק להרבה טענות עזר. כיוון שאנחנו מעוניינים רק ב f T n ולא במכונה עצמה אז אפשר לשנות את T איך שנרצה כל עוד לא נשנה את הפונקציה שהיא מחשבת. לכן, בה"כ, T מכונת טיורניג תקנית:
  1. הא"ב של T כולל רק את {1,B} ונק' ההתחלה והסיום {S,E} .
  2. למכונה יש מצב פנימי יחיד q ˆ שכל ריצה מסתיימת מסתיימת בו, ו q ˆ אינו מופיע במהלך הריצה.
  3. בתום הריצה הראש הקורא נמצא על S ובין S ל E יש רק אחדות.
מכיוון שמספר המצבים הפנימיים של T סופי לא יזיק להניח ש {1,B} מיוצגים ע"י המספרים הטבעיים {1,0} בהתאמה ו {S,E} ע"י {2,3} בהתאמה והמצבים הפנימיים מיוצגים ע"י {4,...,k} כאשר q 0 מיוצג ע"י 4 ו q ˆ מיוצג ע"י k .
כזכור, מצב של T זו שלשה langle n,q,h rangle כאשר n המיקום של הראש ביחס ל S שמיקומו 0 , q המצב הפנימי, ו- h: Z → {0,1,2,3} מתארת את התאים במכונה. כמובן יספיק להניח ש h מתארת רק את המספר הסופי של התאים שבין S ל E . אפשר לתאר מצב ע"י סדרה מהצורה הבאה: langle α 1 , α 2 ,..., α n ,q, α n+1 ,..., α r rangle כאשר α 1 =2, a r =3 ולכל 1<i<r מתקיים a i ∈ {0,1} .
טענה #. (1) היחס ϕ (x) האומר " x מצפין מצב של המכונה T " חשיב.
הוכחה: היחס יתואר ע"י חיתוך של הדרישות הבאות:
  1. θ (x) - היחס האומר ש x מצפין סדרה.
  2. לכל 0<i ≤ β ( x,0 ) מתקיים β ( x,i ) ∈ {0,...,k}
  3. β ( x,1 )=2 וגם β ( x, β ( x,0 ) )=3
  4. קיים 0<i ≤ β ( x,0 ) יחיד כך ש β ( x,i ) ∈ {4,...,k} .
כיוון שכל אלה חשיבים - גמרנו.
טענה #. (2) היחסים ϕ s (x) , " x מצפין מצב התחלתי של T ", " x מצפין מצב סופי של T " - כולם חשיבים.
הוכחה: ϕ S (x) זה חיתוך של ϕ (x) עם הדרישה הנוספת ש β ( x,2 )=4 . ϕ E (x) כנ"ל עם β ( x,2 )=k .
טענה #. (3) היחס ϕ ( x,y ) האומר " x,y מייצגים מצבים של T ו y המצב העוקב של x לפי T " הוא יחס חשיב.
הוכחה: זה כמובן חיתוך של התנאים ϕ (x), ϕ (y) עם התנאי הנוסף ש y המצב העוקב ל x . לכל p ∈ I(T) (לכל פקודה של T ) נגדיר יחס ϕ p ( x,y ) האומר x,y מצבים של T ו- y עוקב של x לפי p ובפרט x מצב רלוונטי לפקודה p . " x מצב רלוונטי לפקודה p " זה פשוט ϕ (x) וגם אם β ( x,i )>3 ל i>1 אז p פקודה מהצורה β ( x,i-1 ) β ( x,i )** . במילים אחרות אם p היא הרביעייה langle α ,q, α ′ , q ′ rangle אז x רלוונטי ל p אם β ( x,i-1 )= α , β ( x,i )=q . נסמן זאת ϕ p (x) . לומר ש y עוקב של x לפי p זה לומר ϕ (x), ϕ (y) . ϕ p (x) עכשיו מתחלק לפי מהות הפקודה p . נטפל למשל במקרה ש p=langle α ,q, α ′ , q ′ rangle כאשר α ′ ∈ {0,1} . מתי y יתקבל מ x ע"י הפקודה p ? אם x=langle α 1 ,..., α i ,q, α i+1 ,..., α k rangle,y=langle α 1 ,..., α i , q ′ , α i+1 ,..., α k rangle . פשוט צריך לדרוש:
  1. נסמן i 0 להיות ה i היחיד כך ש i ≤ β ( x,0 ) ו- β ( x, i 0 ) ∈ {4,...,k} .
  2. נדרוש ש β ( y, i 0 )= q ′ , β ( y, i 0 -1 )= α ′ ובכל מקרה אחר β ( y,j )= β ( x,j ) .
הטיפול בפקודות של תזוזה הוא דומה. זה מקרה ש ϕ p ( x,y ) חשיבה. לומר ש y עוקב של x זה פשוט > ϕ (x) ∧ ϕ (y) ∧ ⋁ p ∈ I ϕ p ( x,y ) .
טענה #. (4) היחס ρ (x) האומר " x מקודד ריצה מסתיימת של T " הוא חשיב.
הוכחה:  
  1. θ (x) - x מצפין סדרה.
  2. ϕ S ( β ( x,1 ) ) כלומר האיבר הראשון בסדרה ש x מצפין הוא מצב התחלתי של T .
  3. ϕ E ( β ( x, β ( x,0 ) ) ) - האיבר האחרון בסדרה הוא מצב סופי של T .
  4. לכל 1 ≤ i< β ( x,0 ) מתקיים ϕ ( β ( x,i ), β ( x,i+1 ) ) כלומר כל איבר בסדרה הוא מצב עוקב של המצב המוצפן ע"י האיבר הקודם לו.
טענה #. (5) f E (x)=n זו הפונקציה שמחזירה n אם x מצפין מצב סופי של T ו n הפלט של המכונה במצב זה. 0 אחרת. זו פונקציה חשיבה: χ ϕ E (x) ⋅ ( β ( x,0 )-3 ) .

16 חשיבות

היינו בעיצומה של ההוכחה שכל פונקציה חשיבה טיורינג היא חשיבה.
טענה #. (1) היחס ϕ (x) האומר " x מצפין מצב של המכונה T " חשיב.
 
טענה #. (2) היחסים ϕ s (x) , " x מצפין מצב התחלתי של T ", " x מצפין מצב סופי של T " - כולם חשיבים.
 
טענה #. (3) היחס ϕ ( x,y ) האומר " x,y מייצגים מצבים של T ו y המצב העוקב של x לפי T " הוא יחס חשיב.
 
טענה #. (4) היחס ρ (x) האומר " x מקודד ריצה מסתיימת של T " הוא חשיב.
 
טענה #. (5) ϕ E (x)=n זו הפונקציה שמחזירה n אם x מצפין מצב סופי של T ו n-1 הפלט של המכונה במצב זה. 0 אחרת. זו פונקציה חשיבה: χ ϕ E (x) ⋅ ( β ( x,0 )-3 ) . נדרוש ש ϕ E (x)=0 אחרת.
 
טענה #. היחס " x מקודד מצב התחלתי של T שבו הקלט הוא x 1 ,..., x n " הוא יחס חשיב. נסמן זאת ϕ s ( x, x 1 ,..., x n ) .
כדי להוכיח את המשפט עלינו להראות ש f T n ( x 1 ,..., x n ) פונקציה חשיבה. נגדיר פונקציה חשיבה באופן הבא: f( x 1 ,..., x n ) = ϕ E ( μ x * ( ρ (x) ∧ ϕ s ( ϕ s,0 (x), x 1 ,..., x n ) ) ) כאשר ϕ s,0 (x)= β ( x,1 ) - האיבר הראשון בסדרה ש x מקודד, וכאשר μ x * ( A( x,y ) ) זה ה x המזערי עבורו χ A ( x,y )=1 .
טענה #. f( x 1 ,..., x n )= f T n ( x 1 ,..., x n ) ובפרט f מוגדרת אם ורק אם ריצת T על x 1 ,..., x n עוצרת.
הוכחה: ראשית נבדוק שתחומי ההגדרה של שתי הפונקציות זהים. אם T עוצרת על x 1 ,..., x n אז קיים x כך ש ρ (x) ∧ ϕ s ( ϕ s,0 ( x 1 ,..., x n ) ) - כלומר קיים x המקודד ריצה מסתיימת של T המתחילה בקלט x 1 ,..., x n . אם נבחר x 0 הקטן ביותר המקיים זאת אז x 0 = μ x * ( ρ (x) ∧ ϕ s ( ϕ s,0 (x), x 1 ,..., x n ) ) כי לכל x ′ < x 0 הפונקציה χ ρ (x) ⋅ χ ϕ s מוגדר ולכן מהגדרת האופרטור μ x * , ואז f( x 1 , x n ) = ϕ E ( x 0 )= def f T n ( x 1 ,..., x n ) נניח ש T אינה עוצרת על x 1 ,..., x n אז ρ (x) ∧ ϕ s ( ϕ s,0 (x), x 1 ,..., x n ) לעולם אינו מוגדר ולכן הפונקציה μ x * ( ρ (x) ∧ ϕ s ( ϕ s,0 (x), x 1 ,..., x n ) ) אינה מוגדרת.
עד עכשיו קודדנו מצבים וריצות של מכונות טיורינג, אבל אין סיבה לא לקודד גם את המכונות עצמן. מכיוון שאנחנו מתעניינים רק בפונקציות החשיבות (טיורינג) ולא במכונות עצמן, אפשר לזהות מכונת טיורינג עם רשימת הפקודות שלה. ומכיוון שהא"ב סופי ורשימת הפקודות סופית (וכבר זיהינו את הא"ב עם המספרים הטבעיים {0..k} ). אם רק נוסיף לזיהוי הזה את k+1 כפקודה L ואת k+2 כפקודה R נוכל לקודד את המכונה על ידי מספר טבעי. נקבע פעם אחת ולתמיד קידוד של כל מכונת טיורינג, ולמכונה T נסמן lceilTrceil את הקוד של T . אם e ∈ N הוא קוד של מ"ט נסמן T e את המכונה ש- e מקודד. יהיה נוח להניח שאם n ∈ N אינו מקודד מ"ט אז נחליט ש n-e מקודד את המכונה שאינה עוצרת על אף קלט.
משפט #. לא קיימת פונקציה חשיבה f: N → N כך ש f(e) = { 1 T e haltsoninput0 0 else
הוכחה: נניח בשלילה שקיימת פונקציה f כנ"ל. נגדיר פונקציה g: N → N ע"י g(e) = { T e (e)+1 f(e)=1 0 else מההנחה (ומהמשפט האחרון, ומהמשפט על ההגדרה לפי מקרים) g פונקציה חשיבה (ואפילו שלמה), ומקודדת, נאמר ע"י e 0 . אז: מצד אחד T e 0 ( e 0 )=g( e 0 ) ומצד שני g( e 0 )= T e 0 ( e 0 )+1 .
מסקנה #. היחס A ⊆ N המוגדר ע"י e ∈ A ⇐ ⇒ T e (e)halts אינו יחס חשיב. מצד שני A הנ"ל היא תחום של מכונת טיורינג T . הרעיון? המכונה מריצה את T e (e) ומחזירה את התשובה, אם היא אי פעם מתקבלת. ביתר פירוט, ניקח U מ"ט אוניברסלית ונשים לב ש U ( e,e ) עוצרת אם ורק אם e ∈ A . לכן יש e בתחום של המכונה U ( x,x ) .
הגדרה #. מכונת טיורינג T תיקרא אוניברסלית אם f T 2 ( e,n )= T e (n) לכל ( e,n ) ∈ N 2 (ובפרט אם T e לא עוצרת על הקלט n אז f T 2 ( e,n ) לא מוגדרת).
משפט #. קיימת מכונת טיורינג אוניברסלית.
הוכחה: הרעיון פשוט, ההוכחה מייגעת, ע"י תיאור המכונה. דרך אחרת: בעזרת פונקציות חשיבות. נגדיר את f T 2 ( e,n ) באופן הבא. נגדיר את היחסים הבאים:
ההמשך זהה בדיוק להוכחת משפט השקילות.
הגדרה #. קבוצה A ⊆ N תקרא ניתנת למניה חשיבה (נל"ח או נל"ר - ניתנת למניה רקורסיבית) אם A היא התחום של פונקציה חשיבה.
ראינו שקיימות קבוצות נל"ח שאינן חשיבות.
משפט #. התנאים הבאים שקולים לקבוצה A ⊆ N :
  1. A נל"ח (תחום של פונקציה חשיבה)
  2. A היא התמונה של פונקציה חשיבה
  3. A היא התמונה של פונקציה חשיבה מלאה
  4. A היא מהצורה { x ∈ N :( ∃ y ) ϕ ( x,y ) } לאיזה יחס חשיב ϕ ( x,y ) .
  5. A היא מהצורה { x ∈ N :( ∃ y ‾ ) ϕ ( x, y ‾ ) } לאיזה יחס חשיב ϕ ( x,y )

17 מניה רקורסיבית

משפט #. תהי ∅ ∖ =A ⊆ N אזי התנאים הבאים שקולים:
  1. A נל"ח
  2. A הטווח של פונקציה חשיבה
  3. A הטווח של פונקציה מלאה
  4. קיים יחס חשיב B ⊆ N 2 כך ש A={x:( ∃ y )B( x,y )}
  5. כנ"ל עבור B ⊆ N k+1 ו- A={x:( ∃ y 1 ,..., y k )B( x, y 1 ,..., y k )}
הוכחה:  
משפט #. (משפט הרקורסיה) תהי C( x,y ) פונקציה חשיבה. אזי קיימת מ"ט T כך ש- C( lceilTrceil,y )=T(y)= f T 1 (y) לכל y .
טענה #. קיימת מכונת טיורינג T כל שלכל n ∈ N מתקיים f T 1 (n)=lceil w n rceil כאשר w n היא המכונה אשר על הקלט הריק כותבת את המספר n . (ההוכחה - בתרגיל הבית).
הוכחה: המכונה T תהיה הרכבה של 3 מכונות: ABC (מפעילים קודם את A אח"כ את B אח"כ את C ). המכונה A על הקלט y תחזיר את הפלט lceilBrceillceilCrceil,y . מה עושה B על הקלט x,y ? היא כותבת את הקוד של המכונה שכותבת x [מטענת העזר] ואחריו את x,y . מה יהיה B( lceilBrceillceilCrceil,y ) ? B( lceilBrceillceilCrceil,y )=lceilArceillceilBrceillceilCrceil,y . יוצא ש- C( B( A(y) ) )=C( B( lceilBrceillceilCrceil,y ) )=C( lceilArceillceilBrceillceilCrceil,y ) אבל זה בדיוק מה שהיינו צריכים.
מסקנה #. (משפט נקודת השבת) תהי f: N → N פונקציה חשיבה ושלמה. אזי קיים e ∈ N כך ש f T e 1 = f T f(e) 1 .
 
מסקנה #. (משפט Rice) נגדיר יחס שקילות של N ע"י e 1 ∼ e 2 אם ורק אם f T e 1 1 = f T e 2 1 . תהי L ⊆ N כך שלכל e ∈ L אם e ′ ∼ e אז e ′ ∈ L . אזי L חשיבה אם ורק אם L= N או L= ∅ .
הוכחה: נניח בשלילה שלא. אז יש e 0 ∈ L ו- e 1 ∖ ∈ L . נגדיר פונקציה חשיבה: f(n)={ e 1 n ∈ L e 0 n ∖ ∈ L אז f חשיבה ושלמה. לכן ממשפט נקודת השבת יש e כך ש- f T e 1 = f T f(e) 1 . אם e ∈ L אז גם f(e) ∈ L כי L סגורה תחת ∼ . אבל אם e ∈ L אז e 1 =f(e) ו- e 1 ∖ ∈ L . באותו אופן בדיוק גם e ∖ ∈ L גורר סתירה.
דוגמה: בעיית העצירה אינה חשיבה. אין מכונת טיורינג המחליטה האם e קוד של מכונה שעוצרת על הקלט הריק. במילים אחרות L = {e ∈ N :eencodesamachinewhichhaltsonemptyinput} אינה חשיבה. ברור ש- L סגורה תחת ∼ . לפי משפט רייס כיוון ש- L ∖ = ∅ (יש מ"ט שעוצרת על כל קלט ובפרט על הקלט הריק) וגם N \ L ∖ = ∅ (יש מכונות שלא עוצרות על שום קלט). לכן לפי משפט רייס L אינה חשיבה.
הוכחה: (משפט נקודת השבת) תהי U ( x,y ) מ"ט אוניברסלית ו- C( x,y )= U ( f(x),y ) . אז C מ"ט. לכן יש T כך ש- U ( f(lceilTrceil),y )=C( lceilTrceil,y )=T(y) . אז e=lceilTrceil .
הערות #.  
  1. קבוצה A ⊆ N חשיבה היא נל"ח
  2. קבוצה A ⊆ N נל"ח היא חשיבה אם ורק אם גם המשלים של A נל"ח. הוכחה: אם גם A וגם N \ A נל"ח אז יש מ"ט T 1 , T 2 שמחשבות את איבריהן. אפשר להניח שהן f T 1 1 והן f T 2 1 פונקציות שלמות. לכל מספר n נתחיל לחשב את T 1 (1), T 1 (2),... ובמקביל את T 2 (1), T 2 (2),... (אפשר לסירוגין). המכונה תעצור ברגע שיתקבל פלט n . כיוון ש A= f T 1 1 ( N ) וגם N \ A= f T 2 1 ( N ) קיים m ∈ N כך ש f T 1 1 (m)=n או f T 2 1 (m)=n . בכל מקרה אחרי 2m חישובים המכונה שלנו תיעצר. אם היא עצרה על הריצה של T 1 (m) אז n ∈ A אחרת n ∖ ∈ A .

18 פונקציות יציגות

תרגיל: תהיינה A 1 , A 2 ⊆ N נל"ח אז:
  1. גם A 1 ∪ A 2 נל"ח
  2. גם A 1 ∩ A 2 נל"ח
  3. יש דרך אחת סבירה להגדיר מתי A ⊆ N k נל"ח ואז הטלה של קבוצה נל"ח היא נל"ח
הגדרה #. תהי שפה L חשיבה. מספור גדל של הנוסחאות F( L ) ב- L זו פונקציה g:F( L ) → N המוגדרת באינדוקציה באופן הבא:
  1. שם עצם x i יקודד ע"י g( x i )= 2 1 ⋅ 3 i
  2. קבוע אישי c i יקודד ע"י g( c i )= 2 2 ⋅ 3 i
  3. שם עצם מהצורה F i ( t 1 ,..., t n ) יקודד ע"י g( F i ( t 1 ,..., t n ) ) = 2 3 ⋅ 3 i ⋅ 5 g( t 1 ) ⋅ 7 g( t 2 ) ⋅ ⋯ ⋅ P n+2 g( t n )
  4. נוסחה מהצורה R i ( t 1 ,..., t n ) יקודד ע"י g( R i ( t 1 ,..., t n ) ) = 2 4 ⋅ 3 i ⋅ 5 g( t 1 ) ⋅ 7 g( t 2 ) ⋅ ⋯ ⋅ P n+2 g( t n )
  5. נוסחה ϕ מהצורה ϕ = ¬ ψ תקודד ע"י g( ϕ )= 2 5 ⋅ 3 g( ψ )
  6. נוסחה ϕ מהצורה ϕ = ψ 1 → ψ 2 תקודד ע"י g( ϕ )= 2 6 ⋅ 3 g( ψ 1 ) ⋅ 5 g( ψ 2 )
  7. נוסחה ϕ מהצורה ϕ =( ∃ x i ) ψ תקודד ע"י g( ϕ )= 2 7 ⋅ 3 i ⋅ 5 g( ψ ) (הכמת ∀ בדומה)
 
הגדרה #.  
  1. תורה T בשפה L היא כריעה אם הקבוצה {g( ϕ ):T ⊢ ϕ } חשיבה.
  2. תורה היא חשיבה אם {g( ϕ ): ϕ ∈ T} חשיבה.
טענה #.  
  1. מספור גדל הוא חח"ע (באינדוקציה על יצירת הנוסחה)
  2. בהינתן שפה חשיבה (או סופית) L היחס " n מקודד נוסחה בשפה L " הוא חשיב.
הוכחה: (רעיון כללי) נשים לב (קל לראות באינדוקציה) שאם ϕ נוסחה באורך n אז g( ϕ )>n . בנוסף, אם ב- ϕ מופיע סימן פונקציה, סימן יחס, קבוע אישי או משתנה עם אינדקס i>n אז (באינדוקציה) g( ϕ )>n .
לכן השאלה האם n מספר גדל של נוסחה שקולה לשאלה האם קיימת נוסחה ϕ באורך קטן-שווה ל- n , שכל הסימנים הלא-לוגיים המופיעים בה הם עם אינדקס קטן או שווה ל- n . ומספר גדל של ϕ הוא n .
אבל קבוצת הנוסחאות ϕ מאורך קטן-שווה ל- n , שכל הסימנים בה עם אינדקס קטן-שווה ל- n היא סופית, כלומר זהו כימות חסום. לכן מספיק לבדוק שהפונקציה ששולחת נוסחה למספר גדל שלה היא חשיבה טיורינג. (זה עסק מייגע, אבל לא קשה.)
הגדרה #.  
  1. תהי f: N → N , נאמר שתורה T בשפה המרחיבה את ( 0,s ) מייצגת (חלש) את f אם קיימת נוסחה ϕ ( x,y ) בשפה L כל שלכל n ∈ Dom(f) מתקיים T ⊢ ( ∀ y )( ϕ ( n ¯ ,y ) ⇐ ⇒ f(n) ¯ ) כאשר הסימון n ¯ := s n (0) עבור s פונקציית העוקב.
  2. יחס A ⊆ N מיוצג ב- T אם χ A מיוצגת ב T .
 
הגדרה #. תורת פיאנו (Peano Arithmetic) זו קבוצת הפסוקים הבאה בשפה L ={0,+, ⋅ ,s) :
  1. ( ∀ x )( s(x) ∖ =0 )
  2. ( ∀ x ∀ y )( s(x)=s(y) → x=y )
  3. ( ∀ x )( x+0=x )
  4. ( ∀ x ∀ y )( x+s(y)=s( x+y ) )
  5. ( ∀ x )( x ⋅ 0=0 )
  6. ( ∀ x ∀ y )( x ⋅ s(y)=x ⋅ y+x )
  7. סכימת האינדוקציה: לכל נוסחה ϕ ( x,y ) אקסיומה מהצורה: ( ∀ x )[ ϕ ( x ‾ ,0 ) ∧ ∀ y( ϕ ( x ‾ ,y ) → ϕ ( x ‾ ,s(y) ) → ∀ y( ϕ ( x ‾ ,y ) ) ]
משפט #. כל פונקציה חשיבה ניתנת לייצוג ב- PA . יתר על כן, קיימת תורה N סופית כך ש- PA ⊢ N וכל פונקציה חשיבה מיוצגת ב- N .
תרגיל: אם f: N → N שלמה ומיוצגת ב- PA אז f חשיבה.
מסקנה #. התורה N שמובטחת במשפט, אינה כריעה.
הוכחה: תהי ϕ ( e,z,n ) הנוסחה האומרת שמ"ט T e (שהקוד שלה הוא e ) עוצרת על הקלט n אחרי z צעדים.
היחס ϕ ( e,z,n ) חשיב [הוכחנו], לכן לפי המשפט מיוצג ב- N . כלומר אם T e (n) לא עוצרת אז לכל z מתקיים N ⊢ ¬ ϕ ( e,z,n ) .
מצד שני, אם T e (n) עוצרת אז N ⊢ ϕ ( e,z,n ) לאיזה z . נניח בשלילה ש- N כריעה אז N ⊢ ( ∃ z ) ϕ ( e,z,n ) אם ורק אם T e (n) עוצרת.
אבל מכריעות נקבל שלכל זוג langle e,n rangle אפשר לדעם האם N ⊢ ( ∃ z ) ϕ ( e,z,n ) או N ⊢ ( ¬ ∃ z ) ϕ ( e,z,n ) . כלומר אפשר להכריע האם T e (n) עוצרת או לא. אבל לפי משפט רייס זו איננה קבוצה חשיבה. סתירה.
הערה: אם N ⊆ T ( N התורה המובטחת במשפט) אז:
  1. כל פונקציה חשיבה ניתנת לייצוג ב- T
  2. לכן, T איננה כריעה, כי אותה ההוכחה ש- N אינה כריעה תעבוד עבור T .
הערה: אם תורה T היא חשיבה ושלמה אז T כריעה. להלן אלגוריתם הכרעה:
נראה בהמשך שאם T חשיבה אז C T :={g( ϕ ):T ⊢ ϕ } נל"ח. כיוון ש- T שלמה, כדי לבדוק האם T ⊢ ϕ נפעיל את המכונה המונה את C T . בכל שלב נבדוק האם האיבר שהמכונה פלטה הוא הוכחה של ϕ או הוכחה של ¬ ϕ . השלמות מבטיחה לנו שאחד מהם יתקבל בזמן סופי. אם מתקבל ϕ - ניצחנו. אם מתקבל ¬ ϕ - גם ניצחנו.
מסקנה #. כל תורה T כך ש- N ⊆ T ⊆ PA מהמסקנה הקודמת אינה כריעה. (למשל תורת המספרים איננה כריעה).

19 פונקציות יציגות

תזכורת: פונקציה f: N k → N תקרא מיוצגת (חלש) בתורה T (בשפה עם סימן קבוע 0 וסימן פונקציה חד מקומי s ) אם קיימת נוסחה ϕ ( x,y ) כך שלכל n ‾ ∈ Dom(f) מתקיים T ⊢ ( ∀ y )( ϕ ( n ‾ ¯ ,y ) ⇐ ⇒ f(n) ¯ =y ) כאשר n ¯ = s n (0) .
משפט #. כל פונקציה חשיבה יציגה בתורת פאנו ואפילו יש תת-תורה סופית של PA שבה כל פונקציה חשיבה יציגה.
מסקנה #. תהי N ⊆ PA כמובטח במשפט. אזי N אינה כריעה.
הוכחה: יהי ϕ ( e,n,z ) היחס האומר "המכונה שהקוד שלה e עצרה על הקלט n אחרי לכל היותר z מהלכים". אז ברור ש- ϕ ( e,n,z ) הוא יחס חשיב. מהמשפט נובע שלכל שלשה langle e,n,z rangle ∈ N 3 מתקיים N ⊢ ϕ ( e,n,z ) אם ורק אם langle e,n,z rangle עומדת ביחס, כלומר המכונה e עוצרת על n אחרי לא יותר מ z צעדים. לכן אם langle e,n rangle עוצרת יש z 0 כך ש N ⊢ ϕ ( e ¯ , n ¯ , z 0 ¯ ) . לכן אם langle e,n rangle עוצרת אז N ⊢ ( ∃ z ) ϕ ( e ¯ , n ¯ ,z ) . מצד שני, אם langle e,n rangle לא עוצרת אז N ∖ ⊢ ϕ ( e ¯ , n ¯ , z 0 ¯ ) לכל z 0 ¯ . אבל N | = PA ולכן N | = N . לכן לא ייתכן ש N ⊢ ( ∃ z ) ϕ ( e ¯ , n ¯ ,z ) אבל מהנחתנו זה לא מתקיים. יוצא N ⊢ ( ∃ z ) ϕ ( e ¯ , n ¯ ,z ) אם ורק אם langle e,n rangle עוצרת. לכן אילו הייתה N כריעה היינו יכולים להכריע את בעיית העצירה: בהינתן זוג langle e,n rangle היינו פשוט שואלים אם N ⊢ ( ∃ z )( e ¯ , n ¯ ,z ) . אם כן - langle e,n rangle עוצרת, ואם לא אז langle e,n rangle לא עוצרת.
מסקנה #. כל תורה N ⊆ T ⊆ PA מהמסקנה הקודמת אינה כריעה.
ניגש להוכחת המשפט עצמו.
תהי N ⊆ PA התורה הבאה:
טענה #. PA ⊢ N .
הוכחה: צריך להוכיח רק את PA ⊢ {N(7),N(8),N(9)} . כלומר צריך להוכיח: PA ⊢ ( ∀ x ) ¬ ( x<0 ) ⇐ ⇒ ( ∀ x ∀ z )( x+z=0 → z=0 ) ⇐ ⇒ ( ∀ x ∀ z )( z ∖ =0 → x+z ∖ =0 ) ⇐ ⇒ ( ∀ x ∀ z )( ( ∃ y )s(y)=z → x+s(y) ∖ =0 ) אבל PA ⊢ z ∖ =0 → ( ∃ y )( ( sy )=z ) . לכן יספיק להוכיח ש- PA ⊢ x+s(y)=s( x+y ) . זה יספיק כי אז נקבל ( ∀ x ∀ z )( ( ∃ y )( sy=z ) ) → s( x+y ) ∖ =0 . ההוכחה ל- N8 ו- N9 דומה מאוד.
הוכחה: נראה שכל פונקציה חשיבה יציגה ב- N . לשם כך יספיק להראות: משפחת הפונקציות היציגות ב- N מכילה מכילה את הפונקציות החשיבות הבסיסיות וסגורה תחת הרכבות ותחת מזעור.
טענה #. (1) פונקציית ההיטל P i ( x 1 ,..., x n )= x i יציגה ע"י ϕ ( x 1 ,..., x n ,y ):= x i ≈ y
הוכחה: יש להראות ש N ⊢ ( ∀ y ) ϕ ( k 1 ¯ ,..., k n ¯ ,y ) ⇐ ⇒ P i ( k 1 ,... k n )=y לכל k 1 ,..., k n ∈ N . אבל זה שקול ל N ⊢ ( ∀ y ) k i ¯ =y ⇐ ⇒ k i =y ¯ .
טענה #. (2) הפונקציה c 0 (x)=0 יציגה ב- N ע"י ϕ ( x,y ):=y ≈ 0 . ההוכחה קשה באותה מידה.
 
טענה #. (3) הפונקציה x+y יציגה ב- N ע"י ϕ ( x,y,z ):=z ≈ x ⊕ y .
הוכחה: עלינו להראות N ⊢ ( n 1 ¯ ⊕ n 2 ¯ = n 1 + n 2 ¯ ) . באינדוקציה על n 2 . עבור n 2 =0 מקבלים n 1 ¯ +0= n 1 ¯ . נניח עבור n 2 ונוכיח עבור n 2 +1 : n 1 ¯ ⊕ n 2 +1 ¯ = n 1 ¯ ⊕ s( n 2 ¯ )=s( n 1 ¯ ⊕ n 2 ¯ )=s( n 1 ¯ + n 2 ¯ )= n 1 + n 2 +1 ¯
לגבי כפל זה בדיוק אותו דבר.
טענה #. (4) c < ( x,y ) יציגה ב- N ע"י ϕ ( x,y,z ) ⊢ ( x<y ∧ z=1 ) ∨ ( y<x ∧ z=0 ) ∨ ( x=y ∧ z=0 ) .
הוכחה: ראשית מראים שלכל n,m ∈ N אם n<m אז N ⊢ n ¯ < m ¯ . באותו אופן אם ¬ ( n<m ) אז N ⊢ ¬ ( n ¯ < m ¯ ) . [למשל באינדוקציה על m : מ N7 אנחנו יודעים ש N ⊢ ¬ ( n<0 ) לכל n ∈ N . אז נניח שהוכחנו ל n נתון עבור m ונוכיח עבור m+1 . אז אם n<m מהנחת האינדוקציה N ⊢ n ¯ < m ¯ ולפי N8 גם N ⊢ n ¯ < m+1 ¯ =s( m ¯ ) . המקרה ההפוך דומה].
טענה #. (5) משפחת הפונקציות היציגות ב N סגורה תחת הרכבה.
הוכחה: נניח ש G( x 1 ,... x n ) יציגה ב N ו h i ( y 1 ,..., y m ) יציגות ב N ל 1 ≤ i ≤ n . עלינו להראות ש G( h 1 ( y 1 ,..., y m ),..., h n ( y 1 ,..., y m ) ) יציגה ב N . נניח ש ϕ i ( y 1 ,..., y m , z i ) מייצגות את h i ל 1 ≤ i ≤ n , ו ψ ( z 1 ,.., z n ,t ) את G . נראה ש θ ( y 1 ,..., y m ,t ): = ( ∃ z 1 ,..., z n ) ⋀ i=1 n ϕ i ( y 1 ,..., y m , z i ) ∧ ψ ( z 1 ,..., z m ,t ) מייצגת את ההרכבה. כלומר עלינו להראות שלכל p 1 ,..., p m טבעיים [ובתחום של הפונקציות h i ] מתקיים ש N ⊢ ( ∀ t )( θ ( p 1 ¯ ,..., p m ¯ ,t ) ⇐ ⇒ t=G( h 1 ( p 1 ,..., p m ),..., h n ( p 1 ,..., p m ) ¯ ) . אם נסמן q i = h i ( p 1 ,..., p m ) ו- r=G( q 1 ,..., q n ) [בהנחה שהכל מוגדר] מה שעלינו להראות זה ש N ⊢ ( ∀ t )( θ ( p 1 ,..., p m ,t ) ⇐ ⇒ t=r ) . על ידי שנחליף את t בקבוע שאינו מופיע ב N יספיק להוכיח N ⊢ θ ( p 1 ,..., p m ,t ) ⇐ ⇒ t= r ¯ . יספיק להוכיח כל כיוון בנפרד. כזכור T ⊢ ϕ → ψ ⇐ ⇒ T ∪ { ϕ } ⊢ ψ . לכן עלינו להוכיח:
  1. N ∪ { θ ( p 1 ¯ ,..., p m ¯ ,t )} ⊢ t= r ¯
  2. N ∪ {t= r ¯ } ⊢ θ ( p 1 ¯ ,..., p m ¯ ,t )
נתחיל מ2. ϕ i מייצגת את h i ו p 1 ,..., p m בתחום של h i לכן N ⊢ ( ∀ z i )( ϕ i ( p 1 ,..., p m , z i ) ⇐ ⇒ z i = q i ) . באותו אופן ψ מייצגת את G ו- q 1 ,..., q n בתחום של G לכן N ⊢ ( ∀ t )( ψ ( q 1 ,..., q m ,t ) ⇐ ⇒ t= r ¯ ) לכן N ⊢ ⋀ i=1 n ϕ i ( p 1 ¯ ,..., p m ¯ , q i ) ∧ ψ ( q 1 ¯ ,..., q n ¯ , r ¯ ) ולכן N ∪ {t = r ¯ } ⊢ ⋀ i=1 n ϕ i ( p 1 ¯ ,..., p m ¯ , q i ) ∧ ψ ( q 1 ¯ ,..., q n ¯ ,t )
נסיים עם 1. כיוון ש ϕ i מייצגות את h i אנחנו יודעים שמההנחה ϕ i ( p 1 ,..., p m , z i ) אפשר להסיק z i = q i . כלומר N ∪ θ ⊢ z i = q i . כיוון ש ψ מייצגת את G אז מ z i = q i עבור 1 ≤ i ≤ n אפשר להסיק מההנחה ψ ( z 1 ,..., z n ,t ) ש t= r ¯ . לכן N ∪ θ ⊢ t= r ¯ כנדרש.
טענה #. (6) משפחת הפונקציות היציגות ב N סגורה תחת מזעור.
הוכחה: (רעיון ההוכחה) תהי G( x 1 ,..., x n ,y ) פונקציה יציגה ע"י נוסחה ϕ ( x 1 ,..., x n ,y,t ) . תהי H( x 1 ,..., x n )= μ y ( G( x 1 ,..., x n ,y ) ) . איזו נוסחה תייצג את H ? ϕ ( x 1 ,..., x n ,y,0 ) ∧ ( ∀ y ′ <y )( ¬ ϕ ( x 1 ,..., x n , y ′ ,0 ) ) . ההוכחה שזה אכן מייצג דומה למה שעשינו עד כה.

20 הוכחת משפטי אי השלמות של גדל

תזכורת: הוכחנו אם f: N → N חשיבה (חלקית) אז f יציגה (חלש) ב N .
תרגיל (מתוך תרגיל 10): אם A ⊆ N יחס חשיב אז הוא יציג ולכן יש נוסחה ϕ (x) כך ש:
  1. N ⊢ ϕ ( n ¯ ) אם n ∈ A
  2. N ⊢ ¬ ϕ ( n ¯ ) אם n ∖ ∈ A
תזכורת: הגדרנו פונקציה g:F( L ) → N "מספור גדל" של הנוסחאות בשפה L של PA וראינו שזו פונקציה חשיבה. לשם נוחות הסימון בהינתן נוסחה ϕ ∈ F( L ) נסמן lceil ϕ rceil מספר הגדל של ϕ .
משפט #. (משפט נקודת השבת של גדל): לכל נוסחה ϕ (x) בשפה של PA קיימת נוסחה ψ כך ש- N ⊢ ϕ (lceil ψ rceil) ⇐ ⇒ ψ .
הגדרה #. תהי Δ : F 1 ( L ) → F 0 ( L ) (נוסחאות עם משתנה חופשי אחד לנוסחאות ללא משתנים חופשיים) הפונקציה המקיימת ϕ (x) mapstochar → ϕ (lceil ϕ rceil) . אז Δ נקראת פונקציית האלכסון.
קל להשתכנע ש- Δ ניתנת לחישוב ע"י מכונת טיורינג. לכן הפונקציה הבאה חשיבה: Δ ˜ : N → N המוגדרת ע"י n ∈ Dom( Δ ) ˜ אם ורק אם n מספר גדל של נוסחה במשתנה חופשי אחד, ואם n ∈ Dom( Δ ) ˜ אז n=lceil ϕ (x) rceil ו Δ ˜ (n)=lceil Δ ( ϕ ) rceil . לכן היחס Δ ˜ ( n,m ) המוגדר ע"י n ∈ Dom( Δ ˜ ) ו- Δ ˜ (n)=m הוא יחס חשיב. לכן Δ ˜ ( x,y ) יציג ב N . לפי התרגיל יש נוסחה δ ( x,y ) כך ש- N ⊢ δ ( n ¯ , m ¯ ) אם ( n,m ) ∈ Δ ˜ ו- N ⊢ ¬ δ ( n ¯ , m ¯ ) אם ( n,m ) ∖ ∈ Δ ˜ .
תהי χ x =( ∃ y )( δ ( x,y ) ∧ ϕ (y) ) . יהי ψ = Δ ( χ )= χ (lceil χ rceil) .
טענה #. N ⊢ ϕ (lceil ψ rceil) ⇐ ⇒ ψ .
הוכחה: נניח ש- N ⊢ ψ . צריך להראות ש- N ⊢ ϕ (lceil ψ rceil) . אבל ψ :=( ∃ y )( δ ( lceil χ rceil,y ) ∧ ϕ (y) ) . נזכור ש lceil χ rceil מספר גדל של נוסחה במשתנה אחד. בנוסף, δ ( x,y ) היא יצוג של היחס Δ ˜ ( x,y ) . לכן N ⊢ δ ( lceil χ rceil,y ) אם ורק אם y=lceil Δ ( χ ) rceil . לכן אם N ⊢ ( ∃ y )( δ ( lceil χ rceil,y ) ∧ ϕ (y) ) המועמד היחיד שיכול להעיד על כך הוא lceil ψ rceil=lceil Δ ( χ ) rceil . לכן N ⊢ ϕ (lceil ψ rceil) . בכיוון השני, נניח ש N ⊢ ϕ (lceil ψ rceil) ועלינו להוכיח N ⊢ ψ . עלינו להראות ש- N ⊢ ( ∃ y )( δ ( lceil χ rceil,y ) ∧ ϕ (y) ) . יספיק להוכיח ש- N ⊢ δ ( lceil χ rceil, y 0 ) ∧ ϕ ( y 0 ) עבור y 0 כלשהו. אבל N ⊢ δ ( lceil χ rceil,lceil ψ rceil ) - כי δ ( x,y ) מייצגת את Δ ˜ ומהנתון N ⊢ ϕ (lceil ψ rceil) . נשים y 0 =lceil ψ rceil וגמרנו.
משפט #. (משפט השלמות הראשון של גדל) תהי T ⊇ N תורה חשיבה ו- ω -שלמה , אז T אינה שלמה.
הגדרה #. תורה T נקראת ω -שלמה אם T ⊢ ( ∃ x ) ϕ (x) לאיזה נוסחה ϕ (x) גורר ש T ⊢ ϕ ( n ¯ ) לאיזה n ∈ N .
הגדרה #. נוסחה Pr(x) נקראת יחס יכיחות אם היא מקיימת את התכונות הבאות:
  1. אם T ⊢ φ אז T ⊢ Pr(lceil φ rceil)
  2. אם T ⊢ Pr(lceil φ rceil) אז T ⊢ Pr(lceil Pr(lceil φ rceil) rceil) .
  3. אם T ⊢ Pr(lceil φ → ψ rceil) אז T ⊢ Pr(lceil φ rceil) ⇐ ⇒ Pr(lceil ψ rceil) .
טענה #. ב N יש יחס יכיחות ואם מניחים ש N היא ω -שלמה אז בנוסף מתקיים: אם N ⊢ Pr(lceil φ rceil) אז N ⊢ φ .
הוכחה: נגדיר יחס דו מקומי Pr ˜ ( x,y ) כך ש ( n,m ) ∈ Pr ˜ אם:
  1. n מספר גדל של נוסחה ϕ , ו-
  2. n מקודד הוכחה של ϕ מתוך N .
אז Pr ˜ יחס חשיב. לכן יש נוסחה Pr( x,y ) שמייצגת את Pr ˜ . כלומר N ⊢ Pr( n ¯ , m ¯ ) אם ( n,m ) ∈ Pr ˜ ומוכיח את השלילה - אחרת.
נגדיר Pr(x):=( ∃ y )Pr( x,y ) . מדוע, למשל N ⊢ φ אז N ⊢ Pr(lceil φ rceil) ? משום שאם N ⊢ φ אז יש הוכחה של φ מ N ויהי m קידוד של ההוכחה הזו. אז Pr ˜ ( lceil φ rceil,m ) . בגלל ש Pr( x,y ) מייצגת את Pr ˜ אז N ⊢ Pr( lceil φ rceil,m ) לכן N ⊢ ( ∃ y )Pr( lceil φ rceil,y ) . 2 נובע מ-1, ו-3 הוכח באופן דומה (תרגיל).
כדי לקבל את 4: אם N ⊢ Pr(lceil φ rceil) ו- N ω -שלמה אז N ⊢ Pr( lceil φ rceil, m ¯ ) לאיזה m ∈ N . אבל אז מהגדרת היציגות N | = Pr ˜ ( lceil φ rceil,m ) כלומר m מקודד הוכחה של φ מ N .
 
הוכחה: (למשפט השלמות הראשון של גדל) לפי משפט נקודת השבת יש φ כך ש T ⊢ ψ ⇐ ⇒ ¬ Pr( ψ ) .
סימון: תהי T תורה חשיבה. נגדיר Co n T := ¬ Pr( 0 ¯ = 1 ¯ ) .
משפט #. (משפט אי השלמות השני של גדל) אם T ⊇ N חשיבה ועקבית אז T ∖ ⊢ Co n T . במילים אחרות T עקבית לא יודעת את זה על עצמה.
הוכחה: נבחר ψ כמו בהוכחת המשפט הראשון. T ⊢ ψ ⇐ ⇒ ¬ Pr(lceil ψ rceil) . אז:
  1. T ⊢ Pr(lceil ψ rceil) → ¬ ψ . מ-2 ומ-3 נקבל:
  2. T ⊢ Pr(lceil Pr(lceil ψ rceil) rceil) → Pr(lceil ¬ ψ rceil)
  3. לפי 2 T ⊢ Pr(lceil ψ rceil) → Pr(lceil Pr(lceil ψ rceil) rceil) .
  4. מ-2 ו-3 ביחד נקבל T ⊢ Pr(lceil ψ rceil) → Pr(lceil ¬ ψ rceil) .
אבל ψ → ( ¬ ψ → 0 ¯ = 1 ¯ ) היא אקסיומה לוגית (ואפילו טאוטולוגיה). לכן T ⊢ ψ → ( ¬ ψ → 0 ¯ = 1 ¯ ) . לפי 1 ו-3 מקבלים: T ⊢ Pr(lceil ψ rceil) → ( Pr(lceil ¬ ψ rceil) → Pr(lceil 0 ¯ = 1 ¯ rceil) ) לפי כלל 4 וכלל הניתוק T ⊢ Pr( ψ ) → ¬ Co n T כלומר T ⊢ Co n T → ¬ Pr(lceil ψ rceil) אבל לפי בחירת ψ , אם מניחים ש T ⊢ Co n T אז מכלל הניתוק T ⊢ ¬ Pr( ψ ) ולכן T ⊢ ψ . אבל לפי 1 זה גורר T ⊢ Pr(lceil ψ rceil) - סתירה.

21 תורת רקורסיה

תהי H: N → N . פונקציה חלקית. מכונת טיורינג עם אוב (אורקל) עבור H זו מכונת טיורינג רגילה שלה פקודה נוספת: "חשב את הערך של H עבור n כלשהו". ואז הערך של H(n) מוחזר אם n ∈ Dom(H) ואחרת האוב אינו מחזיר תשובה, והחישוב של המכונה אינו מסתיים.
למשל, נוסיף למכונת טיורינג רגילה עוד סרט והפקודה "קרא מן האוב" תתפרש כ-"חשב את H עבור הערך שכתוב בסרט בתא מספר 2". מה שחשוב הוא שמ"ט עם אוב H ניתנת לתיאור סופי. לכן בהינתן אוב H אפשר לקודד את כל מ"ט עם אוב H בדומה לקידוד של מ"ט רגילות.
המושגים:
  1. מצב של מכונה עם אוב H
  2. ריצה של מכונה עם אוב H
  3. ריצה מסתיימת
  4. f T n ( x ‾ )
כולם מוגדרים באופן זהה להגדרה הרגילה.
פונקציה f: N → N תקרא חשיבה עם אוב H אם קיימת מ"ט T עם אוב H כך ש f= f T 1
הגדרה #.  
  1. יהיו H,G אובות. נאמר ש H ≤ R G אם כל פונקציה חשיבה מ H חשיבה מ G .
  2. נאמר ש H ∼ R G אם H ≤ R G ו- G ≤ R H .
טענה #. ∼ R הוא יחס שקילות.
הוכחה: צריך להראות רק שאם H ≤ R G ≤ R F אז H ≤ R F . נניח ש f חשיבה מ H . עלינו להראות ש f חשיבה מ F . מהנחתנו f חשיבה מ G , אבל אז גם f חשיבה מ F .
הגדרה #.  
  1. דרגת טיורינג של H הינה deg(H)=H / ∼ R =[H ] ∼ R .
  2. אם a,b דרגות אז נאמר ש a ≤ R b אם לכל H,G כך ש deg(H)=a,deg(G)=b מתקיים H ≤ R G . [הערה: בהגדרה אפשר להחליף "לכל" ב"קיים"].
ברור ש ≤ R הוא יחס סדר חלקי על הדרגות. מטרה ראשונה לחקור את המבנה של הקבוצה סדורה חלקית של דרגות טיורינג.
תכונות בסיסיות של הדרגות:
  1. אם F חשיבה אז deg(F) ≤ R deg(G) לכל G .
  2. בפרט:
    1. אם F,G חשיבות אז F ∼ R G
    2. אם נסמן 0=degF ל F חשיבה אז 0 ≤ R a לכל דרגה a .
  3. אם a 1 ,..., a n דרגות כלשהן אז יש להן חסם מלעיל משותף קטן ביותר.
    הוכחה: יהיו F 1 ,..., F n כך ש deg F i = a i . ברור שכל H המקיימת F i ≤ R H לכל i מחשבת את F 1 ,..., F n . לכן אם נקח בתור אוב את H ˜ ={ F 1 ,..., F n } ( n -אובות) נקבל ש F i ≤ R H ˜ לכל i ומזערי כזה. עכשיו פשוט נחליף את H ˜ ב- H הפועלת באופן הבא: H(m)= F P r L (m) ( P r R (m) ) . H חשיבה מ H ˜ ולכן H ˜ היא החסם המבוקש.
  4. נאמר שסדרת פונקציות { F n } n ∈ N היא חשיבה מ H אם הפונקציה F( n,x )= F n (x) חשיבה מ H . ברור שאם { F n } n ∈ N סדרת פונקציות אז { F n } n ∈ N חשיבה מ F( n,x ) . לכן לכל סדרת פונקציות יש חסם מלעיל. אזהרה: אבל זה לא נכון שלכל סדרת פונקציות יש חסם עליון.
הגדרה #. נאמר ש H נל"ח ב G (ונרשום H ≤ RE G ) אם Dom(f)=H לאיזו f ≤ R G .
בדיוק כמו במקרה של פונקציות חשיבות לכל G יש H ≤ RE G כך ש H ∖ ≤ R G .
בהינתן G(x) נסמן ב G * ( e,x ) זו מכונת טיורינג אשר (עם אוב G ) אשר בהינתן e קוד של מ"ט עם אוב G וקלט x מחשבת את T e (x) . ברור ישירות מההגדרה ש:
  1. אם H ≤ RE G אז H ≤ R G *
  2. G * ≤ RE G .
מדוע?
  1. אם H ≤ RE G אז יש f ≤ R G כך ש H=Im(f) ו- f שלמה. אז H=Im( G * ( e f ,x ) ) כאשר על הקוד של f . וברור ש G * ( e f ,x ) ≤ R G * .
  2. ברור - כי G * חשיבה מ G ולכן הגרף שלה נל"ח מ G .
הגדרה #. אם a דרגה ו- a=degH אז הקפיצה של a היא deg H * ומסומנת a ′ .
שאלה: האם זה מוגדר היטב? אם H ∼ G האם H * ∼ G * ? מתקיים: G * ≤ RE G ⇒ H ∼ G G * ≤ RE H לכן יספיק להראות ש G * נל"ח מירבית מ H . לפי הטענה הקודמת עבור H, H * יוצא ש G * ≤ R H * . מסימטריה בין H ו- G גם H * ≤ R G * ולכן זה מוגדר היטב.
שאלה: האם קיימת דרגה 0<a כך ש a ′ = 0 ′ ? תשובה: כן!

22 תורת רקורסיה - המשך

תזכורת: אם F,G פונקציות (מהטבעיים לטבעיים) אז F ≤ R G אם כל פונקציה חשיבה מ F חשיבה מ G . F ∼ R G אם F ≤ R G ו- G ≤ R F . כמו כן נסמן F / ∼ =degF .
אם a,b דרגות אז a ≤ b אם קיימות פונקציות F,G כך ש degF=a,degG=b ו- F ≤ R G . אמרנו: אפשר להחליף את "קיימות F,G " ב"לכל F,G ".
מתי נאמר ש F ≤ RE G ? אם a,b דרגות אז נגדיר a ≤ RE b בדיוק אם קיימות F,G כך ש degF=a,degG=b ו- F ≤ RE G . תרגיל: A ⊆ N חשיבה ב G אם ורק אם A נל"ח מ G ו- N \ A נל"ח מ G .
אם H פונקציה כלשהי אז H * היא הפונקציה המתאימה למכונת טיורינג אוניברסלית עם אוב H . באופן פורמלי: H * היא הפונקציה המציינת של הקבוצה: {langle e,n rangle:eisacodeformachineHand T e (n)halts} ישירות מן ההגדרה נובע שאם G ≤ RE H אז degG ≤ deg H * . כמסקנה: אם נגדיר לדרגה a את הדרגה a ′ ע"י a ′ =deg H * עבור H כלשהי כך ש a=degH אז:
  1. a ′ מוגדר היטב
  2. a ′ הוא הדרגה המירבית מעל a שהיא נל"ח ב a . במילים אחרות, אם a ≤ b ו- b ≤ RE a אז b ≤ a ′ . מדוע? אם b ≤ RE a אז לפי הגדרה יש G כך ש degG=b ו- G ≤ RE H . לכן degG ≤ deg H * = def a ′ .
ראינו: אם F,G חשיבות אז F ∼ G וסימנו degF=0 :
  1. 0 ≤ a לכל דרגה a
  2. אם a,b דרגות אז יש דרגה c כך ש- c חסם מלעיל קטן ביותר ל a,b .
  3. לכל סדרה F( y,x ):={ F n } n=1 ∞ יש חסם מלעיל (שהוא פשוט F( y,x ) ) אבל אין חסם עליון.
תרגיל: אם a,b דרגות אז a< a ′ (ללא שיוויון) ואם a ≤ b אז a ′ ≤ b ′ . אבל בהמשך נראה שיש a<b כך ש a ′ = b ′ .
משפט #. קיימות דרגות a,b ≤ 0 ′ שאינן ניתנות להשוואה.
מסקנה #. קיימת דרגה 0<a< 0 ′ .
הוכחה: לפי המשפט יש a,b ≤ 0 ′ שאינן ניתנות להשוואה. אז a,b ∖ = 0 ′ ו- a,b ∖ =0 .
שאלה מרכזית: (הבעיה של Post) האם קיימת a כנ"ל שהיא נל"ח?
אבחנה: נניח ש f חשיבה עם אוב H . אז לכל n יש σ ⊆ H פונקציה סופית (ז"א תחום של σ סופי) כך ש f(n) ניתן לחישוב מ σ .
הוכחה: (למשפט) נשים לב שגם אם האוב F אינו ידוע לנו עדיין ניתן לרשום את כל הקודים של מכונת טיורינג עם אוב F . בתור התחלה נבנה שתי פונקציות F,G כך ש- G ∖ ≤ R F וגם F ∖ ≤ R G . כדי למלא את הדרישה הזו עלינו לקיים שני אוספים של תנאים:
  1. (e1) מ"ט עם אוב G שהקוד שלה הוא e אינה מחשבת את F .
  2. (e2) מ"ט עם אוב F שהקוד שלה הוא e אינה מחשבת G .
אז תהי { e i } i=1 ∞ מניה חשיבה של התנאים הנ"ל. נבנה באופן אינדוקטיבי פונקציות סופיות F i , G i כך ש F i ⊆ F i+1 , G i ⊆ G i+1 ג לכל i ואם e i היא תנאי מסוג 1, למשל אז F i+1 תבטיח שהפונקציה המחושבת ע"י המכונה e i עם האוב G לא תחשב את F i+1 . במילים אחרות המכונה e i עם האוב G על קלט מסויים n אז תתן ערך ששונה מ F i+1 (n) . נניח שהגדרנו F i , G i כך ש F i-1 ⊆ F i ו- G i-1 = G i ונניח שבה"כ e i הוא תנאי מסוג 1 (התפקידים של F,G סימטריים לחלוטין בהוכחה). יהי n i ∈ N הקטן ביותר כך ש n i ∖ ∈ dom( F i ) . נבחים בין שני מקרים:
  1. מקרה א' - קיימת פונקציה סופית σ כך ש:
    1. σ מתיישבת עם G i (כלומר אם x ∈ dom( σ ) ∩ dom( G i ) אז σ (x)= G i (x) )
    2. מ"ט e i עם אוב σ עוצרת על הקלט n i .
    במקרה זה, נגדיר G i ⊆ G i+1 עם G i+1 = G i ∪ σ . בגלל הנחה (1) - זוהי פונקציה. נגדיר T e i σ ( n i )+1= F i+1 ( n i ) (כאשר T e i σ הוא הערך שמ"ט e i עם אוב σ מחזירה עבור n i ) וזה מוגדר בגלל הנחה (2).
  2. מקרה ב' - לא מקרה א'. אז נגדיר G i+1 = G i , F i+1 ( n i )=0 . עתה נגדיר > F= ⋃ i=1 ∞ F i ,G= ⋃ i=1 ∞ G i . נראה ש F ∖ ≤ R G (המקרה השני סימטרי לחלוטין). תהי e מ"ט כלשהי עם אוב G . נראה ש e אינה מחשבת את F . לשם כך יספיק למצוא n ∈ N כלשהו כך ש F(n) ∖ = T e G (n) [נשים לב ש F(n) מוגדרת לכל n , פשוט משום שהבניה מבטיחה שנטפל בבניה של F אינסוף פעמים ובכל פעם אנחנו מגדירים את F i+1 ( n i ) עבור n i קטן ביותר עבורו הפונקציה טרם הוגדרה. לכן בהכרח dom(F)= N ]. בפרט, אם T e G (n) לא עוצרת, נקבל את הדרישה.
יש שלב i שבו טיפלנו במכונה e . יש שתי אפשרויות. אם היינו במקרה ב' אז T e i G ( n i ) אינה עוצרת. אילו הייתה עוצרת, לפי האבחנה שרשמנו היה σ ⊆ G סופי כך ש T e i σ ( n i ) עוצרת, ומכיוון של G i ול σ הרחבה משותפת G הן מתיישבות בסתירה להנחה שאנחנו במקרה ב'. אם היינו במקרה א' אז יש σ i ⊆ G סופית (שהיא זאת שמופיעה בבניה בשלב ה i ) כך ש F(n)= F i+1 ( n i )= T e i σ ( n i )+1 ∖ = T e i σ ( n i )= T e i G ( n i ) .
מסקנה #. degG אינו ניתן להשוואה עם degF . נותר להראות degF ≤ 0 ′ .

23 תורת רקורסיה - המשך

התחלנו להוכיח: קיימות דרגות 0 ≤ a,b ≤ 0 ′ כך ש- a,b אינן ניתנות להשוואה ונסמן a|b . בנינו שתי פונקציות F,G כך ש- F ∖ ≤ R G ו- G ∖ ≤ R F . נותר לבדוק ש- degF,degG ≤ 0 ′ . כדי להבטיח שהפונקציות בלתי ניתנות להשוואה היה צריך להגשים שני סוגי תנאים:
  1. (e1) F ∖ = f T e G
  2. (e2) G ∖ = f T e F
למה #. (למת השימוש) תהי e מ"ט ו- H,G אובות. נניח שבריצה של T e H (n) הפניות לאורקל H מבקשות בדיוק את הערכים H( r 1 ),...,H( r k ) לאיזה k ∈ N ונניח ש- G( r i )=H( r i ) לכל 1 ≤ i ≤ k . אז T e H (n)= T e G (n) . בפרט: אם T e H (n) עוצרת אז יש σ ⊆ H סופית כך ש- T e H (n)= T e σ (n) .
כדי לבנות את F,G מספרנו את התנאים { e i } i=0 ∞ בצורה חשיבה. אם בשלב n עלינו לטפל בתנאי מסוג e1 אז נבחר k להיות הראשון שאינו ב dom F n ונבחין בין שני מקרים.
  1. מקרה א' - אם קיימת σ סופית כך ש:
    1. σ מתיישבת עם G n ו-
    2. T e σ (k) עוצרת
    אז נגדיר G n+1 = G n ∪ σ ו- F n+1 = F n ∪ {(k, σ } כאשר r= f T e σ (k)+1 .
  2. מקרה ב' - אחרת (כלומר, אין σ כנ"ל) נגדיר F n+1 (k)=0, G n+1 = G n . אז ראינו ש- F ∖ ≤ R G ו- G ∖ ≤ R F כאשר > F= ⋃ i=0 ∞ F i ו- > G= ⋃ i=0 ∞ G i . נותר לבדוק ש- degG,degF ≤ 0 ′ . כלומר עלינו להראות שיש אוב נל"ח שממנו F,G חשיבות. משיקולי סימטריה יספיק לבדוק שזה נכון עבור F .
נגדיר פונקציה s: N → N שהיא הבניה: כלומר s(n) מחזיר לנו קוד עבור langle F n , G n , e n rangle . יספיק לוודא ש- s חשיבה מאיזה אוב נל"ח. נניח שאנחנו יודעים את s(n) ואנחנו רוצים לחשב את s( n+1 ) . ב.ה.כ השלב e n+1 הוא מסוג e1 . דבר ראשון s צריכה להכריע אם אנחנו במקרה א' או מקרה ב'. ז"א עלינו לדעת להכריע אם קיימת σ שמתיישבת עם G n ו- T e+1 σ (k) עוצרת (מיהו k ידוע מ s(n) ). דבר ראשון נשים לב שהתנאי בתוך הסוגריים הוא נל"ח [ב σ , אבל מכיוון ש σ סופית אז היא ממש נל"ח]. אבל לכל יחס נל"ח A( x ‾ , y ‾ ) אז גם ( ∃ x )A( x ‾ , y ‾ ) נל"ח. לכן ההכרעה האם אנחנו במקרה א' או במקרה ב' חשיבה מאוב נל"ח. אם נחנו במקרה ב' - אין בעיה, הכל חשיב. אם אנחנו במקרה א' - עלינו למצוא את σ . זה שוב דבר שהוא חשיב באופן כללי, כי אם A( x ‾ , y ‾ ) נל"ח ו- y ‾ כזה ש- ( ∃ x )A( x ‾ , y ‾ ) אז יש פונקציה חשיבה שמחזירה x ‾ שמעיד על כך. לכן בסה"כ s( n+1 ) חשיבה מ s(n) בעזרת האוב הנל"ח ( ∃ σ )(...) .
מסקנה #. קיימת 0<a< 0 ′ .
אותה הוכחה בדיוק תראה: לכל דרגה c קיימת דרגה a כך ש c<a< c ′ .
האם אפשר למצוא a כמו במסקנה שהיא נל"ח? תשובה: כן. ואפשר אפילו לדרוש ש- a ′ = 0 ′ .
משפט #. קיימת דרגת טיורינג נל"ח a כך ש- a ∖ =0 ו- a ′ = 0 ′ .
הוכחה: (רעיון) נבנה קבוצה A ⊆ N באינדוקציה. בכל שלב n נוסיף לקבוצה שבנינו בשלבים הקודמים מספר של איברים. הבניה תהיה כזו שלגבי כל איבר שהכנסנו ל- A אנחנו מתחייבים שהוא יישאר ב- A . אבל באופן כללי בשום שלב סופי לא נתחייב לגבי שום מספר טבעי שהוא לא ייכנס ל- A מתישהו בעתיד. לפי מה אנחנו מחליטים האם להכניס איבר ל- A או לא (שזה דבר שלא יקרה)? כדי להבטיח את התנאים נרצה לוודא שהקבוצה A שאנחנו בונים אינה חשיבה. לכן נרצה להבטיח ש- χ A שונה מ χ E לכל קבוצה חשיבה E .
הצרה היא שאנחנו לא יכולים להתמקד בפונקציות מציינות של קבוצות חשיבות. צריך לעבור על כל הפונקציות החשיבות - ובכלל זה אלו שאינן שלמות. מתי נכניס איבר k ל- A ? לכל מ"ט T e נתאים מספר טבעי k(e) ונריץ את T e ( k(e) ) . אם נקבל 0 עולה החשד ש T e פונקציה מציינת של איזו קבוצה ו- T e חושבת ש- k(e) לא בקבוצה. ליתר בטחון, נכניס את k(e) ל- A וזה יבטיח ש A שונה מהקבוצה ש- T e (אולי) מקודדת. הקושי העיקרי - כיצד נדע אם T e ( k(e) ) אי פעם תעצור?
כדי להבטיח ש- A שנבנה תהיה נל"ח נרצה לוודא שהבניה שאנחנו מנהלים היא חשיבה. לכן שאלות מהסוג "האם T e ( k(e) ) עוצרת" אינן באות בחשבון. מה הפתרון? נשים לב שאם T e ( k(e) ) אינה עוצרת ומחזירה 0, לא יקרה שום דבר רע אם אף פעם לא נחליט להכניס את k(e) ל- A כי בסוף פשוט k(e) לא יהיה ב A ואנחנו בסדר. השאלה היא איך לא לתקוע את הבניה אם T e ( k(e) ) לא עוצרת. כמו תמיד, נדאג לחזור ל e אינסוף פעמים ובכל פעם לבצע מספר חסום (אבל עולה לאינסוף) של צעדים. אם אי פעם T e ( k(e) ) תעצור נדע אם עצרה על 0 או לא - אם כן נכניס את k(e) ואם לא - לא נעשה כלום. בדיוק כמו במקרה שבו T e ( k(e) ) בכלל לא עוצרת.
הדרישה השניה, ש- (degA ) ′ = 0 ′ מצריכה אותנו לטפל בעוד משפחה של תנאים: ( 2 e,k ) - צריך להחליט האם T e A (k) עוצרת או לא. נניח שרוצים לטפל בתנאים אלה. רוצים לדעת האם T e A (k) עוצרת או לא. אבל איפה A ואיפה אנחנו?? (אליבא ד'חסון). בשלב סופי התחייבנו רק לגבי מספר סופי של A i שהם ב A . ננסה לחשב את T e A (k) - את זה גם כן אי אפשר לחשב. את זה נפתור כמו קודם. נטפל בתנאי 2 e,k אינסוף פעמים וכל פעם נריץ את המכונה עוד קצת. כל זה יעזור בכלל במשהו אם בסוף, לגבי כל r שעליו T e A (k) שאלה האם r ∈ A i נקבל בדיוק את אותה התשובה גם ב A (או לחלופין בכל שלב בעתיד בו נחזור לטפל ב ( 2 e,k ) .
המכונה שואלת את האוב A i שאלות מהצורה "האם r ∈ A i ?" או "האם r ∖ ∈ A i ?". מהבניה - אם T e A i שאלה "האם r ∈ A i ?" וקיבלה תשובה חיובית אז היא תמיד תקבל תשובה חיובית לכל A j עם i ≤ j . לכן התשובות היחידות שיכולות להשתנות הן תשובות ש A i חושב ש r ∖ ∈ A i . ל r יש שימוש שלילי בריצה של T e A i אם T e A i פונה לאוב בשאלה "האם r ∈ A i ?" ומקבלת תשובה r ∖ ∈ A i . לכל חישוב של ריצה עבור T e A i [במילים אחרות, לכל טיפול בתנאי 2 e,k ] נצוות רשימה N e,k של כל ה r ∈ N בהם נעשה שימוש שלילי בזמן הריצה.
כל עוד N e,k ∧ A j = ∅ - אנחנו בסדר. מה שנרצה הוא להשתדל שלא להכניס איברים מ- N e,k ל- A . אבל מה נעשה אם פתאום תנאי מסוג 1 מחליט שהוא רוצה להכניס ל- A איבר ששייך לאיזה N e,k ? נחליט על סדר קדימויות. נמספר את כל התנאים שלנו (כמו בהוכחת המשפט הקודם) ונרשה לתנאי מסוג 1 e לפצוע קבוצה מסוג N e,k רק אם המספר הסידורי של 1 e קטן מזה של 2 e,k .

24 תורת רקורסיה - המשך

(המשך רעיון ההוכחה משיעור שעבר)
טענה #. הקבוצה A שנקבל בסוף הבניה עונה על כל התנאים 1 e , 2 e,k .
הוכחה: נניח שיש לנו תנאי 1 e i . אם בשלב כלשהו הכנסו ל- A מספר k מ- R i זה אומר שמצאנו ש- T e i (k)=0 והכנסנו את k ל- A ולכן χ A (k)=1 ואנחנו בסדר.
אז נניח שאין k ∈ R i שהוכנס ל- A . נבחר k ∈ R i גדול מספיק כדי ש- k אינו מופיע באף 2 e,k - הכרזה עם אינדקס קטן מהאינדקס של 1 ei .
מדוע יש k כזה? נשים לב שאם n הוא האינדקס של 2 e,l אז כל תנאי עם אינדקס m<n יכול "לפצוע" הכרזה של n לכל היותר פעם אחת. אם התנאי עם אינדקס n פצע הכרזה כלשהי ז"א שהתנאי הכניס איבר כלשהו ל- A ולפי (1) של מקרה א' לעולם לא נחזור לטפל בתנאי עם אינדקס n . בסה"כ את ה- 2 e,l הכרזות ניתן "לפצוע" לכל היותר n פעמים. לכן יש לכל היותר n+1 הכרזות 2 e,l . בסה"כ לכל תנאי שהוא יש לכל היותר מספר סופי של הכרזות של תנאים עם אינדקס קטן יותר. לכן יש k כמו שאנחנו רוצים ועבור k כזה לא ייתכן ש- T e i (k)=0 . מדוע? אילו זה היה מתקיים לפי מקרה (א'2) היינו מכניסים את k ל- A בסתירה להנחה. לכן על התנאים 1 e מתקיימים.
מה בקשר לתנאים 2 e,k ? נאמר ש- 2 e,k הכרזה היא קבועה אם היא זרה ל- A . נראה ש- T e A (k) עוצרת אם ורק אם קיימת 2 e,k הכרזה קבועה.
אם קיימת 2 e,k הכרזה קבועה ז"א שקיים איזה שלב n בבניה שבו T e A n-1 עצרה (אחרי n צעדים) ויצרה את ההכרזה. כיוון שההכרזה קבועה, לכל r ∈ N כך ש- T e A n-1 פנתה לאוב בשאלה "האם r ∈ A n-1 ?" האוב A יחזיר את אותה התשובה. לכן לפי עקרון השימוש T e A (k) עוצרת.
בכיוון השני אם T e A (k) עוצרת (נאמר אחרי n צעדים) אז לכל c i כך שהתנאי ב- c i הוא 2 e,k ו- i>n , הבניה במקרה ב' תייצר 2 e,k - הכרזה. (ובתנאי שבשלב ה- i כבר נכנסו ל- A כל האיברים שבהם נעשה שימוש חיובי בחישוב של T e A (k) .
אבל מהדיון הקודם, כל תנאי יכול לייצר לכל היותר מספר סופי של הכרזות. אז האחרונה מביניהן שהכרח לא תשתנה, ז"א תהיה קבועה.
עד עתה: בנינו את A , הראנו ש- A מקיימת את התנאים 1 e ואת 2 e,k (לפי א' הנ"ל) וברור שהבניה חשיבה. כיוון ש- A מקיימת את 1 e לכל e , ברור ש- A אינה חשיבה. כיוון שהבניה חשיבה, אם נגדיר s(n) להיות הקבוצה A n שהתקבלה בשלב ה- n של הבנייה נקבל ש- A נל"ח, כי s(n) חשיבה.
נותר לוודא ש- deg( A * ) ≤ 0 . ראינו בתרגיל 11 טענה שאומרת שאם A * =dim( B i ) עבור i ∈ N כך ש- B i חשיבה מ- A אז deg( A * ) ≤ 0 ′ . נגדיר langle e,k rangle ∈ B i אם ורק אם בשלב ה- i של הבנייה יש 2 e,k - הכרזה שאיננה פצועה. כיוון שהבניה חשיבה B i יחס חשיב. לפי (א) הנ"ל T e A (k)( ⇐ ⇒ langle e,k rangle ∈ B i ) עוצרת אם ורק אם dim χ B i (langle e,k rangle)=1 .
משפט #. לכל דרגה 0 ′ ≤ a קיימת דרגה b כך ש- b ′ = 0 ′ ∪ b=a .
רעיון ההוכחה: נבחר g: N → N כך ש- deg(g)=a , אפשר לבחור g כזו שלמה. נרצה לבנות f: N → N כך ש- f * חשיבה מ- 0 ′ ∪ deg(f) ו- g חשיבה מ- f * .
נרצה להגשים שני סוגים תנאים:
כרגיל נמספר את התנאים { c i } , ובשלב ה- i אם אנו בתנאי 1 e,k ויש σ : N → N סופית שמתיישבת עם f i-1 כך ש- T e σ (k) עוצרת, נגדיר f i = f i-1 ∪ σ ואחרת נגדיר f i = f i-1 . ואם בשלב ה- i אנו בתנאי 2 n אז נבחר m מזערי כך שאינו בתחום של f i-1 ונגדיר f i (m)=g(n) . לסיכום: יוצא שהבניה חשיבה מ- 0 ′ ∪ a=a וחשיבה גם מ- 0 ′ ∪ b .
 
הוכחה: תהי g כנ"ל ונמצא פונקציה f כך ש- deg(f) תענה על הדרישות.
b ∪ b ′ ≤ b ′ ולכן יספיק למצוא b כך ש- b ′ ≤ a ≤ b . מזה נבטיח שיש שיוויונות לכל אורך הדרך. אז צריך למצוא b כך ש- b ′ חשיבה מ- b ומ- 0 ′ .
כרגיל נמספר את התנאים (כולם ביחד) במספור חשיב { e i } i=0 ∞ ונניח שלכל i ≤ n בנינו פונקציה f i (עם תחום סופי) כך ש- f i ⊆ f j אם i ≤ j .
בניית f n+1 :
כדי לממש את הבניה:
נשאר להראות כי את b ′ ניתן לחשב מ- b ומ- 0 ′ אבל b ′ =deg( f * ) ו- f * זהו האוב שעונה לכל שאלה מהצורה "האם T e f (k) עוצרת?". ראשית אם אנו יודעים את הבניה של t אז אנו יודעים לענות על כל השאלות מהצורה הנ"ל. אבל הבניה חשיבה גם מ- 0 ′ וגם מ- b ′ (ביחד) ולכן b ′ ≤ b ∪ 0 ′ כנדרש.
מסקנה #. הפונקציה a → a ′ איננה חח"ע.