Question

Show that every infinite Turing-recognizable language is the range of some one-to-one computable function.

Answer 1

set of all string over any finite alphabet can be enumerated i.e. it take finite number of steps taken to generate an element of language.

suppose alphabet Σ = {a,b}
Σ* = {ε,a,b,aa,ab,ba,bb...................}

Go length wise and dictionary order
length 0 ε
length 1 a,b
length 2 aa,ab,ba,bb and so on.........

Here exists a enumerated method through which any string over set Σ = {a,b} can be generated in constant time (through index)

Therefore, set of all string over any finite alphabet Σ = {a,b} are countable .
Turing-recognizable language is Recursive Language.
Recursive language is subset of all string over any finite alphabet Σ = {a,b}
Therefore ,Recursive Language is also countable.

Hence,every infinite Turing-recognizable language is the range of some one-to-one computable function.