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

==מניה רקורסיבית של שפות בעלות תכונה==

 

 

 

{{משפט|תוכן=

בהנתן תכונה <math>S \subseteq RE</math>, אז <math>LS \in RE</math> אמ"ם מתקיימות כ"א מהתכונות הבאות:

# אם <math>L \in S</math>, אז יש ל-<math>L</math> תת-שפה סופית <math>L' \subseteq L</math> המקיימת <math>L' \in S</math>.

# שפת כל השפות הסופיות ב-<math>S</math> היא ב-<math>RE</math> (כלומר, יש מ"ט המונה כל שפה סופית ב-<math>S</math>).

שגם היא ב-<math>S</math>. שיטת הdovetailing כאן מבטיחה שהחל משלב כלשהו, <math>L'</math> תשקל על ידי <math>Q_3</math>. תנאי 3 מבטיח שבזמן סופי כלשהו, <math>Q_3</math> תזהה את <math>L'</math> כשייכת ל-<math>S</math>. שוב פעם, שיטת הdovetailing מבטיחה שלאחר מספיק איטרציות <math>Q_3</math> תפעל מספיק פעמים על <math>L'</math>. כלומר, אם התשובה חיובית, אז <math>Q</math> בוודאות תחזיר תשובה חיובית.

 

}}