0
$\begingroup$

One of my final exam questions asked me to give a Turing-unrecognizable language over an unary alphabet, which I wasn't able to complete, but I ended using the Busy Beaver function (BB(k)) which is known to be something intractable or uncomputable so that I constructed the language as a set of strings 1^BB(k) for natural number k=1,2,... It intuitively feels like it's Turing unrecognizable but how can I prove it(if this is true)?

$\endgroup$
0
$\begingroup$

Suppose that you have an algorithm $f$ that decides $L=\{1^{BB(k)}\mid k \in \mathbb N\}\subseteq \{1^n\mid n\in \mathbb N\}$. Then you can build the following algorithm that computes $BB$:

// input k
n = 0
values_of_bb = []
while length(values_of_bb) < k
  if f(1^n) == 1
    values_of_bb.push(n)
    n = n + 1
return values_of_bb[k]

This will be true for all strictly increasing functions from $\mathbb N$ to $\mathbb N$: if the image is decidable, then the function is computable. You just have to enumerate potential values in increasing order and put them in a list (still in increasing order), and then the $k^\text{th}$ value is simply the $k^\text{th}$ element of this list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.