» נושאי לימוד
» נושאי לימוד
יום שישי 29 במרץ 2024
חישוב פונקציה
דף ראשי  מכונת טיורינג  חישוב פונקציה גרסה להדפסה

חישוב פונקציה ע"י מכונת טיורינג

 

הגדרה: תהי *1∑→*2∑:f , ותהי S,h),(Q,S,d M=  מכונת טיורינג , כאשר    S2 È 1S Ê S

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

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

 

בחישוב של פונקציה ממספרים טבעיים למספרים טבעיים, נשתמש בייצוג אונרי של המספרים, ז"א המספר  k  ייוצג ע"י המחרוזת:

k = 111...11

    

    k  פעמים

הגדרה: תהי  :N N f  ותהי S,h),(Q,S,d M=  מכונת טיורינג. נאמר כי M   מחשבת את f את לכל  kÍ 

מתקיים

 (  #  f (k)             ( s, #1 k # ) |------  ( h, #1

 

דוגמא: f: NN     

                      2n = f(n)

 

 

 

  נשים לב  שה - א"ב  של התשובה זה רק 1. אבל, במכונה הוספנו את A  ואת  . אלו הם סימונים פנימיים של המכונה, שלא נראה אותם בקלט או בפלט.

 

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