תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 117:
משמעות העקביות היא שלא ניתן להוכיח טענות "שגויות". אם ניתן להוכיח טענה וגם היפוכה, המערכת מאבדת את ההגיון שבה, כי ניתן להוכיח בעזרה ששקר(False) הוא טענת-אמת (<math>F\vdash False</math>), ומכאן ניתן להוכיח כל טענה (כי <math>False \Rightarrow S</math> הוא טענת אמת).
משמעות השלמות היא שכל טענה היא או "נכונה" או "שקרית" כלומר, ניתן
{{משפט|שם=משפט האי-שלמות הראשון של גדל|
תוכן= לכל מערכת הוכחה F חזקה דיו ועקבית, F אינה שלמה.{{רווח קשיח|5}}}}
==== הוכחת משפט גדל בעזרת משפט הרקורסיה ====
כעת נניח שיש לנו מערכת הוכחה F "חזקה דיו" במובן שניתן לתאר בה טענות לגבי מכונות טיורינג. בפרט, נניח שניתן לתאר בה את תהליך החישוב של מכונת טיורינג, ולנסח טענות שאומרות "המכונה M עוצרת".{{תזכורת|המערכת שאנו משתמשים בה ביום יום (באופן מובלע) נקראת 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> היא קונפיגורציה סופית}}
{{להשלים}}
| |||