pode

Estou tentando me ensinar a teoria da computabilidade com um livro didático. De acordo com o meu livro, uma função$f$ sobre um alfabeto $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\}$ só é computável se o idioma

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

é decidível. Por que é que? Não foi possível uma função$f$ não seja computável, mesmo que $L$ é decidível?

E se $L$ é decidível, então você pode usá-lo para calcular $f$: para o primeiro símbolo de $f(s)$ executar o decisor na entrada $s\#x$ para qualquer $x\in A$. Para um deles, o decisor responderá SIM - esta é a primeira letra do$f(s)$.

Continue fazendo isso (por exemplo, para a segunda letra, decida se $s\#\#x \in L$etc.) e revele $f(s)$letra por letra até o momento em que o decisor responder NÃO a todos$x\in A$, o que significa que você chegou ao final de $f(s)$.

Então se $L$ é decidível, $f$é computável. Por outro lado, se$f$ não é computável, não pode ser isso $L$ é decidível.