Home / Publications / On the parallel computation thesis

Publications

On the parallel computation thesis

FacebookTwitter

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

Abstract

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 (Oxfordjournals.org)

Machine Learning Tools for Historical Documents
01 October 2015 - 30 June 2016
30 June 2016
506
Nachum Dershowitz
4154
2016
Digital humanities
Contemporary period (1789-…)
World or no region
Nachum Dershowitz et al.