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.
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.