Description
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
