On the philosophical basis of computational theories

by Oded Goldreich

[Feb. 2014]

In this short note we exemplify the problems that may arise when presenting computational theories based on theories of natural phenomena that lack computational complexity components. These problems may arise when the latter theories refers to environments of unbounded size. In contrast, the standard theory of computation (e.g., based on the model of Turing machines) refer implicitly to theories about bounded portions of the environment (e.g., the mechanics or electricity of possible implementations of a Turing machine).

We start by recalling the postulates that underly all reasonable computational models, as presented in standard computational classes and texts. We then focus on exemplifying what happens when these postulates are ignored.

Back to Oded's page of essays and opinions or to Oded's homepage.