Question: Simulate a TM with infinite tape on both ends by using a two-track TM with finite storage.
Question: Prove the given language is non-Turing recognizable by using the diagnolization principle {(M, w) | TM M, starts with input w, does not halt}
Question: Make a TM for L = {w| w contains equal number of 0’s and 1’s} over {0,1}
a) Give an algorithmic description
b) Draw the transition diagram.
Question: Consider a language L = {0m10n10max(m,n)| m, n>= 0}. Make a TM which decides the language. Explain the algorithm and draw the transition diagram of the TM.
Question: Given the following TM M, does M a) accept or b) reject on inputs w1 = 000 and w2 = 0000? Illustrate the content of the input tape and positions of the head step-by-step.
