computer-science - 有没有比传统计算机更容易在图灵机上实现的问题？

Question

例如，我知道找到模数 n 为 k 的整数很好地映射到有限状态机，并降低自动机在解析确定性语法方面的工作。我想知道是否有类似图灵机的问题。

标签： computer-scienceturing-machinesautomata-theory

Answer 1

正如tia所提到的，这类问题更适合cs.stackexchange.com。我想说这个问题没有很好地说明，因为传统计算机基本上是一种图灵机。这取决于您使用的是哪种图灵机。例如，许多问题在非确定性图灵机上的解决速度比在经典计算机（确定性）上要快得多。