a$)$ Define what is called a nondeterministic configuration tree of a one$-$tape nonde$-$

terministic Turing machine $M=($:$Q,,,,q_0,q_a,q_r$:$)$ for input uin${}^{**}.$ b$)$ Assume,

that $q_0$abbab$|--{?}^{**}a{q}_{r}ba(a,$bin$)$ holds. Does it imply abbab!inL$(M)?$ Why?

a$)$ What does it mean, that two closed first order formula are logically equivalent

to each other? b$)$ Define the language EQUIVPRED. c$)$ Is EQUIVPRED decidable?

d$)$ And the complementary language of EQUIVPRED? Why?