# turing machine decidability proof [closed]

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...

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).
• What happens if the input is not a subsequence of the decimal expansion of $\pi$? – Luke Mathieson Jan 28 '15 at 10:57