## A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

I read some computation theory lecture notes and after citing and proving the proposition: $$\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$$ it says that $$\emptyset\in S$$ is not a sufficient condition, i.e $$L_S \notin RE$$ doesn’t yield $$\emptyset \in S$$, by giving the counter example $$L_{\Sigma ^*}\notin RE$$ . However it says that there is a necessary and sufficient condition under which $$L_S\notin RE$$. I searched in Sipser’s book for this condition but couldn’t find it. I would really appreciate a reference for this condition.

Edit : given the answer by @dkaeae , I wish to know what is the stronger property one can deduce about a non-trivial $$S\subset RE$$ in case $$L_S \notin RE$$.

Posted on Categories proxies

## If $\lambda \notin \sigma(A)$ then $\lambda \in \sigma (B)$ iff $\lambda \in \sigma_p(B)$ or $\overline{\lambda} \in \sigma_p(B^*)$

Let $$A$$, $$B$$ and $$C$$ the differential operators defined by $$D(A)=H^{2n}(\mathbb{R}), \ D(B)=H^{2n}(0, \infty)\cap H^{n}_0(0, \infty), D(C)=H^{2n}(-\infty,0)\cap H^{n}_0(-\infty,0),$$ where $$H^{k}(I)$$ is the Sobolev space $$W^{k,2}(I)$$, and $$Af:=Tf, Bg:=Tg, Ch:=Th \mbox{ for } \ f \in D(A), \ g \in D(B), \ h \in D(C),$$ where $$T:=\sum_{r=0}^{2n}a_r\frac{d^r}{dx^r}$$ with $$a_r$$ complex constants.

I know that $$\sigma(A)=\sigma_{ess}(A)$$, i.e., $$\lambda \in \sigma(A)$$ iff $$A-\lambda I$$ is not a Fredholm operator (an operator is Fredholm if its range is closed and both its kernel and its cokernel are finite-dimensional).

I need to show that if $$\lambda \notin \sigma(A)$$ then $$\lambda \in \sigma (B)$$ iff $$\lambda$$ is an eigenvalue of $$B$$ or $$\overline{\lambda}$$ is an eigenvalue of $$B^{*}$$. I’m reading a proof of that assertion, but I don’t understand the argument. The proof is the following:

Since $$B\oplus C$$ differs from $$A$$ only by imposing homogeneous Dirichlet boundary conditions at $$0$$ (I think that I can say that $$A$$ is a finite-dimensional extension of $$B\oplus C$$), the difference of the resolvents is of finite rank (If $$A$$ is a finite-dimensional extension of $$B\oplus C$$, the difference of the resolvents of that operators is of finite rank (Lemma 6.32 on page 188 of Kato’s book)). So if $$\lambda \notin \sigma(A)$$ then it follows that $$B-\lambda I$$ and $$C-\lambda I$$ are Fredholm operators (why?). Thus $$\lambda \in \sigma (B)$$ iff $$\lambda$$ is an eigenvalue of $$B$$ or $$\overline{\lambda}$$ is an eigenvalue of $$B^{*}$$ (why?).

Thank you for reading my question. Can you help me to understand the proof?

## How to proof problem L $\notin \texttt{DSPACE}(f)$

I want to proof a language $$L$$ is not in $$\texttt{DSPACE}(f(n))$$ the languages, that a deterministic Turing machine can decide with fixed tape length of $$f(n)$$ (wiki). Show:

\begin{align*} L \notin \texttt{DSPACE}(f(n)) \end{align*}

How would I do this?

My first attempt was to reduce a language $$L’$$ from $$\texttt{DSPACE}$$ to the language $$L$$, but I don’t know of any language in $$\texttt{DSPACE}$$ and I don’t know if I can “simply” reduce it. Does anyone have a reduction that I see and try to understand?

edit:

as david-richerby mentioned: $$f(n) \in \Omega(\log{n})$$

The exact exercise is: $$L = \{ w\mid w \in T(M_w),M_w \text{ needs space |w|}\}$$

Posted on Categories proxies

## Is $L = \{ a^n\ |\ a^n \not\in L_n \}$ Turing recognizable (recursively enumerable)?

Say $$\Sigma = \{a\}$$, $$M_1, M_2, …$$ is an enumeration of all TMs that recognize languages over $$\Sigma$$ and $$L_1, L_2, …$$ are respectively the languages that are recognized by those TMs. We construct the language $$L = \{ a^n\ |\ a^n \not\in L_n \}$$. Is $$L$$ Turing recognizable (recursively enumerable)?

My thought process is this: Say $$L$$ is recognizable. Then given a string $$a^k$$, we find $$L_k$$ based on the enumeration of $$L_i$$‘s, and then we run $$M_k$$ on input $$a^k$$ to find if indeed $$a^k \not\in L_k$$. We must accept if $$a^k \not\in L_k$$, but $$M_k$$ is not guaranteed to halt in that case. So $$L$$ is not recognizable.

Now I have 2 questions: 1) Is my thought correct?, and 2) How can I make this more formal?

Posted on Categories proxies