11

No. Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.


3

What you are missing is that if $\langle M, w\rangle \notin \overline{A_{\mathrm{TM}}}$, i.e. if $M$ halts on input $w$, you don't know whether or $M_1 \notin L$. If $M$ does halt on $w$, but this takes longer than $20$ steps, it would also hold that $M_1 \in L$. Thus, you don't have a reduction here. That the language $L$ cannot be co-RE is an immediate ...


2

This is minimization in Python: def mu(p): n = 0 while not p(n): n += 1 return n It is a slightly more complicated exercise to convert a while to $\mu$, but essentially, $\mu$ performs a search for the first (minimal) number satisfying a given condition, where there is no guarantee that the search will succeed.


2

"Do this ad infinitum and you will eventually describe $\mathbb{R}$." The "ad infinitum" takes uncountably many steps to complete.


Only top voted, non community-wiki answers of a minimum length are eligible