Thoughts on the Nature of Computation

I am concerned with two question here:

(A) What is Computation, in the most general sense? What does the brain and  Conway's Game of Life have in common?
(B) Is (mathematical) Reasoning some sort of Computation?

In the last blog entry I speculated whether the concept computation is more restrictive than Mathematics, and whether laws of nature can be expressed in terms of computation.

What is the difference between Computation and Mathematics? Of course, Mathematics is concerned with proofs, whereas Computation is concerned with algorithms. But is there really a difference?

[Before you proceed, an important Note: I am not concerned here with scientific computing, which is about how to use computational resources in the most intelligent way. The notion of Computation I am up to is not concerned with numerics, parallel computing and the like, but about the nature of an abstract algorithmic process, not necessarily in time. I want to think about Computation in a hardware-independent way.]

Let us start with Mathematics: The difference between Mathematics and Physics in my view is:
Mathematics is about all (logically) possible Worlds, whereas Physics is about the actual World.

Convential (predicate) logic + some set of mathematical axioms (for sets, numbers, and usually some more exotic ones as well) leads to standard mathematics. Given that one assumes these axioms to be self-evident for any intellectual being, mathematics should be universal, that is each civilization in the universe should find the same mathematical truths.

But what is Computation then?  Let me contrast Computation and Mathematics by a couple of examples:
(1) Mathematicians want to know whether a set (of, say, numbers) is finite or infinite.
Computation is interested to give a description on how to calculate the elements of this set (e.g. prime numbers).
(2) Mathematicians want to prove that there exists a solution to some equation or that the solution is unique. If it is unique, they give the expression explicitly. Two typical examples are
Diophantine equations or general expressions for the solution of an algebraic equation (e.g. the p-q-formula), or differential equations.
Computation solves these equations for specific parameters or initial conditions (e.g. iterative methods or matrix inversion)
(3) Mathematicians want to enumerate all possible cases of (classification of Graphs, Riemann surfaces, Lie-algebras, etc.)
Computation is concerned with calculating the numbers which characterize a particular structure in this classification (e.g. the Euler characteristics)

These examples shall illustrate: Computation, in terms of algorithms (and maybe something else), is of course more than just the calculation of numbers. But it never questions the framework, the set of theorems, it uses them.

Computer algebra programs such as Mathematica are just such well-defined frameworks for Computing, but they are not suitable to prove mathematical theorems. They can only give hints on how to prove something, as a heuristics.

Here are various candidate descriptions of what Compuatation is in contrast to Mathematics:

1. Computation is a subfield of Mathematics, in particular it is applied mathematics
2. Mathematics is about theorems, Computation is about its consequences.
3. Computation is what Computability Theory and Algorithmic Information Theory is about.
4. Computation is (sophisticated) Counting, like manipulating an abacus.

To each of these descriptions there are counter-arguments:

ad 1. & 2. Computation can be an essential part of a mathematical proof. For example the four-color theorem was proven with the help of a computer program. Computer-assisted proofs are not accepted by all mathematicians, and it is important to understand why.
Computation can also address mathematical theorems themselves: automated theorem provers are programs that do some sort of Computation (here, the framework is not algebra, but prediacte logic) in order to prove theorems, not to apply them.

ad 3. Computability theory is concerned with questions like the halting problem. It can tell what kind of algorithms produce a result within a finite number of elementary steps. Algorithmic information theory is about the complexity of algorithms. Both are important questions, but they are rather Meta-theories of Computation, categorizing specific computations into various groups. They do not address the content of computation.
ad 4. Counting is a mental activity. An abacus is just a tool to do so.
A machine that is able to perform computations, say a Turing machine, can be described by states which can be mapped on the natural numbers. Each of the possible instructions acting on a set of data can be regarded as an elementary arithmetic step like an increment. However, the program which tells the machine what to do is given as an input as well, and the complexity of what the machine does is encoded in the program. Hence Computing should focus on the algorithm itself, not on the realization of the algorithm in a specific setup.

I would like to argue in favor of a view that there are systems which can be described purely in mathematical terms, but which are too complex to study. Mathematics is somehow concerned with the simple truths, but there are also complicated truths out there, which cannot be found withouth some sort of computation, because the mental capacities of humans for reasoning have limitations.
This is of course along the line of thought of Steven Wolfram, "A New Kind of Science", however, Computation, in my view is not a new science at all, but it should be a paradigm to understand the common features of various phenomena such as evolution, the connection of brain and mind, and emergent properties of complex systems in general.

I conclude that the concept of Computation is context-sensitive, it requires a system of formal rules; Mathematics, in contrast, is universal and hence context-free. One might object that logic sums up the laws of thinking, but I am convinced that it is the law of thinking of man, but of any intelligent being.

This brings me to my last topic, the question whether reasoning is some sort of computation... Reasoning is what minds do - not brains, if there is a difference - but we have seen that there are programs of automated reasoning.
This question is not about whether the brain is something like a computer. I take it for granted that the brain processes inputs and generates outputs via a neural network. If this neural network was static, it could be simply characterized by an high-dimensional function relating inputs to outputs.
The question is whether this real time dynamics of that neural network has anything to do with the content of the mind, and if so, whether this process can be characterized as a specific computation.

If we do not know what Computation really is, we cannot reject the hypothesis that our mental states are a result of Computing.

I apologize to the reader that these thoughts were not discussed systematically here, and touching so many different subjects might have caused some confusion. I will address some of the raised issues in greater detail soon.

-----

PS: One last comment: not every physical phenomenon that can be studied via computer simulations (the weather/climate, lattice QCD) is a case of (exact) Computing  I have in mind here. These simulations use approximations (involving rounding errors) and/or pseudo random numbers (such as in Monte Carlo simulations). In actual simulations, one often has to trade accuracy for efficiency.
I rather think of computations like exact enumerations, which produce unambiguous answers without statistical errors.