mapreduceturing-complete

Is MapReduce Turing Complete?

I have two questions regarding the MapReduce framework and Turing Completeness:

  1. First of all, since MapReduce isn't an actual programming language (it's more like a set of rules for processing data), does it make any sense to talk about Turing Completeness?
  2. If it actually makes sense, is the MapReduce system Turing Complete?
Solution

    1. Turing completeness applies to instruction sets (i.e. programming languages) but MapReduce is a programming model. So this question only makes sense if you specify the exact set of instructions available in the map and reduce phases.

    2. My bet is that MapReduce for a given instruction set is Turing complete if and only if the instruction set is: If the instruction set is Turing complete then adding MapReduce into the mix doesn't change anything. If the instruction set is not Turing complete there is nothing in the map or reduce phase that would make it Turing complete.