2
$\begingroup$

I was doing some exercises from computability and complexity and then I have stuck on this problem:

What type of problem (decidable, semi-decidable, undecidable) is the problem (show it):

Do given Turing Machines M, N accepts equinumerous languages?

  • Answer this question without using Rice theorem.

I know what equinumerous means and I know basics about Turing Machines, however I totally don't have idea how to do this exercise or even how to start it. I will be very thankful for every help.

$\endgroup$
  • $\begingroup$ Are you supposed to determine whether this is a decidable problem? $\endgroup$ – realdonaldtrump May 16 '18 at 11:53
  • $\begingroup$ The question looks like this but when problem is decidable there is Turing Machine which decides language L if it accepts all strings in L and rejects all strings not in L so I think this can be the way how to do this. And there is said to not use Rice theroem so I think it is a question about decidable problem. $\endgroup$ – Ppyyt May 16 '18 at 12:21
  • $\begingroup$ This post would be better with more context - where did you encounter the problem? What theorems are you familiar with? In general, for problems like this, the first step is to compute where you think the problem falls in the arithmetical hierarchy. Have you done that here? $\endgroup$ – Carl Mummert May 20 '18 at 15:07
  • $\begingroup$ I have encountered this problem in topic about Halting Problem where to proof some of given examples we should create Machine on which we later proof that if the language is decidable undecidable or semi-decidable. $\endgroup$ – Ppyyt May 21 '18 at 9:54
1
$\begingroup$

It's undecidable.

Otherwise, you could answer questions like 'does M halts on word $w$ ?' by building a machine that accepts words of size $s$ iff M halts on $w$ after less than $s$ steps of computation and comparing that machine to the machine that accepts all words. A yes would mean the first question is a yes too.

It's also not semi-decidable because you also could answer questions like 'does M never halts on word $w$ ?' by building a machine that accepts words of size $s$ iff M halts on $w$ after less than $s$ steps of computation and comparing that machine to the machine that rejects all words. A yes would mean the first question is a yes too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.