תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרות: ניווט |
|||
שורה 97:
מושג הקונפיגורציה יאפשר לנו לטעון ולהוכיח (באופן פורמלי) נכונות של טענות לגבי
ההוכחה מתבצעת באינדוקציה על אורך הקלט m. נניח כי סדרת החישוב היא <math>C_0\vdash C_1\vdash \cdots C_{m+1}</math> ומתקיים:{{ש}}
<math>C_0=(x,q_0,1)</math>{{ש}}
|