HW2
1- State the Turing Machines in the tabular format discussed in class
and lecture notes that implement the following RATM statements :
(a)add =c ; (b) jpos s ; (c) sub j
2- Assuming a 2 tape TM that multiplies the binary coded positive
integers in tapes 1 and 2 and writes the result in tape 1 is available and
is named as MULT ; construct in tabular format a multitape ,
nondeterministic TM that decides whether a given binary coded integer
is a prime number making use of the TM MULT.
3- Problems from the main text book (note the word accepts means
semidecides in our class terminology): 4.5.1, 4.5.2
