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.

Tardif

Wouldn't this be better on the cstheory stackexchange site? – Bertiebertila

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.

Teriteria

Can you provide an explicit mapping of {1}* into Turing machines? – Kutaisi

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).

Sapotaceous

Answer 3

The only subset that is not decidable in {1}* is the empty set.

We can define a Language over {1}* in terms of a TM: L = { < M > | M is a TM and L(M) = empty }

So we can show that L is not decidable, because a TM U that receive L as a input need to test all elements over {1}* and then decide to accept in case of M rejected all of them, so it will never halt and it means that L is not decidable, implies that the empty Language is not decidable

Grandson