Consider the language L3 = { 0^p | p is a prime number }.

1. Show that L3 is not regular and not context free.

2. Give a turing machine (possibly multi-tape) that recognizes L3. You can give higher level description of the turing machine, but all the steps (or each batch) should be precisely described in a clear manner.