HW1
1- Sketch a composed TM M that performs the computation :
(s, à # w ) --|* M (h, à # wc
)
where wc 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 Nk
as 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 !
