קבלת שפות
הגדרה: תהי Mמכונת טיורינג ויהי w Î (S - { # } ) *
נאמר כי M מקבלת את W אם
עבור u , a ,v כלשהם.
ז"א שאם M מקבלת את W אז המכונה עוצרת, אחרת היא לא עוצרת לעולם, אלא נכנסת
ללולאה אינסופית.
תהי (S - { # } ) * L Í שפה. נאמר כי M מקבלת את L את לכל w Î (S - { # } ) *
Mמקבלת את W אם ורק אם L w Î
עבור מכונה M נסמן L ( M ) את השפה ש – M מקבלת.
|
השפה L ( M ) מוגדרת היטב - או שהמכונה עוצרת או שלא. |
לכל מכונה יש תמיד שפה שהיא מקבלת, ז"א שלכל מכונה
טענה: תהי L שפה אם קיימת מכונת טיורינג M שמכריעה את L , אזי קיימת מכונת טיורינג אחרת M’ שמקבלת את L .
הוכחה: M’ תפעיל את M. אחרי ש – M עצרה אם בפלט כתוב "1" M’ תעצור,
אם בפלט כתוב "0" , M’ תכנס ללולאה אינסופית.
גולשים מקוונים: 2