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.


closed as unclear what you're asking by Raphael Jan 28 '15 at 11:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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?
  • $\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.