What is computation?

Abstract

Three conditions are usually given that must be satisfied by a process in order for it to be called a computation, namely, there must exist a finite length algorithm for the process, the algorithm must terminate in finite time for valid inputs and return a valid output and, finally, the algorithm must never return an output for invalid inputs. These three conditions are advanced as being necessary and sufficient for the process to be computable by a universal model of computation. In fact, these conditions are neither necessary nor sufficient. On the one hand, recently defined paradigms show how certain processes that do not satisfy one or more of the aforementioned properties can indeed be carried out in principle on new, more powerful, types of computers, and hence can be considered as computations. Thus, the conditions are not necessary. On the other hand, contemporary work in unconventional computation has demonstrated the existence of processes that satisfy the three stated conditions, yet contradict the Church–Turing thesis and, more generally, the principle of universality in computer science. Thus, the conditions are not sufficient.

Keywords::

• Church–Turing thesis
• hypercomputation
• natural computation
• non-universality in computation
• parallel computation
• unconventional computation