Recursively Enumerable Languages and Turing Machines

Question

L1 = { M | Turing Machine M terminates for at least 637 inputs} L2 = { M | Turing Machine M terminates for at most 636 inputs} One of them is recursively enumerable, which one?

Answer 1

A language is said to be recursively enumerable if you can build a Turing machine that accepts all inputs that are in the language (but does not necessarily reject inputs that are not).

The obvious machine you'd want to construct, for both languages, is one that activates $M$ on all possible inputs in a finite time. While this may seem like a too much, it's actually possible, with the following algorithm:

1. Set an order in which you traverse all inputs, call them $(x_i)_{i=0}^\infty$. (This can be, for instance, the alphabetical order)
2. For the $i$th iteration, initialize $M$ and run $i$ steps of it on $\{x_0,\ldots,x_i\}$.

By doing this you guarantee that eventually you'll have run any finite number of steps of $M$ on any input.

Can you use this method to construct a machine that accepts one of $L_1,L_2$?