关于MoC的两个重要原理 一计算复杂性是否与计算模型有关？ 一不同计算模型解决同一类问题所需资源是否相同？ 相似性原理 一相似性原理：所有计算模型的计算能力等同 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 ·Turing完备性 丘奇一图灵论题：可计算性等价于图灵机的可计 算性 ·对偶性原理 一在并行计算模型上，计算的时间与空间可以互换关于MoC的两个重要原理 – 计算复杂性是否与计算模型有关？ – 不同计算模型解决同一类问题所需资源是否相同? • 相似性原理 – 相似性原理：所有计算模型的计算能力等同 • 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 • Turing完备性 – 丘奇－图灵论题：可计算性等价于图灵机的可计 算性 • 对偶性原理 – 在并行计算模型上，计算的时间与空间可以互换