בהוכחת משפט קוק-לוין שראינו בשיעור, ייצגנו ריצה של מכונה M על קלט (x,w) על ידי טבלה T M,x. במהלך ההוכחה, בנינו…

בהוכחת משפט קוק-לוין שראינו בשיעור, ייצגנו ריצה של מכונה M על קלט (x,w) על ידי טבלה $T_{M,x}$. במהלך ההוכחה, בנינו טבלאות אמת עבור תאים שונים בטבלה והמרנו אותן לצורת CNF. נניח שמספר המצבים ב- M הוא 10 ושמספר התוויים בא"ב העבודה של M הוא 5. השאלה היא לגבי טבלת האמת עבור התא השמאלי ביותר בשורה השנייה (התא האחרון) של T_{M,x} (השורה שמייצגת את הקונפיגורציה הסופית של M על (x,w)). כזכור הנחנו שאם M מקבלת את (x,w) אז התא הזה מכיל (B, 1, qaccept) (כלומר התו בתא הראשון הוא B, ראש המכונה הוא על תו זה והמכונה היא במצב qaccept). מה מספר השורות בטבלת אמת זו שערכם הוא 0 (כלומר False)?