# Tag Info

2

In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then: if $x \in A$, ...

2

As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint. Hint: consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not ...

1

What confuses you is that the words in the languages are encodings of machines that simulate runs of other machines, but at the end of the day, these are just words. Specifically, given input $x = \langle M, x\rangle$ for the reduction, the reduction itself does not simulate the run of $M$ on $x$, the reduction only outputs $f(x) = \langle M'\rangle$ which ...

1

Let's say that $f:\Sigma^* \to \Sigma^*$ is a reduction from $A\subseteq \Sigma^*$ to $B\subseteq \Sigma^*$. A flowchart graph of $f$ looks like: Indeed, $f$ maps all words in $A$ to $B$, and all words in $\overline{A}$ to $\overline{B}$. The closest flowchart to the image that you attached corresponds to the reduction theorem, to be explined below. (You ...

1

The arrow is going from $A$ to $B$. It means you are solving problem $A$ using problem $B$. So, it is a reduction from $A$ to $B$

1

For $L_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$. Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by: The current state. The ...

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