MapReduce图灵完备吗？

Question

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

1. 首先，由于MapReduce不是一种实际的编程语言（它更像是一套处理数据的规则），那么谈论图灵完备性是否有意义？
2. 如果真的有意义，那么MapReduce系统是图灵完备的吗？

Answer 1

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

2. 我的赌注是，如果且仅当指令集是图灵完备的时候，给定指令集的MapReduce才是图灵完备的。如果指令集是图灵完备的，那么加入MapReduce不会改变任何东西。如果指令集不是图灵完备，那么在map或reduce阶段没有任何东西可以使其成为图灵完备。