-1

Such binary operator returns an output in the same set as the two inputs and is a general computer program.

Such general computer program is used in the reduce phase of some computations I run. Knowing ahead of time whether my general computer program is commutative is a necessary requirement to decide whether the reduce data has be processed in a specific order or not.

I'd like to know whether it is possible to ascertain logically that such an operator is commutative without doing an exhaustive search of all the pair-wise combinations.

Giorgio
  • 3
  • It's hard to tell what your Question is. I take it you mean a binary operation takes two arguments and returns an output in the same set. Some such operations are commutative and some are not. Determining "whether it is commutative" is possible but depends on how the operation is defined, and you've not shared any information with Readers about how an operation will be defined. – hardmath Mar 21 '18 at 23:21
  • Assuming your operator is specified as a general computer program, being commutative is a nontrivial property of the program's behavior, so Rice's theorem gives a (provable) answer in the negative. If there is some more restrictive way it could be specified, it is possible that you could make some sort of determination. – Micah Mar 22 '18 at 00:29

1 Answers1

0

I assume you mean binary functions. If your range of inputs is finite, then you can check all possible input pairs to check commutativity. Otherwise, no; in general there is not an easy check for commutativity.

yammatack
  • 130
  • Yes, sorry, I meant my question to be restricted to binary functions. I edited my question accordingly. Is there no general way to prove this because such method has not been found, yet, or because it has been proven that such a general method cannot exist? – Giorgio Mar 21 '18 at 22:22
  • I suspect that a general method t9 show communitiverty could be leveraged to solve the halting problem. – Q the Platypus Mar 21 '18 at 22:52