# Tag Info

6

No - even within (say) the class of $\Sigma_1$ (= c.e., r.e., semidecidable, ...) sets, there is lots of non-linearity even up to Turing reducibility (of course this is stronger than non-linearity up to many-one reducibility since $m$-reductions imply $T$-reductions). The study of the c.e. degrees began with Post's problem: is there a c.e. set whose Turing ...

2

Let $B$ be $A$ join $A^c$, for the concept of join defined in your question. Consider the language $H = \{\langle T \rangle \, \mid \, \text{$T$is a Turing Machine that halts on empty input}\}$. Let $f$ be $m$-reduction from $H$ to $A$. Given word $w \in \{0,1\}^*$ (think of this word as a Turing Machine), $w \in H \iff f(w) \in A \iff f(w)0 \in B$. ...

2

The languages are not the same. In the first one, $w$ is a part of the input. In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.

1

The easy and immediate way to see this is to note that the language of strings of length at most $k$ is finite, therefore it is regular. Regular languages are closed under complementation (just switch the accept and reject states), so your language of strings of length greater than $k$ is also regular.

1

The operation you described in actually the join operator in the semilattice of Turing degrees, defined as $A\sqcup B=\{0x | x\in A\}\cup \{1x | x\in B\}$. It is not hard to show that $A,B\le_T A\sqcup B$, thus if $A\in RE\setminus R$ then $\overline{A}\notin RE$ and thus $A\sqcup\overline{A}\notin RE$.

1

Suppose, for example, that $A$ join $A^c$ is c.e. Since $A$ is c.e.-complete, $A$ join $A^c$ reduces to $A$. In particular, $A^c$ reduces to $A$. Show that this leads to a contradiction. The proof that $A$ join $A^c$ isn't co-c.e. is similar.

1

I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question? You can easily simulate any DFA in your model, and so your model ...

1

The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows: Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $... 1 Using the definition of reduction,$x\in L_1\iff f(x)\in L \iff x\in L_2$And thus$L_1=L_2\$.

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