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$
4
  • $\begingroup$ Are you supposed to determine whether this is a decidable problem? $\endgroup$
    – realdonaldtrump
    Commented May 16, 2018 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
    Commented May 16, 2018 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
    Commented May 20, 2018 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
    Commented May 21, 2018 at 9:54

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .