Peut être pas calculable même si est décidable?

J'essaie de m'enseigner la théorie de la calculabilité avec un manuel. Selon mon livre, une fonction sur un alphabet n'est calculable que si la langue$f$$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\}$

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

est décidable. Pourquoi donc? Une fonction ne pourrait-elle pas être calculable même si est décidable?$f$$L$

Si est décidable alors vous pouvez l' utiliser est decider pour calculer : pour le premier symbole de exécuter le decider sur l'entrée pour tout . Pour l' un d'eux, le décideur répondra OUI - c'est la première lettre de .$L$$f$$f(s)$$s\#x$$x\in A$$f(s)$

Continuez à faire cela (par exemple, pour la deuxième lettre, décidez si , etc.) et révélez lettre par lettre jusqu'au moment où le décideur répond NON pour tous les , ce qui signifie que vous avez atteint la fin de .$s\#\#x \in L$$f(s)$$x\in A$$f(s)$

Donc, si est décidable, est calculable. Inversement, si n'est pas calculable, il ne peut pas être que soit décidable.$L$$f$$f$$L$