An exercise problem once again has me stumped on a Turing Machine decidability proof.

We are given an alphabet with the strings 0 through 9.

Along with this, we have x as the infinite string of all digits in PI. (3141592...)

With L ⊆ Σ*, the language L = {A ∈ Σ*| A is a sub-sequence of x}. (from what I understand, the definition here of a sub-sequence is having a $x = x_1x_2x_3... $ where each $x_i$ can be constructed from Σ, then a sub-sequence of x is a finite string of the form $x_{i1}x_{i2}x_{i3} ... x_{ik}$ where $i_1 < i_2 < i_3 < ... < i_k.$

Other than that I have no idea where to start with this...

Thanks in advance.

  • $\begingroup$ And what is the question now? (Both the problem statement, and yours.) $\endgroup$ – Raphael Jan 28 '15 at 11:03
  1. Can you come up with a Turing machine that writes the decimal expansion of $\pi$ to tape?
  2. Can you come up with a Turing machine that, given a string, a separator, and the decimal expansion of $\pi$ on the tape, determines whether the string occurs as a subsequence of $\pi$? (see this question).
  3. Given such machines, can you 'weave' them into a single machine?
| cite | improve this answer | |
  • $\begingroup$ What happens if the input is not a subsequence of the decimal expansion of $\pi$? $\endgroup$ – Luke Mathieson Jan 28 '15 at 10:57

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