When L is a language, lengths(L) denotes the language {1|w|: w L}1?.

(3)

(a) Prove or disprove: If L is Turing decidable, then lengths(L) is Turing decidable. (b) Disprove: If lengths(L) is regular, then L is Turing recognizable.

When L is a language, lengths(L) denotes the language {1lvl : WEL}