1

What are the different kinds of computation that exist? From what I can see, there are two kinds:

  • Computation based on non-electric and analog devices: abacuses, human brain, calculator
  • Computation based on digital devices: computers

I am wondering if there are more kinds of computation or whether philosophers use different criteria to distinguish between different kinds of computation.

20
  • To discuss a "kind of computation" you need to specify a category with respect to which the "kinds" are taken. The specific examples you give correspond not even to the computation itself but to its implementation, digital or analog. Artificial neural networks and quantum computer implementations are arguably distinct from both. The classification intrinsic to computation itself is based on computational complexity.
    – Conifold
    Jan 1 at 8:02
  • 1
    @Conifold Don't neural nets run on perfectly conventional hardware? They're a clever way of organizing a computation, but they're no different in principle than a spreadsheet or word processor. The idea of weighting nodes is not new, it's an old optimization technique. Likewise quantum computers offer no improvement in what can be computed. As you admit, the only difference is in efficiency. Complexity is not computability, and the computational limits of Turing machines have not been breached in any way.
    – user4894
    Jan 1 at 8:18
  • 3
    Computing using pencil and paper methods or an abacus is not different in principle from using a classical electronic computer, so I don't see why we would call it a different kind of computation. The difference is just speed. Quantum computers can solve problems in a different complexity class to those solvable by a classical computer: there is evidence that BQP is a strict superset of PH. Analog computers are quite different, but ultimately they run into limitations of precision of measurement and they require calibration, which make them inconvenient and impractical.
    – Bumble
    Jan 1 at 13:32
  • Do you do the computations with pencil or pen? Paper or animal hides? Left-to-right, right-to-left, top-to-bottom, bottom-to-top?
    – Hot Licks
    Jan 1 at 15:21
  • 2
    @Bumble Quantum computers give absolutely no improvement in computability, only in complexity. I hope you agree. Anything that a quantum computer can compute can already be computed by a classical one. The proof is that quantum computers can be simulated (albeit slowly) by classical ones.
    – user4894
    Jan 1 at 19:37
0

Types of computation are not based on the type of device but on the way in which information is structured and processed. The principal types are analogue, digital and quantum. (What follows is updated following comments and downvotes made).

For example an abacus is a digital (ON/OFF) computer, albeit using decimal word lengths rather than bit-count word lengths. Some early electronic computers used the same decimal system, as did Babbage's mechanical Difference Engine of the late 19th century. A box of counters, a pencil and a sheet of paper are an even simpler, though rather more flexible, digital computer. Powerful ones just happen to be electronic these days.

By contrast an analogue computer processes signals (numbers) which are continuously variable across the working range. Analogue computers have been mechanical as in the computing gunsights fitted to American bombers in WWII, electrical as in some early aircraft control systems, or even hydraulic as in the first ever computational model of the UK economy.

A quantum computer operates on a third principle again. Where a digital process is discrete and analog is continuous, a quantum process is a superposition of all possibilities. A quantum computer typically comprises a set of components called qbits, which are linked or entangled together in such a way as to collectively processes a near-infinite superposition of intangible possibilities before they find the most likely answer. Other more exotic quantum architectures also exist, which are not bound by the "bit" model necessary to communicate with a discrete-logic controller. Although the quantum processor is surrounded by a conventional digital control system, the core processor itself is anything but digital. These devices are at a very early stage of development and to say more requires a degree in advanced ... - you know, I don't even know what you do need to know.

The human or animal brain is, broadly speaking, an analogue device in terms of its chemistry but digital in the way it encodes nerve signals as pulse trains. Nobel prize-winning physicist and mathematician Roger Penrose is among those who have argued that neural processing, especially memory, also depends on quantum phenomena.

A neural network is a technological architecture which seeks to emulate certain features of human brain activity. Neural networks are commonly used for AI applications involving big data and deep learning. Typically, at some point a digital device will be used to simulate an analogue function (which is itself an approximation of the original neural digital pulse train). Theoretically an analogue device known as a memristor would greatly improve circuit efficiency, but only experimental memristor-like circuit modules have yet been developed. Working systems remain all-digital emulations.

