可以考虑使用一个简单的图灵机M,如下:M = (Q, Σ, Γ, q0, F, δ)其中,Q={q0, q1, q2, q3},Σ={0, 1},Γ={B},q0=q0,F={q3},δ(q0, 0)=q1,δ(q1, 0)=q2,δ(q2, 0)=q3,δ(q3, 0)=q3,δ(q3, 1)=q3。并且可以选择一个简短的串w=0001,模拟证明过程,构造出一簇骨牌P:P={(q0, 0, B, q1), (q1, 0, B, q2), (q2, 0, B, q3), (q3, 0, B, q3), (q3, 1, B, q3)}。