图灵机=有限自动机+两个栈？这结论早就不新鲜了

图灵机到底是不是某种更简单的东西？2018年这篇UTEP的技术报告给出了一个答案：图灵机本质上就是一个带着两个栈的有限自动机。这个等价关系在计算理论教材里其实早有提及，并非什么惊世骇俗的新发现。但它被写成正式报告发布，说明还有人愿意把老结论梳理清楚、落笔成文。说实话，这种"把已知东西说清楚"的工作，在学术界被严重低估。不过，它能在Hacker News上拿到1个点、0条评论，也暴露了一个事实：对于已经懂的人，这不是新知识；对于不懂的人，它可能门槛太高。知识传播的鸿沟，从来不只是内容的问题。

原文：A Turing Machine Is Just a Finite Automaton with Two Stacks (2018) · 来源：Hacker News