Turing Machine & Recursively enumerable languages.

Question

Suppose Turing Machine(TM) M and language L.

L = { "M" | M has as input strings which $∈$ $\{0,1\}^{*}$ and terminate at a maximum of $512^{512}$ steps}

Is L a recursively enumerable language?

Answer 1

We define an encoding of a Turing Machine as a set of combinations of all strings of length $\le 512^{512}$. To imagine this let's take an smaller case : $2^2$ steps
Then L would contain combinations of all the strings of length $\le 2^2$ as follows:
$$0 $$ $$1$$ $$00$$ $$01$$ $$10$$ $$11$$ $$.$$$$.$$ $$.$$ $$.$$ Each Combination of these strings encodes a turing machine thus representing a turing machine by strings generated by it
We can define this set of turing machine encoding as a power set but of a finite set so it is also finite so it is countable.
Similarly you can prove it for the length$\le 512^{512}$
Since by definition Every recursively enumerable language is countable and because this set of encoding of turing machines is countable ,it is recursively enumerable.