3
$\begingroup$

$L\subseteq \{0,1\}^*$

Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides the language, you can arbitrarily extend this Turing Machine (by adding redundant states), which means there are a countably infinite number of Turing Machines that semi-decide L. Does this reasoning sound right, or does the answer depend on what the language L is?

$\endgroup$
5
$\begingroup$

You are correct.

One can always add redundant states to obtain different Turing machines deciding (or semi deciding) the same language. This yields countably infinite Turing machines deciding $L$ (for any decidable $L\subseteq \Sigma^*)$.

$\endgroup$
0
$\begingroup$

Yes; every computable function has infinitey many Turing machines that compute it. That is a fundamental property of all Turing-complete models/formalisms.

It is a consequence of the s-m-n theorem and (a stronger version of) Kleene's recursion theorem taken together, two properties that all Turing-complete models of computation share.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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