Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.

Then, that language/set is decidable. Because it is trivial to devise a TM_R, using TM_G, that recognize/accepts the words/numbers of that language/set.

It is also clear (really?), that there must be a non-contracting grammar for the language of TM_G.

Now, let's suppose a we have a TM_G' that generates a decidable language not in lexicographical order. Because the language is decidable, there must exist a TM_R' that completely recognizes it. Now, it is not clear how to build TM_R' using TM_G' (probably this is a unsolvable problem (is it?). At least, it is easy how to have a semi-deciding TM_R' based on TM_G').

In any case, by assumption, TM_R' (the complete-recognizer) exists and therefore (really?) it exists a non-contracting grammar for the language.

In sum, is the class of decidable languages equivalent to non-contracting grammars?

In other words, are there a decidable language that cannot be generated by a non-contracting grammar (type 1)?

Expressed in terms of Turing Machines: **is the power of all halting TM equivalent to the power of all linear bounded automata (a restricted type of TM equivalent to type-1 grammars).? **

Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.

Then, that language/set is decidable. Because it is trivial to devise a (halting) TM_R, using TM_G, that recognize/accepts the words/numbers of that language/set.

It is also clear (really?), that there must be a non-contracting grammar for the language of TM_G.

Now, let's suppose a we have a TM_G' that generates a decidable language not in lexicographical order. Because the language is decidable, there must exist a TM_R' that completely recognizes it. Now, it is not clear how to build TM_R' using TM_G' (probably this is a unsolvable problem (is it?). At least, it is easy how to have a semi-deciding TM_R' based on TM_G').

In any case, by assumption, TM_R' (the halting/complete recognizer) does exist. Then, we can use TM_R' to build a TM_G'' which generates the language in lexicographical order. Hence (really?), there exists a non-contracting grammar for the language.

In sum, is the class of decidable languages equivalent to non-contracting grammars?

In other words, are there a decidable language that cannot be generated by a non-contracting grammar (type 1)?

Expressed in terms of Turing Machines: **is the power of all halting TM equivalent to the power of all linear bounded automata (a restricted type of TM equivalent to type-1 grammars).? **