What is the most general definition of computation, and how does it differ from the more common definitions of it?

What is the most general definition of computation and how does it differ from the most common definition of it? I am thinking the most common definition implies the use of a computer (but some include the mind?), and the most general definition doesn't imply the use of a computer. What does the philosophy of information say about this?

  • Better for cs.stackexchange.com perhaps. Turing defined computation in 1936 and nobody has found a better definition since. Computer scientists study all kinds of interesting variations on the theme. – user4894 Oct 27 '20 at 4:31
  • Whether the definition is "most general" does not depend on whether computers are featured in it. The Church-Turing thesis is "computation is whatever can be converted into a program executable on a Turing machine", a virtual "computer" with very basic formally defined design. Other definitions, some not involving computers, are provably equivalent to it. For example, it can be rephrased as "computation is whatever outputs a general recursive function of its inputs". – Conifold Oct 27 '20 at 5:17
  • Welcome to SE Philosophy! Thanks for your contribution. Please take a quick moment to take the tour or find help. You can perform searches here or seek additional clarification at the meta site. Don't forget, when someone has answered your question, you can click on the checkmark to reward the contributor. – J D Oct 27 '20 at 16:57
  • A good place to start on the nature of computation is SEP: Information. An authoritative book is The Philosophy of Information by Luciano Floridi. In intro texts, computation is generally defined as one of four steps in the information processing cycle: most generally, input, output, processing, and storage. – J D Oct 27 '20 at 17:08
  • You are right that the layperson tends to think of digital computers, but the notion extends much more broadly among professional thinkers. Many psychologists embrace theories modeled on digital computers./wiki/Information_processing_theory – J D Oct 27 '20 at 17:13

Short Answer

Computation in the lay sense has a few meanings: to use math, to calculate, or the use of a computer. Fact is, in the 19th century, computers were humans who did arithmetic for a living. There are more modern specific definitions pertaining to computing and information technology, and every introductory textbook for IT/MIS (and many general psychology textbooks) offers the information processing cycle (input, processing, storage, and data) which is a generic definition to show what computation does: It is a step in the flow of information that changes data.

In computer science, Alan Turing kicked off formal definitions of computing that draw from formal languages, automata, computability, and formal logic. Psychologists and neurologists also have models of thought and neural computation based on digital computers. Lastly, philosophers of information argue that the notion of information and computation is still not well understood and have various notions of computation given their respective definitions of information.

Long Answer

According to the general use dictionary Merriam-Webster:

Definition of compute

transitive verb
: to determine especially by mathematical means Compute the area of the triangle. also : to determine or calculate by means of a computer computing pi to over one billion places

intransitive verb
1 : to make calculation : reckon They compute by weight in selling grain.
2 : to use a computer

Here we see the lay definition at work with its various senses related to mathematics and digital and mechanical computers. Computing is not only an activity related to doing math, it's been broadened to mean using a computer for anything such as playing video games.

In introductory texts, computing is the processing stage of the information processing cycle, and is broad by including any transformation of data in a system. For example, if one attaches a USB drive and inputs files from the drive to the machine, then processing can be interpreted as ANY task done on the machine and depends on the context. The classic model for ICT is the ISO OSI model with it's 7 layers: application, presentation, session, transport, networking, data-link, and physical layers. The unit of data is different at every level. At the physical level, data consists of bits. In this case, computing consists of executing machine instructions to manipulate those bits in the ALU/CU/MMU, a portion of the CPU. At the network layer, the measure of data is the packet, and computing involves manipulating packets. So, this more sophisticated model allows discussion about computing in terms of a 7-layered ontology. Of course, there are other models such as the 4-layered model in TCP/IP stacks.

The gold standard in computer science is the notion of the Turing machine though there are many equivalent formal systems such as the lambda calculus. One excellent treatise on the topic is Computability and Logic by Boolos et al. The text purports itself to be a book on computability theory. In fact, the general notion of computability boasts many models. From WP:

Lambda calculus...
Register machine...
Turing machine...
Multitape Turing machine...
Deterministic finite automaton (DFA)...
Nondeterministic finite automaton (NFA)...
Pushdown automaton...

Each of these has a very specific set-theoretic and functional definition to accomplish different types of computation.

Lastly, Luciano Floridi in his book The Philosophy of Information seeks to broaden claims about computation beyond formal computability, and charges philosophy with giving short shrift to the philosophical basis of computation and information. To wit on page 17:

Among our mundane and technical concepts, information is currently one of the most important, widely used yet least understood. So far, philosophers have done comparatively little work about it and its cognate concepts...

Two pages later:

If we restrict our attention to [philosophy of information (PI)], we may consider, for example, the trust placed by many philosophers of mind in computational and informational approaches... In cases like these, PI can work as a powerful methodology to debug past philosop[hical mistakes... The analysis of the misuse of the Church-Turing thesis and of the concept of Universal Turing Machine provides an instructive example...

He goes on page 33 to talk about a unified theory of information to broaden computation and information to the widest possible definition invoking the Wittgensteinian notion of family resemblance to clarify his notion of definition.

  • Great answer. Only missing a nod to related concepts in physics. – CriglCragl Nov 27 '20 at 13:52
  • 1
    @CriglCragl Thanks. I do have Seth Lloyd's Programming the Universe, and I omitted that class of theories out of my empirical bias. I'll revise this weekend. – J D Nov 27 '20 at 14:46

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.