Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

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

2 Answers

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^*)$.

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.