משפט רייס

[guyTHEred]

משפט רייס

מישהו יודע מה זה אומר? ויכול לתת לי לינק טוב לקרוא הסבר על זה? תודה מראש

 

[xxxy1]

גוגל יודע הכל

 

[alexrait1]

בטח שיודעים

משפט רייס זה משפט מתורת החישוביות, לפי מה שאני זוכר זה בערך כך: נחלק את קבוצת הפונקציות שניתנות לחישוב לשניים :F1,F2. הקבצות האלו יהיו זרות מצד אחד ולא ריקות מצד שני. אז אם נותנים לנו קידוד של מכונה <M> לא ניתן להכריע את הפוקנציה שM שייכת לקבוצה האחת או השניה. קוראים לזה הניסוח הפונקציונלי של משפט רייס. הניסוח השני די דומה אבל במושגים קצת אחרים.

 

[alexrait1]

הכוונה

לא ניתן להריע לאיזה מהקבוצות הפונקציה ש M מחשבת שייכת.

 

[עידו123456]

משפט רייס:

נקרא ל - C תת קבוצה של RE תכונה של שפה ב RE. תכונה של שפה תקרא לא טרוויאלית אם C שונה מ RE (הכלה ממש) ואם C אינו הקבוצה הריקה. משפט רייס: כל תכונה לא טריוויאלית של שפות ב RE הינה לא כריעה. כלומר - אם C לא טריוויאלית אזי Lc = {<M> | L(M) belongs to C} does not belong to R