מילון מונחים ק-ר
ק
תהי Mמכונת טיורינג ויהי w Î (S - { # } ) *
נאמר כי M מקבלת את W אם
עבור u , a ,v כלשהם.
תהי S,h),(Q,S,d M= מכונת טיורינג.
קונפיגורציה של M הינה רביעיה(q,u,a,v)ÎQ x S* x S x S* :
כלומר: q ÎQ מצב
u, v מחרוזות
α סימן
ר
רדוקצית התאמה מ -A ל B- הינה הפונקציה: 2* å ® 1* å f: כך שלכל, 1 *, XÎå f(X) ÎB Û XÎ A.
מתקיים אם B כריעה וקיימת רדוקצית התאמה מ- A ל- B שניתנת לחישוב אז גם A כריעה.
רדוקצית התאמה הפוכה מ A ל B הינה הפונקציה: 2* å ® 1* å f: כך שלכל 1*, XÎå f(X) ÏB Û XÎ A.
מתקיים אם B כריעה וקיימת רדוקצית התאמה הפוכה מ A לB ניתנת לחישוב אז גם A ניתנת להכרעה.
גולשים מקוונים: 4