mapreduce - MapReduce 图灵完备吗？

Question

我有两个关于 MapReduce 框架和图灵完备性的问题:

1. 首先，由于 MapReduce 不是一种实际的编程语言(它更像是一组处理数据的规则)，谈论图灵完备性?
2. 如果它确实有意义，MapReduce 系统是否图灵完备？

Answer 1

1. 图灵完整性适用于指令集(即编程语言)，但 MapReduce 是一种编程模型。所以这个问题只有在您指定 map 和 reduce 阶段中可用的确切指令集时才有意义。

2. 我敢打赌，给定指令集的 MapReduce 是图灵完备的，当且仅当指令集是: 如果指令集是图灵完备的，那么将 MapReduce 添加到组合中不会改变任何东西。如果指令集不是图灵完备的，则在 map 或 reduce 阶段中没有任何内容可以使它成为图灵完备的。