6.1. קיום שפות שאינן כריעותטענה: קיימות שפות שאינן ב-R (וכן נטען גם טענה חזקה יותר: קיימות שפות שאינן ב-RE). הוכחה: נטען כי מתקיים: המעבר הראשון יבוצע על ידי התאמת מכונת טיורינג לכל שפה שב-RE (על פי הגדרה, קיים כזה). המעבר השני יבוצע על ידי התאמת טענה: מסקנה: טענה: הוכחה: נניח בשלילה כי מכאן: קיים נניח שכן, אזי הגדרה: שפה
במילים: שפה היא RE-שלמה אם היא שייכת ל-RE וכן ניתן לעשות אליה רדוקציה מכל שפה אחרת שב-RE. טענה: תגיות המסמך: |
תוכן העניינים:
קישורים רלוונטיים:שיתוף: |
החלק הראשון
בבקשה