patternMinor
Can $f$ be not computable even if $L$ is decidable?
Viewed 0 times
cancomputabledecidableevennot
Problem
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? Couldn't a function $f$ be not computable even if $L$ is decidable?
$$
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? Couldn't a function $f$ be not computable even if $L$ is decidable?
Solution
If $L$ is decidable then you can use it's decider to compute $f$:
for the first symbol of $f(s)$ run the decider on the input $s\#x$ for any $x\in A$. For one of them, the decider will answer YES--this is the first letter in $f(s)$.
Continue doing this (e.g., for the second letter, decide if $s\#\#x \in L$, etc.), and reveal $f(s)$ letter-by-letter until the time where the decider answers NO for all $x\in A$, which means you reached the end of $f(s)$.
So if $L$ is decidable, $f$ is computable. Conversely, if $f$ is not computable, it can't be that $L$ is decidable.
for the first symbol of $f(s)$ run the decider on the input $s\#x$ for any $x\in A$. For one of them, the decider will answer YES--this is the first letter in $f(s)$.
Continue doing this (e.g., for the second letter, decide if $s\#\#x \in L$, etc.), and reveal $f(s)$ letter-by-letter until the time where the decider answers NO for all $x\in A$, which means you reached the end of $f(s)$.
So if $L$ is decidable, $f$ is computable. Conversely, if $f$ is not computable, it can't be that $L$ is decidable.
Context
StackExchange Computer Science Q#6406, answer score: 6
Revisions (0)
No revisions yet.