Is computation independent of hardware?

Question

We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is not dependent of how we make our computers, then does the same principle which apply to a computer apply to how brain works? I want to know if computation is an abstract object which then is realized as computers. In other words, if we visit some alien civilization we expect that our mathematicians and physicists understand the alien physics and math. Is it the same as with the notion or concept of computation? It seems that in order to consider computation first we need consider a realization of a machine or a model. For example according to the first two lines of this question there are Turing machine, circuits and lambda calculation. How do we know that there is not another way of computation? For example, the way the brain works and does computation might not be describable by the computation which we consider in Turing machine.

To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry.

Answer 1

To answer the title question, yes, computation is independent of hardware. Computation is defined by the transformation of information, not by how it's embedded in the real world. This is easy to see: all the computation models have a mathematical formulation, and you can write mathematics as symbols on paper. In fact, many models of computation, such as the lambda calculus (1936) and Turing machines (1936) were invented before there were general-purpose computing machines (there were numeric calculators and data sorters, but programmable machines didn't exist until the 1940s).

It is possible to model today's computers by mathematical tools. They're just finite-state machines, after all. There are a lot of states, so a complete pen-and-paper representation is not feasible, but if you only model the part that you're interested in, that can be within reach.

As to whether there is only a single notion of computation, we don't know. We think so: that's the Church-Turing thesis. We think so because we've invented a lot of models of computation, and they all turned out to be equivalent. Some of them are easier to work with than others, or more directly applicable to certain problems, or are a closer match for certain computing hardware (e.g. in terms of performance or locality). But they can express the same computations.

Are Turing machines (or any of the equivalent concepts) the last word on the topic? We don't know. We certainly have weaker models of computation, but we think of them as restricted computation. And we have stronger models of computation, but we think of them as “magic“ — we can reason about them, but we have no idea how they could be implemented.

Is the brain a Turing machine? That's a question about the brain, and we don't know. We know that it's at least as powerful as a Turing machine, since it can simulate one. We are very far from being able to accurately simulate a brain with a Turing machine, but we don't know whether that's a matter of scale (a brain has tens of millions of neurons — a PC doesn't have enough memory to even store all the connexions). We do tend to think of brains as being more powerful than computers — when a problem is undecidable (in the Turing computation sense), we offer to solve it by thinking, but that doesn't answer the question. When we solve a problem by thinking, the solution is expressible in Turing machine terms. The problem solving method, however, may or may not be more powerful than Turing machines.

Would aliens have the same notion of computations? We don't know. We think so — mathematics seems universal to us — but that's a question about aliens, and since we don't know anything about aliens except what your imagination tells us, we can't answer it.

Answer 2

How do we know that there is not another way of computation?

We do not. Well, we know plenty of Turing-complete and less powerful models. We have also thought about more powerful models but we don't know how to build them in reality.

The Church-Turing thesis is our best guess but it can not be proven.

So you are asking for speculation resp. trivialities like this:

If we had physics that allowed us to store and manipulate real numbers, we could implement Real-RAMs which are strictly more powerful than Turing machines.

Answer 3

"To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry."

We defined the existence of certain numbers such as the Set of Integers and the Set of Real Numbers via axioms. We have created notions such as variables and relations. We can create linear relations such as linear equations based on these sets. We have proofs (using methods such as the method of substitution) and can solve linear systems of relations in several ways. Every solution is a form of computation. Thus there are axioms (such as those used for sets) which we have built theories of computations.

"Is computation independent of the hardware we use?"

We have adapted the solutions to situations with constraints. For example, there is no practical computer that can represent the elements of the set of Real Numbers or the elements of the Set of Integers. Thus we have fields such as Numerical Methods/Analysis to study how solutions behave using the Set of Floating Point Numbers instead of using the Set of Real Numbers. Thus some computations are dependent on constraints.

Answer 4

in fact,no have the thing to calling the computation.it's just the transformation of energy to some phenomena.but in my opinion,things look like don't depend on the cause or consequence,it's random.Because in the quantum scale,we have no intractable or get out of zeno paradox in the transfer the energy.so they would been in disjointed.so it's no difference if say the event is random,so does computing.