computation-theory - 证明具有 k 个堆栈的 PDA 是图灵可识别的

Question

这曾经是一个家庭作业，但我现在将它用于修订目的；但是这个问题没有解决方案。任何建议将不胜感激。

问题是：“假设 k-PDA 是一个可以访问 k 个堆栈的下推自动机。1-PDA 是标准 PDA，您已经看到 2-PDA 可以识别任何图灵可识别的语言。证明，对于任何k ≥ 0，任何被识别为 k-PDA 的语言都是图灵可识别的。”

直接复制粘贴，有大神帮忙解决下这个问题吗？另外，我觉得这写得不正确，但我不确定什么是正确的。

Answer 1

似乎我们可以通过多带（k-tape）图灵机来模拟 k-pda 运动，其运动可以由标准图灵机模拟。