תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף

כעת נניח שיש לנו מערכת הוכחה F "חזקה דיו" במובן שניתן לתאר בה טענות לגבי מכונות טיורינג. בפרט, נניח שניתן לתאר בה את תהליך החישוב של מכונת טיורינג, ולנסח טענות שאומרות "המכונה M עוצרת".{{תזכורת|המערכת שאנו משתמשים בה ביום יום (באופן מובלע) נקראת [[w:ZFC|ZFC]], והיא חזקה דיו לתאר מ״ט. למשל טענה לגבי עצירה של מכונה M תהיה בסגנון הבא: קיימת סדרה <math>C_1, C_2, \ldots, C_n</math> כך שמתקיים (1) <math>C_1</math> היא קונפיגורציה תחילתית של M (על קלט ריק); (2) לכל <math>i>1</math> הקונפיגורציה <math>C_i</math> היא הקונפיגורציה העוקבת של <math>C_{i-1}</math>; (3) <math>C_n</math> היא קונפיגורציה סופית}}