2006 Q9

Question 9 (2006)
a) Any operation that is defined on all sequences of K numbers (for some number K >= 1) and that can be performed by a TM is called Turing-computable or just computable.

b)(Do you draw a TM?)

1. Get first a replace with A
2. Go to end of tape add X
3. Return to First A move one right and replace a with A
4. Repeat 2-3 until no more a's/ first X
5. Goto beginning of Tape
6. Replace all A's with a's and X's with a's till end of tape
7. HALT

TM = Computable


YES/NO?

b) Draw a TM

3) I started like that. But when changing A's and X's back to a's you do not know where the beginning of the tape is.

1) (a, A, R)
2) Look for a delta, move left and change the A back to a and add another a. HALT
3) From START to HALT have (delta, delta, R) , as N=0
4) Another branch after (a, A, R) with (a, a, R), which has a state that loops until delta. Add X.
5) Loop back to A and change the next a to Y. Back to and ens and add X. (repeat for the rest of the a's)
6) when you get to the first X, then all a's are now Y's or an A.
7) Move left on the X back to A.
8) Now move down the tape changing all A, Y's and X's to a's
9) delta to HALT

Hope this makes sense (it is late)

_____________________________________
The sun is always shining, but it is far away.

All helps appreciated. If not by me then students to follow