שאלות 5-8

      5. בנו מכונת טיורינג המחשבת את הפונקציה {0} U  N → N * N :f

            f(m, n)=m mod n .

עבור תוצאת אפס, קונפיגורציית הפלט צריכה להיות ### , וכן m ,n ותוצאת הפלט מיוצגים אונארית.

6. בנו מכונת טיורינג המחשבת את הפונקציה g:N2→N המוגדרת על ידי: g(m,n)=m+n, כאשר m, n מיוצגים בייצוג בינרי. הספרה הימנית ביותר ב-m מתאימה לספרה הימנית ביותר ב-n.

לדוגמא, עבור הקלט                    #1001010110#10101###

            נקבל                                                  #1001101011###

7. בנו מכונת טיורינג המקבלת את השפה L מעל {a,b,c}*, המוגדרת על-ידי:

L={aⁿbⁿcⁿ | Nn}

8. בנו מכונת טיורינג המקבלת את השפה L מעל {a,b}*, המוגדרת על-ידי:

}בכל רישא של w יש יותר a-ים מ-b-יםL={w |