חישוב פונקציה ע"י מכונת טיורינג
נאמר כי M מחשבת את f לכל wÎS1*
בחישוב של פונקציה ממספרים טבעיים למספרים טבעיים, נשתמש בייצוג אונרי של המספרים, ז"א המספר k ייוצג ע"י המחרוזת:
k פעמים
מתקיים
2n = f(n)
נשים לב שה - א"ב של התשובה זה רק 1. אבל, במכונה הוספנו את A ואת # . אלו הם סימונים פנימיים של המכונה, שלא נראה אותם בקלט או בפלט. |