# Tag Info

• 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 ...
• 160k

### 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>) = ...
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.
• 13.4k
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....
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 ...