On Computation

In an old entry of this blog, I had criticised a blog post who was a review of my book. The author of that review posted a new post entitled Deflating Hypercomputation, where he advertizes his paper The Physical Church–Turing Thesis: Modest or Bold? This paper is a defense of a "modest version of the Physical Church-Turing thesis":

Any function that is physically computable is  Turing computable.

The next question is, of course, what is meant by physical computable? Gualtiero Piccinini, that is, the author of this paper, proposes that "if a physical process is a computation, it can be used by a finite observer to obtain the desired values of a function". Now, finite observers are "human beings and any other intelligent beings of similarly bounded capacities". In an explanation of this description, he includes among observers beings that are located in spacetimes that are (currently?) inaccessible to humans (so hypercomputation near a black hole is not a fantasy!).  Physical processes must be executable, automatic, uniform, and reliable in order to be usable. In particular,

• executable means that the process can be started by the observer to generate results;
• automatic means that the process is mechanical;
• uniform means that the process is the same for different inputs; and
• reliable means that it generates correct results in the course of execution.

Then he proposes some other sub-criteria that should be used to define the notion of physical process. However, this definition is surprisingly similar to the definition of an algorithm that follows and which is borrowed from Fundamentals of data structures in PASCAL:

Definition An algorithm is a finite set of instructions that if followed, accomplish a particular task. In addition, every algorithm must satisfy the following criteria:

1. input: there are zero or more quantities that are externally supplied;
2. output: at least one quantity is produced;
3. definiteness: each instruction must be clear and unambiguous;
4. finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps;
5. effectiveness: every instruction must be sufficiently basic that it can in principle be carried out by a person using only pencil and paper. It is not enough that each operation be defined, but it must also be feasible.

In different words, he is not proposing something entirely new.  Now in my book I had used the following definition of computation, which I have borrowed from Computation is just interpretable symbol manipulation; cognition isn't:

Definition Computation is an implementation-independent, systematically interpretable, symbol manipulation process.

Obviously, this definition is far more general and it can be applied in cases where Piccinini's formulation fails. Also, I have used this definition to rule out "computing" walls and stones as genuine computing devices. In conclusion, Piccinini "response" shows that he did not actually read the book.