0
$\begingroup$

This question already has an answer here:

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)?

$\endgroup$

marked as duplicate by Raphael Dec 10 '17 at 19:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Use a reduction? $\endgroup$ – D.W. Dec 10 '17 at 15:56
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.