He knows the famous result that "Equivalence of two Turing Machines is undecidable", but hopes to find a subset for which it is decidable, which would allow various interesting algorithms.
Unfortunately a decidable subset is not a Turing Machine ("unrestricted grammar" in the Chomsky hierarchy), which is possibly why the project went inactive.
2 comments
[ 4.8 ms ] story [ 19.4 ms ] threadCan anyone please explain what he's trying to create here? This looks interesting but I can't find anything on google. Thanks!
Unfortunately a decidable subset is not a Turing Machine ("unrestricted grammar" in the Chomsky hierarchy), which is possibly why the project went inactive.