Sketch a composed TM M that performs the computation :

1- Sketch a composed TM M that performs the computation :

(s, à # w ) --|* M    (h, à # w c)


where w c is the compressed version of w where all the characters ‘$’ within w are removed.

2- Problems from the main text book :

4.1.4, 4.1.7,4.1.12, 4.2.2, 4.3.1, 4.3.2 (a);(b),4.3.6


An optional HW question

Question – A Turing machine Mn operates on an abstract n-dimensional quadrant given by X = N´ … ´ N = Nn where N = {0,1,2, … , } denotes the set of natural numbers. The head can move in positive and negative directions along each of the dimensions; hence it has precisely 2n moves at each slot position. Each slot is an n-dimensional cube that carries data represented by a symbol in its alphabet set S . A standard TM M to simulate Mn must assign a unique slot on its tape corresponding to each n-dimensional cubic slot of Mn.

This is accomplished by defining functions fk : Nk ® N defined inductively via functions f1,f2 ,…,fn , each with the range N k for k= 1,…,n operating on N to Nkas follows :

f1(i1) = i1  for all i1Î N n

fk(i1,i2, ..., ik) := (fk-1(i1,i2, ...,ik-1) +ik)( fk-1(i1,i2,...,ik-1) +ik+1)/2 +ik , k =2,3,...,n . . . . . (1)


Hence each fk (i1,i2, ...,ik) can be computed sequentially using the inductive recipe above.


For example f2(i1,i2) = (i1+i2) (i1+i2 +1)/2 + i2  etc.








Theorem

The function fn : Nn ® N described above by (1) is a bijection .

i.e. :

    (i) fn(i1,i2, ..., in ) = fn(j1,j2, ..., jn ) Þ ip = jp  for p=1,…, n (hence it is an injection (1-to-1))

    (ii) for every uÎN there exist (i1 ,…, in)ÎNn such that fn(i1,i2, ..., in ) = u (hence it is

a surjection (onto) )


Using this theorem describe how M can simulate Mn . In particular describe how M moves its head when Mn oves its head from slot (i1 , ..., ip ... , in ) to (i1 , … , ip ± 1, … . in ).

(To get a feeling for the problem first solve it for n=2 , namely simulating a 2D-TM ! )


Meanwhile try also to prove the theorem above using induction on n !