תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←קונפיגורציה: הרחבה |
|||
שורה 93:
מושג הקונפיגורציה יאפשר לנו לטעון ולהוכיח (באופן פורמלי) נכונות של טענות לגבי מונות טיורינג. לדוגמא, נוכיח נכונות המכונה ב[[#דוגמא|דוגמא]] להזזת הקלט, כלומר נוכיח את הטענה: "לכל קלט x הפלט הוא 0x".
ההוכחה מתבצעת באינדוקציה על אורך הקלט m. נניח כי סדרת החישוב היא <math>C_0\vdash C_1\vdash \cdots C_{m+1}</math> ומתקיים:{{ש}}
<math>C_0=(x,q_0,1)</math>{{ש}}
<math>\forall 0<i\le m, C_i=(0x_1x_2..x_{i-1}x_{i+1}..x_m,mem_{x_i},i+1)</math>{{ש}}
<math>C_{m+1}=(0x_1x_2..x_m\sqcup,done,m+2)</math>{{ש}}
| |||