0
$\begingroup$

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?

  • 0
    Thanks, but couldn't function f still be not computable even if $L$ is decidable?2012-10-31

1 Answers 1

1

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