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

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