Sketch a composed TM M that performs the computation :

Description

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 = Nⁿ 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 : N^k ® N defined inductively via functions f1,f2 ,…,fn , each with the range N ^k for k= 1,…,n operating on N to N^kas 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 : Nⁿ ® N described above by (1) is a bijection .

i.e. :

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

2. for every uÎN there exist (i1 ,…, in)ÎNⁿ 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 !