הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

7.1. הגדרות בסיסיות

הגדרה: פונקציה plot:[f:{Sigma ^*} o {Sigma ^*}] היא ניתנת לחישוב אם קיימת מ"ט M כך ש-plot:[{f_M} = f].

הגדרה: פונקציה "קלה" היא פונקציה ניתנת לחישוב. פונקציה "קשה" היא פונקציה שלא ניתנת לחישוב.

הגדרה: בהינתן פונקציה plot:[f], נגדיר: plot:[{L_f} riangleq left{ {left( {x,y} ight)|y = fleft( x ight)} ight}].

דוגמאות לפונקציות הניתנות לחישוב:

  • פונקצית הזהות.
  • פונקציה המוציאה plot:$varepsilon $ תמיד.
  • פונקציות רבות נוספות.

דוגמא לפונקציה שאינה ניתנת לחישוב:

  • פונקציה המקבלת קידוד של מכונה וקלט x ומחזירה 1 אם המכונה עוצרת על הקלט, ו-0 אם לא.

תרגיל: לאיזו מחלקה שייכת השפה הבאה: plot:${f_M}} $אינה ניתנת לחישוב plot:$L = {langle ext{M} angle |$

פתרון: אם plot:${f_M}$ אינה ניתנת לחישוב, אז אין מ"ט המתאימה לה, ולכן plot:$L$ היא השפה הריקה, ומכאן כפי שכבר ראינו plot:$L in R$.

משפט: תהי פונקציה plot:[f], אזי:

  1. plot:[f] ניתנת לחישוב plot:[ Leftrightarrow ][{L_f} in { ext{RE}}].
  2. plot:[f] היא פונקציה מלאה plot:$ Leftarrow $ (plot:[f] ניתנת לחישוב plot:[ Leftrightarrow ]plot:[{L_f} in R])

החלק הראשון של המשפט אומר לנו בעצם כי השפה של כל מכונה שייכת ל-RE.


תגיות המסמך:

לפרק הקודם7. חישוב פונקציות
לפרק הבא7.2. סיבוכיות קולמגורוב
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד