I have a grammatically computable function $f$, which means that a grammar $G = (V,\Sigma,P,S)$ exists, so that
$SwS \rightarrow v \iff v = f(w)$.
Now I have to show that, given a grammatically computable function $f$, a Turing Machine $M$ can be constructed, so that $M$ computes $f$.
Here is my idea:
- The Turing Machine writes the string $SwS$ to its tape.
- It nondeterministically chooses one of the productions in $P$.
- For the chosen production rule, say $x \rightarrow y$, it scans the tape from left to right and nondeterministically stops at a symbol and checks whether the next $|x|$ symbols match the left side of the production rule. If that's the case, it replaces $x$ with $y$ and chooses the next production rule.
After the computation, the tape contains the string $f(w) = v$.
Here is the question:
Because the TM is nondeterministic, there are many branches in the computation and each branch has its own "version" of the tape with its own content. But in the end, the starting string can only derive to a single string $v$, because the TM computes a function.
Does this mean that the computation branches will all have the same tape content when they arrive at their leaves?