language over {1} which is recognizable but not decidable?

Question

What is an example of a language over the alphabet {1}* which is recognizable but not decidable?

I have troubles finding an example of this. After a long search, I am still curious for the answer though.

A hint would be very welcome.

Answer 1

Since the universe of strings over any finite alphabet is countable, every language can be mapped to a subset of the natural numbers. So you just have to take a Recursively enumerable language wich is not decidable and map it into a subset of {1}*.

For example, in the classic version of the halting problem we enumerate every turing machine into a binary string; you can now sort all the turing machines and define a map f : TM -> N from Turing machines to integers where f(TM) = n if TM is the nth turing machine in the ordered list of all TM.

Now, the halting problem for turing machines coded as unary numbers is r.e. but not decidable.

Answer 2

Imagine a machine that given two machines whose alphabets are {1}*, accepts if the first can generate all strings that the second can generate.

Our machine halts if it accepts. But for strings not in the language (the first given machine cannot generate all the strings the second one can), our machine may halt and reject, or may never halt. This means that our Turing Machine is Recognizable, but it is not decidable.

See the Encyclopedia of Mathematics for more on recognizable and undecidable languages (specifically page 56).