» נושאי לימוד
» נושאי לימוד
יום ראשון 5 ביולי 2020
מילון מונחים ק-ר
דף ראשי  מילון מונחים א-ח  מילון מונחים ק-ר גרסה להדפסה

מילון מונחים ק-ר

 

א    ה    ח    מ    ס    פ    ק    ר   

 

ק

 

קבלה: יהי   S1 א"ב כך  ש: 1S Ï #   ותהיL Í S1   שפה.

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

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

h, u a v )                                              (      *    ( s ‘,  #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 ניתנת להכרעה.

 

תהי A מערכת ריצוף. ריצוף בעזרת A הינה פונקציה f: N×N→C.

 10-02-04 / 11:07  עודכן ,  10-02-04 / 10:21  נוצר ע"י שמרית דויטש  בתאריך 
 מילון מונחים מ-פ - הקודםהבא - תגבור 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 5