ויקיפדיה

משפט רייס – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Yonidebot (שיחה | תרומות)
271,876 עריכות
מ בוט החלפות: דוגמה; על ידי ;
מ הסרת קטע לא אנציקלופדי שחוזר על משהו שכבר נאמר והוספת קטגוריה
שורה 1:
'''משפט רייס''' הוא [[משפט (מתמטיקה)|משפט]] מרכזי בתחום ה[[חישוביות]], שעוסק ביכולת של [[אלגוריתם|אלגוריתמים]] לחקור אלגוריתמים אחרים. המשפט אומר שאין [[תוכנית מחשב]] שמקבלת כקלט תוכנית מחשב אחרת, ומכריעה האם ה[[פונקציה]] שמחשבת תוכנית מחשב זו היא בעלת תכונה מסוימת "לא-טריוויאלית" או לא. (כלומר, תכונות אשר מאפיינות חלק מהפונקציות שמחושבות בידי תוכנית מחשב, אך לא את כולן) יש לשים לב שהתכונה היא תכונה של הפונקציה, ולא של תוכנית המחשב עצמה. באופן אינטואיטיבי המשפט טוען שתוכנית מחשב אינה יכולה לדעת מהכמעט תוכניתמאום מחשבעל אחרתהפלטים עושהשל (כיתוכניות אז היא הייתה צריכה להריץ אותה, וזהמחשב שקולהנתונות לבעייתלה העצירה)כקלט.
 
== הוכחת המשפט ==
שורה 27:
 
אלא שהפונקציה הריקה אינה בעלת התכונה <math>\ \overline{X}</math> (שכן הנחנו שהיא כן בעלת התכונה <math>\ X</math>) ולכן הגענו לסתירה לתוצאה שהוכחנו בסעיף הקודם - הראינו כיצד ניתן להכריע האם אלגוריתם <math>\ A</math> נתון מחשב פונקציה בעלת תכונה לא טריוויאלית שהפונקציה הריקה לא מקיימת.
==מגבלות משפט ריס ==
 
; 1) התכונות אליהם מתייחס משפט רייס הם תכונות של שפת המכונה ולא את המכונה עצמה :
===לדוגמה===
השפה L המקיימת כל המכונות m כך שקיימת מילה w כך ש m מקבלת את w תוך 100 צעדים לא שייכת לR
<br />
לא ניתן להוכיח זאת על ידי משפט ריס
 
; 2) משפט רייס אינו "אם ורק אם " , כלומר , הכיוון ההפוך לא בהכרח נכון . :
===לדוגמה===
השפה
 
<math> { m } : L(m)= </math>
<math>{ \Sigma}</math>
<sup>*</sup>
 
אינה בRE (אינה מתקבלת טיורינג )
<br />
אך לא ניתן להוכיח זאת בעזרת משפט רייס
<math>{{p=L \in RE :L= (\Sigma^*}}={{\Sigma^*}}</math>
 
<br />
<math>L_p=L_(\Sigma^*) </math> ו <math>\phi</math> לא שיך לp
<br /><br />
ובאמת לא ניתן להסיק זאת ממשפט רייס
 
==קישורים חיצוניים==
* {{גדילא מדויק|6770|על הבעיה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית}}
[[קטגוריה:מדעי המחשב]]
[[קטגוריה:חישוביות]]
[[קטגוריה:משפטים מתמטיים|רייס]]
[[קטגוריה:הוכחות]]
[[קטגוריה:בעיות שאינן ניתנות לחישוב]]
 
[[en:Rice's theorem]]
[[de:Satz von Rice]]
אוחזר מתוך "https://he.wikipedia.org/wiki/משפט_רייס"