10
  • 4
    Quantum computers and neural networks can be implemented on classical computers. Quantum computers are so implemented as proof of concept; and neural nets always are. They do not constitute new types of computing, any more than laptops over keypunch machines do. OP asked about computation, not complexity classes.
    – user4894
    Jan 1 at 19:39
  • 1
    You're just misinformed or wrong. Nothing can be computed by a quantum computer that can not already be computed on a classical one. The proof, which I already explained, is that one can implement a quantum computer on a conventional one. There are differences in complexity class for a limited set of problems such as integer factorization. But there is no increase in computation ability. You are confusing complexity with computability. In the case of neural nets the case is even more clear because neural nets are ALWAYS implemented on conventional computers.
    – user4894
    Jan 2 at 19:22
  • 1
    ps -- Quantum supremacy is a concept of complexity, not computability. It refers to how efficiently a computation can be done; for example, the difference between polynomial time and exponential time. Both are computable, but as the size of the input grows, exponential problems take longer and longer to run. As a striking example, Shor's algorithm is a quantum algorithm to factor integers in polynomial time. That's a fantastic breakthrough; but it does NOT offer any improvement in computability; only in complexity. If someone found a mode of computation beyond the Turing machine it would be
    – user4894
    Jan 2 at 20:01
  • 1
    (cont) a world-shaking breakthrough that would violate the Church-Turing thesis. en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis. This has not happened at all. Anything a quantum computer can compute can already be computed with pencil and paper by a person emulating a Turing machine, a model of computation created in 1936 by Turing and never exceeded. I hope you will come to appreciate these points as the breathless quantum and AI hype trains roll down the tracks. Both are perfectly classical computations in the sense of Turing.
    – user4894
    Jan 2 at 20:03
  • 2
    Why should I give an answer, you've already earned the checkmark. Quick checkmarks to wrong answers are one of the problems with this site. Quick checkmarks in general preclude others from answering; and checkmarks to wrong answers confuse everybody, especially the OP as has happened here. I'm disappointed that you refuse to acknowledge the distinction between computability and complexity. In no effing way does Penrose think quantum computers disprove the Church-Turing thesis. You keep doubling and tripling down on your misconceptions. There is no Nobel prize in mathematics, of course.
    – user4894
    Jan 2 at 21:08
4

Well, there are different kinds of physical computers as the other answer touched on. But if you're asking about types of computation, then in mathematics and computer science this often refers to formal systems that are able to calculate different classes of functions. See the article on automata theory which highlights four important models of computation, and then goes on to describe a lot more.

  • Combinational logic corresponds to Boolean expressions, or functions that can be calculated by a single pass through a feed-forward logic circuit.
  • Finite state machines are computers with only a finite set of internal states and a finite possible set of inputs. After each input, a finite state machine changes to a new state, depending on its current state and the input. They can tell whether a string is part of a specific "regular language" - similar to what a regex can do.
  • Pushdown automata are computers with a finite state machine that can also interact with a stack of unlimited size. A pushdown automaton can only push or pop the top element of the stack, it can't look at an element below the top without popping the elements above it first. Pushdown automata can tell whether a string is part of a context free language.
  • Turing machines are computers with a finite state machine that can interact with a tape of unlimited size. A Turing machine can read or write to the "current" tape cell, or it can move the current tape cell left or right.

These are four important and common models of computation, but there are more. There are the primitive recursive functions which can calculate anything a pushdown automaton can calculate, but can't calculate as much as a Turing machine. There are hypercomputation and oracle machines which are more powerful than Turing machines, but cannot be physically implemented as far as we know. There are also many models of computation that are equivalent to some already mentioned, many of which are laid out in the article on automata theory. Some examples are lambda calculus, combinatory logic, cellular automata, non-deterministic Turing machines, Post canonical systems.

1
  • Thank you so much for posting this. This is the response that should be checkmarked, as it's the correct answer.
    – user4894
    Jan 2 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.