Show that it is undecidable if two Turing Machines accept the same language I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a homework question!
Let's restrict ourselves to Turing machines that ignore their input. Now suppose you have two Turing machines:


Some given one T.
Another that loops forever.


If you could decide if they accept the same language, you'd be able to decide if T halts or not. This is impossible - see the halting problem.



This applies to SW/HW as well. It's undecidable if two programs perform the same computation or not.