Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R.
The third language defines a constant Upper bound for the calculation steps of the machine.
While the second language defines a Upper bound according to the word and may enter an infinite loop. (is it true ?)
In addition, what is the difference between the first language and the second language?
The third language defines a constant Upper bound for the calculation steps of the machine.
There is no constant upper bound on the number of steps of $M$ in $L_3$. $L_3$ is the language of all machines that halt on at least one word $w$ while performing less steps than the length of $w$. The word $w$ is not fixed, all that is needed to $M$ to be in $L_3$ is for such a word to exists. The length $w$ must be finite by might be arbitrarily large.
$L_3$ is not in $R$. If $L_3$ was in $R$ then you wold be able to decide the halting problem. Given a given Turing machine $T$ and an input $w$, construct a Turing machine $T'$ that simulates $T$ on input $w$ and then accepts. If $T$ halts then it must do so within a certain number $x$ of steps, showing that $T' \in L_3$ since we can pick $w = 1^{x+1}$. If $T$ does not halt, then $T'$ also does not halt showing that $T' \not \in L_3$.
While the second language defines a Upper bound according to the word and may enter an infinite loop. (is it true ?)
I don't know what you mean by "may enter an infinite loop". It makes no sense to say that a language "enters an infinite loop". Moreover, a Turing machine $M$ in $L_2$ might or might not enter into an infinite loop, depending on its input. However you know for sure that there is at least one input to $M$ such that $M$ does not enter an infinite loop (since it must halt in less than $|M|$ steps). Notice that, as before, there is no constant upper bound on the number of steps. Rather the maximum number of steps is determined by the length of the encoding of $M$ (which must be finite but can be arbitrarily large).
$L_2$ is in $R$ since there are at most $|M|-1$ different positions of the input word that can be read by a Turing machine $M$ that halts in less than $|M|$ steps. You can then simulate (all the possible execution paths of) $M$ for $|M|-1$ steps on all possible input words of length at most $|M|-1$ (there are only $|\Sigma|^{|M|-1}$ such words).
In addition, what is the difference between the first language and the second language?
If you meant the intuitive difference in the definitions of $L_1$ and $L_2$, then in the first language the number of steps by which $M$ must halt is specified as part of the word in $L_1$. Alternatively, you can think of it as being written in unary as a part of the input of a TM that decides $L_1$. In contrast, the second language specifies the number of steps by which $M$ must halt using the length of the encoding of $M$ itself.
If you meant the set difference then $L_1 \setminus L_2 = L_1$.
$L_1$ is in $R$. since it suffices to simulate all the (possibly exponentially many w.r.t. $t$) execution paths of $M$ of length at most $t$.
