» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
קבלת שפות
דף ראשי  מכונת טיורינג  קבלת שפות גרסה להדפסה

קבלת שפות

 

הגדרה: תהי   Mמכונת טיורינג  ויהי  w Î (S - { # } ) *

נאמר כי  M מקבלת את W אם

h, u a v )                                              (      *    ( s ‘,  #w# )  

עבור  u , a ,v  כלשהם.

ז"א שאם M מקבלת את W אז המכונה עוצרת, אחרת היא לא עוצרת לעולם, אלא נכנסת

 ללולאה אינסופית. 

תהי     (S - { # } ) * L Í שפה. נאמר כי M מקבלת את L  את לכל w Î (S - { # } ) *   

   Mמקבלת  את W  אם ורק אם L       w Î

עבור מכונה M    נסמן  L ( M )    את השפה ש – M מקבלת.

 

 לכל מכונה יש תמיד שפה שהיא מקבלת, ז"א שלכל מכונה M ,

השפה L ( M ) מוגדרת היטב - או שהמכונה עוצרת או שלא.

 

טענה: תהי L  שפה אם קיימת מכונת טיורינג M שמכריעה את L , אזי קיימת מכונת טיורינג אחרת M’  שמקבלת את L .

הוכחה: M’ תפעיל את  M. אחרי ש – M  עצרה אם בפלט כתוב "1" M’  תעצור,

אם בפלט כתוב "0" , M’ תכנס ללולאה אינסופית.

 

 

 22-03-04 / 11:00  עודכן ,  31-12-03 / 21:47  נוצר ע"י שמרית דויטש  בתאריך 
 מכונה עם K סרטים- הוכחת המשפט - הקודםהבא - מכונת טיורינג לא דטרמיניסטית 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 4