patternMinor
Show that it is undecidable if two Turing Machines accept the same language
Viewed 0 times
showsameundecidabletheacceptlanguagetwothatmachinesturing
Problem
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!
Solution
Let's restrict ourselves to Turing machines that ignore their input. Now suppose you have two Turing machines:
If you could decide if they accept the same language, you'd be able to decide if
This applies to SW/HW as well. It's undecidable if two programs perform the same computation or not.
- 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.
Context
StackExchange Computer Science Q#11916, answer score: 6
Revisions (0)
No revisions yet.