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

Question

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

Answer 1

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