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
