Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}$ is only computable iff the language

$$ L = \{s\#^j\sigma : s\in A^*, \sigma \in A, \text{ the }j\text{'th symbol of } f(s)\text{ is } \sigma\}$$

is decidable. Why is that? Couldn't a function $f$ be not computable even if $L$ is decidable?

share|cite|improve this question
up vote 6 down vote accepted

If $L$ is decidable then you can use it's decider to compute $f$: for the first symbol of $f(s)$ run the decider on the input $s\#x$ for any $x\in A$. For one of them, the decider will answer YES--this is the first letter in $f(s)$.

Continue doing this (e.g., for the second letter, decide if $s\#\#x \in L$, etc.), and reveal $f(s)$ letter-by-letter until the time where the decider answers NO for all $x\in A$, which means you reached the end of $f(s)$.

So if $L$ is decidable, $f$ is computable. Conversely, if $f$ is not computable, it can't be that $L$ is decidable.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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