Skip to main content

New answers tagged

3 votes

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

It is decidable whether $\epsilon \in L(G)$. Given a context-free grammar $G$, you can construct a new context-free grammar $G'$ such that $L(G')=L(G) \cap \Sigma^+$. If $L(G')=\Sigma^+$ and $\...
D.W.'s user avatar
  • 160k
0 votes

Is the Rice Theorem applicable for these problems?

Just a rule of thumb:- Rice's theorem concerns properties of languages, not the Turing machines. Consider property P as the set of some R.E. languages, P is nontrivial if it does not contains all R.E. ...
harshchy2210's user avatar
1 vote

Prove that a language does not many one reduce to its complement

You won't be able to prove this, because it is false. Let $J$ be an arbtirary undecidable language. Let $L = \{2n \mid n \in J\} \cup \{2n+1 \mid n \notin J\}$. Then $L$ is undecidable, and $L \...
Arno's user avatar
  • 3,105
1 vote
Accepted

A decision procedure for PCP

A decision procedure must always terminate. Your procedure never terminates if there is no possible way to make a match. If you run your procedure for a year and don't find any match, do you ...
D.W.'s user avatar
  • 160k
0 votes

Show that it is undecidable if two Turing Machines accept the same language

I think this is an alternative answer: give a mapping reduction from HALT to L, where L is the language consisting of all Turing machine pairs that accept exactly the same inputs. Let f(<M,w>) = ...
Charlie Weiler's user avatar
1 vote

If a language L over a finite alphabet A has both a subset and superset that are Turing-recognizable, does this make L Turing-Recognizable too?

Hint: consider the empty set and the set of all strings.
orlp's user avatar
  • 13.4k
3 votes

Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
Hendrik Jan's user avatar
  • 30.7k
6 votes

Is every non-recursively-enumerable language RE-hard?

Partial answer here: I think it at least depends on the chosen reduction. For example, consider $H\in \mathsf{RE}$ the halting problem. Then $\overline{H}\notin \mathsf{RE}$, but there is no many-one ...
Nathaniel's user avatar
  • 15.7k

Top 50 recent answers are included