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
