WHAT IS THE LOGIC OF PARALLEL PROCESSING?
Jaakko Hintikka, Gabriel Sandu · International Journal of Foundations of Computer Science · 1995
We can associate with each consistent formula F of first-order logic a computing device as its representation. This computing device is one which will calculate the Skolem functions of F (for a denumerable domain). When two such devices are operating in parallel, the resulting architecture does not necessarily represent any ordinary first-order formula, but it will represent a formula in independence-friendly (IF) logic, which hence can be considered as a true logic of parallel processing. In order to preserve representability by a digital automaton (Turing machine), a nonstandard (constructivistic) interpretation of the logic in question has to be adopted. It is obtained by restricting the Skolem functions available to verify a formula F to recursive ones, as in the Gödel’s Dialectica interpretation.