מילון מונחים

א    ה    ח    מ    ס    פ    ק    ר   

א

האוסף P הינו האוסף P=U DTIME(f) (f פולינום).

אוסף כל השפות שאפשר להכריע אותם בסיבוכיות זמן פולינומית.

ה

הכרעת שפות: תהי  S,h),(Q,S,d M=  מכונת טיורינג. נאמר כי M  מכריעה את L  

אם לכל wÎS1*  מתקיים:

  ( s , # w #)|-----( h , # 1 # )                                    אם  wÎ L         

                                    ) # o  ( s , # w #)|-----( h , # אם   wÏ L     

כלומר, אם מילה נמצאת בשפה, המכונה תחזיר 1 , אחרת היא תחזיר 0.

ח

חישוב פונקציה: תהי *1∑→*2∑:f , ותהי S,h),(Q,S,d M=  מכונת טיורינג ,

כאשר    S2 È 1S Ê S

נאמר כי M  מחשבת את f  לכל  wÎS1*

(s, #w # )     M*      (h, #, f (w) #^ ).

חישוב פונקציה עם K פרמטרים: תהי 2* ∑→^K(*1∑):f   (= פונקציה ששולחת k פרמטרים, k מחרוזות)  ותהי S,h),(Q,S,d M= מכונת טיורינג.

 נאמר כי M  מחשבת את f  אם לכל   w1, w2,.….wk Î (S1^*) ^k   מתקיים:

( s, #w1#, #w2 #, ….. wk # )|---- (h, #, f (w1,w2, ….wk) # )