lata

Estoy tratando de enseñarme la teoría de la computabilidad con un libro de texto. Según mi libro, una función$f$ sobre un 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\}$ solo es computable si el idioma

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

es decidible ¿Porqué es eso? No se pudo una función$f$ no ser computable incluso si $L$ es decidible?

Si $L$ es decidible, entonces puedes usar su decisor para calcular $f$: para el primer símbolo de $f(s)$ ejecuta el decisor en la entrada $s\#x$ para cualquier $x\in A$. Para uno de ellos, el decisor responderá SÍ, esta es la primera letra en$f(s)$.

Continúe haciendo esto (por ejemplo, para la segunda letra, decida si $s\#\#x \in L$, etc.), y revelar $f(s)$letra por letra hasta el momento en que el decisor responde NO para todos$x\in A$, lo que significa que llegaste al final de $f(s)$.

Así que si $L$ es decidible $f$es computable Por el contrario, si$f$ no es computable, no puede ser eso $L$ es decidible