Accueil / Publications / On the parallel computation thesis

On the parallel computation thesis


Nachum Dershowitz, Eugenia Falkovich-Derzhavetz, "On the parallel computation thesis", in Logic Journal of IGPL, Oxford University Press, 2016.


We develop a generic programming language for parallel algorithms, one that works for all data structures and control structures. We show that any parallel algorithm satisfying intuitively-appealing postulates can be modelled by a collection of cells, each of which is an abstract state machine, augmented with the ability to spawn new cells. The cells all run the same algorithm and communicate via a shared global memory. Using a formal definition of what makes such an algorithm effective, we prove the validity of the Parallel Computation Thesis, according to which all reasonable parallel models of computation have roughly equivalent running times.

Full text (PDF on

Machine Learning Tools for Historical Documents
01 octobre 2015 - 30 juin 2016
30 juin 2016
Nachum Dershowitz
Époque contemporaine (1789-...)
Monde ou sans région
Nachum Dershowitz et al.