Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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? I don't understand because computability and decidability are 2 different concepts, right?

share|cite|improve this question
Does your book really define the alphabet $A$ as the English alphabet, or could you be mixing up the technical term with the English word? More common alphabets include $\{0,1\},\{1\},\{a\},$ and $\{0,1,2,3,4,5,6,7,8,9\}$. Also, do you mind defining the notation #$^j$? – Kevin Carlson Oct 30 '12 at 23:00
Basically computability and decidability are two names for the same concept -- and the property you quote here is exactly what makes them the same concept. (One uses the word "computable" about finding the value of functions, and the word "decidable" about determining membership of sets, but they are really the same thing -- or at least very close allies -- because you can express a set as a function or vice versa). – Henning Makholm Oct 30 '12 at 23:09
The idea is that a function is computable if you can decide whether a given character is or isn't the correct $j$-th character of $f(s)$ for every input $s$ and output position $j$. I'm not sure why not just say $L=\{s\#f(s) : s\in A^{*}\}$, though, unless it's to allow for infinitely long output strings. – mjqxxxx Oct 30 '12 at 23:59
Thanks, but couldn't function $f$ still be not computable even if $L$ is decidable? – Minden Petrofsky Oct 31 '12 at 21:18

If you can compute $f(\sigma)$ then, for each $k$, you can compute the $k$th letter of $f(\sigma)$. Conversely, if you can compute the $k$th letter of $f(\sigma)$, as a function of $\sigma$ and $k$, then you can compute $f(\sigma)$ itself, but just computing letters one after another until you hit the end of the string. You can tell when you hit the end of the string because, for example, if the string $f(\sigma)$ has length $5$ then you will find that no letter in your alphabet is the $6$th letter of $f(\sigma)$.

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.