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
    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$?2012-10-30
  • 1
    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).2012-10-30
  • 0
    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.2012-10-30
  • 0
    Thanks, but couldn't function $f$ still be not computable even if $L$ is decidable?2012-10-31

1 Answers 1