I have a made up machine, which has the same definition as Turing machine, but the transition function and the step of computation of the machine. What would be the approach of the proof that the language accepted by this machine is (or is not) equal to L0 (recursively enumerable language)?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Use a reduction? $\endgroup$– D.W. ♦Commented Dec 10, 2017 at 15:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You need to show that any language that is accepted by a Turing machine is accepted by one of your machines. So, start with an arbitrary Turing machine $M$ and show that one of your machines can accept $L(M)$, e.g., by showing how to directly simulate the operation of $M$.
answered Dec 10, 2017 at 19:30