Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

  1. The Turing Machine writes the string $SwS$ to its tape.
  2. It nondeterministically chooses one of the productions in $P$.
  3. 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?

share|cite|improve this question
up vote 1 down vote accepted

The typical case would be that most computation branches never arrive at a leaf at all. It is also possible, depending on the grammar, that some branches will arrive at a string that doesn't have the required form, yet no further reductions are possible. In that case you'd have to program an explicit infinite loop into your nondeterministic machine, such that those branches don't contribute a final result.

Note: If you're allowed to appeal to the Church-Turing thesis and say "because I can program such-and-such in a more convenient language, a Turing machine can do it", then I think it would be clearer simply to do a breadth-first search through the reduction graph until you reach a string of the required form. That is essentially equivalent to your solution (since something like breadth-first is the standard construction for getting a deterministic machine out of a nondeterministic one), but feels more direct at least to me.

share|cite|improve this answer

If f is a grammatically computable function as you define it, then yes. Either the leaves will all be the same, correct, string v = f(w), or the branches will "crash" on a leaf containing nonterminals which cannot be eliminated via productions. Otherwise, you do not have a grammatically computable function as you have defined it, since you would be able to produce two strings from SvS, and the sequence of production rules used by different branches of the TM would provide the counterexample.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.