Does there exist a problem for which no existing solution can be parallelized on a Turing machine?

Question

I'm asking for problems for which we know there exists a solution for which an equivalent parallel program cannot be written on a Turing machine.

Alternatively, have we proven the opposite to be true - that for every problem, there exists at least one parallelizable solution?

Answer 1

The question is not precisely defined, so it's not really amenable to a precise technical answer at this stage. But a common view/hypothesis/expectation is that there exist problems that are inherently sequential, in the sense that they cannot be substantially sped up on a parallel computer, no matter how many parallel processors you have. A weak version of this view is implied by the conjecture that $NC \ne P$ (see https://en.wikipedia.org/wiki/NC_%28complexity%29), which is conjectured but not known to hold. In particular, P-complete problems are good candidates for problems that don't benefit much from parallelization. There are stronger versions of this view; for instance, in cryptography, timelock puzzles utilize functions that are believed to be inherently sequential: a parallel processor cannot speed them up very much.