Computation in Physical Systems

First published Wed Jul 21, 2010; substantive revision Wed Aug 20, 2025

In our ordinary discourse, we distinguish between physical systemsthat perform computations, such as computers and calculators, andphysical systems that don’t, such as rocks. Among computingdevices, we distinguish between more and less powerful ones. Thesedistinctions affect our behavior: if a device is computationally morepowerful than another, we pay more money for it. What grounds thesedistinctions? What is the principled difference, if there is one,between a rock and a calculator, or between a calculator and acomputer? Answering these questions is more difficult than it mayseem.

In addition to our ordinary discourse, computation is central to manysciences. Computer scientists design, build, and program computers.But again, what counts as a computer? If a salesperson sold you anordinary rock as a computer, you should probably get your money back.Again, what does the rock lack that a genuine computer has?

How powerful a computer can you build? Can you build a machine thatcomputes anything you wish? Although it is often said that moderncomputers can compute anything (i.e., any function defined over adenumerable domain, such as the natural numbers or strings of lettersfrom a finite alphabet), this is incorrect. Ordinary computers cancompute only a tiny subset of all functions. Is it physically possibleto do better? Which functions are physically computable? Thesequestions are bound up with the foundations of physics.

Computation is also central to the mind sciences, and perhaps otherareas of biology. According to the computational theory of cognition,cognition is a kind of computation: the behavior of cognitive systemsis causally explained by the computations they perform. In order totest a computational theory of something, we need to know what countsas a computation in a physical system. Once again, the nature ofphysical computation lies at the foundation of empirical science.

1. Abstract Computation and Concrete Computation

Computation may be studied mathematically by formally definingcomputational objects, such as algorithms and Turing machines, andproving theorems about their properties. The mathematical theory ofcomputation is a well-established branch of mathematics. It deals withcomputation in the abstract, without worrying much about physicalimplementation.

By contrast, most uses of computation in science and ordinary practicedeal with concrete computation: computation in concrete physicalsystems such as computers and brains. Concrete computation is closelyrelated to abstract computation: we speak of physical systems asrunning an algorithm or as implementing a Turing machine, for example.But the relationship between concrete computation and abstractcomputation is not part of the mathematical theory of computation perse and requires further investigation (cf. Curtis-Trudel 2022 for anargument that abstract and concrete computation cannot be given aunified account). Questions about concrete computation are the mainsubject of this entry. Nevertheless, it is important to bear in mindsome basic mathematical results.

An important notion of computation is that ofdigitalcomputation, which Alan Turing, Kurt Gödel, AlonzoChurch, Emil Post, and Stephen Kleene formalized in the 1930s. Theirwork investigated the foundations of mathematics. One crucial questionwas whether first order logic isdecidable — whetherthere is an algorithm that determines whether any given first orderlogical formula is a theorem.

Both Turing (1936–7) and Church (1936) proved that the answer isnegative: there is no such algorithm. To show this, they offeredprecise characterizations of the informal notion of algorithmicallycomputable function (over a denumerable domain). Turing did so interms of so-called Turing machines (TMs) — devices thatmanipulate discrete symbols written on a tape in accordance withfinitely many instructions. Other logicians did the same thing —they formalized the notion of algorithmically computable function— in terms of other notions, such as general recursive functionsand λ-definable functions.

To their surprise, all such notions turned out to be extensionallyequivalent, that is, any function computable within any of theseformalisms is computable within any of the others. This is evidencethat their quest for a precise definition of “algorithm”or “algorithmically computable function” had beensuccessful. The resulting view — that TMs and other equivalentformalisms capture the informal notion of algorithm for computingfunctions over a denumerable domain — is now known as theChurch-Turing thesis (more on this in Section 4). The study ofcomputable functions, made possible by the work of Turingetal., is part of the mathematical theory of computation.

The theoretical significance of Turinget al.’s notionof computation can hardly be overstated. As Gödel pointed out (ina lecture following one by Tarski):

Tarski has stressed in his lecture (and I think justly) the greatimportance of the concept of general recursiveness (or Turing’scomputability). It seems to me that this importance is largely due tothe fact that with this concept one has for the first time succeededin giving an absolute definition of an interesting epistemologicalnotion, i.e., one not depending on the formalism chosen. (Gödel1946, 84)

Turing also showed that there are universal TMs — machines thatcan compute any function computable by any other TM. Universal TMs dothis by executing instructions that encode the behavior of the machinethey simulate. Assuming the Church-Turing thesis, universal TMs cancompute any function computable by algorithm. This result issignificant for computer science: you don’t need to builddifferent computers for different functions; one universal computerwill suffice to compute any computable function. Modern digitalcomputers are universal in this sense: they can compute any functioncomputable by algorithm for as long as they have time and memory.(Strictly speaking, a universal machine has an unbounded memory,whereas digital computer memories can be extended but notindefinitely, so they are not unbounded.)

The above result should not be confused with the common claim thatcomputers can computeanything. This claim is false: anotherimportant result of computability theory is that most functions arenot computable by TMs (and hence, by digital computers). TMscompute functions defined over denumerable domains, such as strings ofletters from a finite alphabet. There are uncountably many suchfunctions. But there are only countably many TMs; you can enumerateTMs by enumerating all lists of TM instructions. Since an uncountableinfinity is much larger than a countable one, it follows that TMs (andhence digital computers) can compute only a tiny portion of allfunctions (over denumerable domains, such as natural numbers orstrings of letters).

TMs and most modern computers are known as (classical)digitalcomputers, that is, computers that manipulate strings ofdiscrete, unambiguously distinguishable states by performing discreteoperations that are sensitive to the position of a state within thestring. Digital computers are sometimes contrasted withanalogcomputers, which manipulate variables thatcan be continuous via operations such as integration anddifferentiation. Continuous variables are variables that can changetheir value continuously over time while taking any value within acertain interval. Analog computers are used primarily to solve certainsystems of differential equations (Pour-El 1974, Rubel 1993).

Classical digital computers may also be contrasted withquantumcomputers. Quantum computers manipulatequantum states called qudits (usuallybinary qudits, known asqubits). Unlike the computational states of digital computers, qubitsare not unambiguously distinguishable from one another. This entrywill focus primarily on classical computation. For more on quantumcomputation, see theentry on quantum computing.

The same objects studied in the mathematical theory of computation— TMs, algorithms, and so on — are typically said to beimplemented by concrete physical systems. This poses a problem: howcan a concrete, physical system perform a computation when computationis defined by an abstract mathematical formalism? This may be calledthe problem of computational implementation.

The problem of computational implementation may be formulated in acouple of different ways. Platonists interpret the formalisms ofcomputability theory as defining abstractobjects. Accordingto platonists, TMs, algorithms, and the like are abstract objects. Buthow can a concrete physical system implement an abstract object?Non-platonists treat the formalisms of computability theory asabstract computationaldescriptions. But how can a concretephysical system satisfy an abstract computational description in a waythat turns it into a system that performs the computation defined bythe computational description? Regardless of how the problem ofcomputational implementation is formulated, solving it requires anaccount of concrete computation — an account of what it takesfor a physical system to implement a given computation.

A closely related problem is that of distinguishing between physicalsystems such as digital computers, which appear to compute, andphysical systems such as rocks, which appear not to compute. Unlikecomputers, ordinary rocks are not sold in computer stores and areusually not considered computers. Why? What do computers have thatrocks lack, such that computers compute and rocks don’t? (Ifindeed they don’t?) In other words, what properties must aphysical system have to implement computations? Different answers tothese questions give rise to different accounts of concretecomputation.

Questions on the nature of concrete computation should not be confusedwith questions about computational modeling. The dynamical evolutionof many physical systems may be described by computational models— computer programs that simulate the dynamics of a system. Thebehavior of rocks — as well as rivers, ecosystems, and planetarysystems, among many others — may well be modeledcomputationally. It doesn’t follow that the modeled systems arecomputing devices — that they themselves perform computations.Prima facie, only relatively few and quite special systems compute.Explaining what makes them special — or explaining away ourfeeling that they are special — is the job of an account ofconcrete computation.

2. Accounts of Concrete Computation

Consider a mathematically defined computational system undergoing astate transition,s₁ →s₂, and a concrete physical system undergoing astate transition,p₁ →p₂. What must be the case forp₁ →p₂ to implements₁ →s₂? Differentaccounts give different answers.

2.1 The Simple Mapping Account

One of the earliest and most influential accounts of computation, dueto Hilary Putnam (1960/1975a, 365; 1967/1975a, 433–4), wasdubbed the “simple mapping account” by Godfrey-Smith(2009). To a first approximation, the account says that anything thatis accurately described by a computational descriptionC is acomputing system implementingC. More precisely, a physicalsystemS performs computationC just in case (i)there is a mapping from the states ascribed toS by aphysical description to the states defined by computationaldescriptionC, such that (ii) the state transitions betweenthe physical states, such asp₁ →p₂, mirror the state transitions between thecomputational states, such ass₁ →s₂. Clause (ii) requires that for anycomputational state transition of the forms₁→s₂ (specified by the computationaldescriptionC), if the system is in a physical state thatmaps ontos₁, it then goes into a physical statethat maps ontos₂.

One difficulty with the formulation above is that ordinary physicaldescriptions, such as systems of differential equations, generallyascribe uncountably many states to physical systems, whereas ordinarycomputational descriptions, such as TMs tables, ascribe at mostcountably many states. Thus, there are not enough computational statesfor the physical states to map onto. One solution to this problem isto reverse the direction of the mapping, requiring a mapping of thecomputational states onto (a subset of) the physical states. A morecommon solution — often left implicit — is to selecteither a subset of the physical states or equivalence classes of thephysical states and map those onto the computational states. When thisis done, clause (i) is replaced by the following: (i′) there isa mapping froma subset of (orequivalence classesof) the states ascribed toS by a physical descriptionto the states defined by computational descriptionC.

The simple mapping account turns out to be very liberal: it attributesmany computations to many systems. In the absence of restrictions onwhich mappings are acceptable, such mappings are relatively easy tocome by. As a consequence, some have argued that every physical systemof enough complexity implements every computation from a broad class(Putnam 1988, Searle 1992). This thesis, which trivializes the claimthat something is a computing system, will be discussed in Section3.1. Meanwhile, the desire to avoid this trivialization result is onemotivation behind other accounts of concrete computation.

2.2 Restricted Mapping Accounts

One way to construct accounts of computation that are more restrictivethan the simple mapping account is to constrain acceptable mappings.As we’ve seen, according to the simple mapping account, clause(ii) requires that for any computational state transition of the forms₁ →s₂ (specified by acomputational description), if the system is in a physical state thatmaps ontos₁, it then goes into a physical statethat maps ontos₂. That second part of (ii) is amaterial conditional. It may be strengthened by turning it into alogically stronger conditional — specifically, a conditionalexpressing a relation that supports counterfactuals.

In a pure counterfactual account, clause (ii) is strengthened simplyby requiring that the physical state transitions support certaincounterfactuals (Block 1978, Maudlin 1989, Copeland 1996, Rescorla2014; Campbell and Yang 2021). In other words, a pure counterfactualaccount requires the mapping between computational and physicaldescriptions to be such that the counterfactual relations between thephysical states be isomorphic to the counterfactual relations betweenthe computational states. These counterfactuals are not satisfied bythe material conditional of clause (ii) as it appears in the simplemapping account of computation. Thus, counterfactual accounts arestronger than the simple mapping account.

An account of concrete computation in which the physical statetransitions support counterfactuals may also be generated by appealingto causal, nomic, or dispositional relations, assuming (as most peopledo) that causal, nomic, or dispositional relations supportcounterfactuals. Appealing to causation or dispositions may also haveadvantages over pure counterfactual accounts in blocking unwantedcomputational implementations (Klein 2008, 145, makes the case fordispositional versus counterfactual accounts).

In a causal account, clause (ii) is strengthened by requiring a causalrelation between the physical states: for any computational statetransition of the forms₁ →s₂ (specified by a computational description), ifthe system is in a physical state that maps ontos₁, its physical statecauses it to gointo a physical state that maps ontos₂ (Chrisley1995, Chalmers 1995, 1996, 2011, Scheutz 1999, 2001).

To this causal constraint on acceptable mappings, David Chalmers(1995, 1996, 2011) adds a further restriction (in order to avoidunlimited pancomputationalism, which is discussed in Section 3): agenuine physical implementation of a computational system must divideinto separate physical components, each of which maps onto thecomponents specified by the computational formalism. As Godfrey-Smith(2009, 293) notes, this combination of a causal and alocalizational constraint goes in the direction ofmechanistic explanation (Machamer, Darden, and Craver 2000). Accountsof computation that are explicitly based on mechanistic explanationwill be discussed in Section 2.5. For now, the causal accountsimpliciter requires only that the mappings between physical andcomputational descriptions be such that the causal relations betweenthe physical states are isomorphic to the relations between statetransitions specified by the computational description. In this sense,according to the causal account, concrete computation is the causalstructure of a physical process.

In a dispositional account, clause (ii) is strengthened by requiring adispositional relation between the physical states: for anycomputational state transition of the forms₁→s₂ (specified by a computationaldescription), if the system is in a physical state that maps ontos₁, the systemmanifests a dispositionwhose manifestation is the transition from the physical state thatmaps ontos₁ to a physical state that maps ontos₂ (Klein 2008). In other words, the dispositionalaccount requires the mapping between computational and physicaldescriptions to be such that the dispositional relations between thephysical states be isomorphic to the relations between statetransitions specified by the computational description. Thus,according to the dispositional account, concrete computation is thedispositional structure of a physical process.

Other restricted mapping accounts may restrict clause (ii) byrequiring that the physical state transitions mapping ontocomputational state transitions be lawful (Stabler 1987), thatmappings between physical and computational transitions minimize thelength of the shortest program that can return a computationaldescription given a physical description (Millhouse 2019), or thatphysical states that map onto computational states be predictive ofthe computational transitions (Horsman et al. 2014; 2018; cf. Fletcher2018).

The difference between the simple mapping account and restrictivemapping accounts may be seen by examining a simple example.

Consider a rock under the sun, early in the morning. During any timeinterval, the rock’s temperature rises. The rock goes fromtemperatureT to temperatureT+1, toT+2,toT+3. Now consider a two-state automaton that alternatesbetween its two states (call them 0 and 1) on each computational step,which will be loosely called a ‘NOT gate with feedback’hereafter for simplicity. At first, suppose the NOT gate receives‘0’ as an input; it then returns a ‘1’. Afterthe ‘1’ is fed back to the NOT gate, the gate returns a‘0’ again, and so on. The NOT gate goes back and forthbetween outputting a ‘0’ and outputting a ‘1’.Now map physical statesT andT+2 onto‘0’; then mapT+1 andT+3 onto‘1’.

According to the simple mapping account, the rock implements a NOTgate with feedback undergoing the computation represented by‘0101’.

By contast, according to the counterfactual account, the rock’sputative computational implementation is spurious, because thephysical state transitions do not support counterfactuals. If the rockwere put in stateT, it may or may not transition intoT+1 depending on whether it is morning or evening and otherextraneous factors. Since the rock’s physical state transitionsthat map onto the NOT gate’s computational state transitions donot support counterfactuals, the rock does not implement the NOT gatewith feedback according to the counterfactual account.

According to the causal and dispositional accounts too, this putativecomputational implementation is spurious, because the physical statetransitions are not due to causal or dispositional properties of therock and its states.T does not causeT+1, nor doesthe rock have a disposition to go intoT+1 when it is inT. Rather, the rock changes its state due to the action ofthe sun. Since the rock’s physical state transitions that maponto the NOT gate’s computational state transitions are notgrounded in either the causal or dispositional properties of the rockand its states, the rock does not implement the NOT gate with feedbackaccording to the causal and dispositional accounts.

Importantly, under the above family of restrictive mapping accounts,there are mappings between any physical system and at least somecomputational descriptions. Thus, according to these accounts,everything performs at least some computations (cf. Section 3.2). Thisstill strikes some as overly inclusive. In computer science andcognitive science, there seems to be a distinction between systemsthat compute and systems that do not.

To account for this distinction, Anderson and Piccinini (2024) proposea “robust mapping account” based on three precise mappingrestrictions that are independently motivated by physical informationtheory. First, if a physical systemP is to implement acomputational system defined by computational descriptionC,it must possess physical states that map ontoallcomputational states defined byC — more precisely,there must be physical states belonging to subsystems ofPthat map onto each value of each variable defined byC.Second, ifp₁ andp₂ arephysical states that map onto computational statess₁ ands₂, respectively, thenthe physical state transitionp₁ →p₂ must map onto the computational statetransitions₁ →s₂.Finally, and most significantly, for any computational states defined byC, each physical state that maps ontos must be equally informative about the computationaltrajectory of the system as iss. In other words, it shouldnot be possible to infer either more or less about the computationalevolution of the system by knowing which particular physical state thesystem is in than one could infer by knowing the computational stateonto which that physical state maps. This robustness conditiongeneralizes on a faithfulness requirement proposed by Ladyman et al.(2007). In our example of the rock under the sun, knowing thetemperature of the rock allows one to infer whether it istransitioning into the first occurrence of ‘1’, the firstoccurrence of ‘0’, the second occurrence of‘1’, and so forth, which is a lot more than what can beinferred by knowing that the input was ‘0’ or‘1’. Thus, a rock does not implement a NOT gate withfeedback by laying under the sun. By similar reasoning, Anderson andPiccinini (2024) argue that many mappings that count as computationalimplementations under other restricted mapping accounts are not robustenough for physical systems to bear the physical signature of anycomputation. To bear the physical signature of a computation, theyargue, a physical system must satisfy the three conditions theypropose.

2.3 The Semantic Account

In our everyday life, we usually employ computations to processmeaningful symbols, in order to extract information from them. Thesemantic account of computation turns this practice into ametaphysical doctrine: computationis the processing ofrepresentations — or at least, the processing of appropriaterepresentations in appropriate ways. Opinions as to whichrepresentational manipulations constitute computations vary a greatdeal (Fodor 1975, Cummins 1983, Pylyshyn 1984, Churchland andSejnowski 1992, Shagrir 2006, 2022, Sprevak 2010). What all versionsof the semantic account have in common is that, in a slogan, there is“no computation without representation” (Fodor 1981,180).

The semantic account may be seen as imposing a further restriction onacceptable mappings. In addition to the restriction(s) imposed byrestricted mapping accounts, the semantic account imposes a semanticrestriction. Only physical states that qualify as representations maybe mapped onto computational descriptions, thereby qualifying ascomputational states. If a state is not representational, it is notcomputational either.

The semantic account is popular in philosophy of mind, because itappears to fit some of its specific needs better than other accounts.Since minds and digital computers are generally assumed to manipulate(the right kind of) representations, they turn out to compute. Sincemost other systems are generally assumednot to manipulate(the relevant kind of) representations, they do not compute. Thus, thesemantic account appears to accommodate some common intuitions aboutwhat does and does not count as a computing system. It keeps minds andcomputers in while leaving most everything else out, therebyvindicating the computational theory of cognition as a strong andnontrivial theory.

The semantic account raises three important questions: howrepresentations are to be individuated, what counts as arepresentation of the relevant kind, and what gives representationstheir semantic content.

On the individuation of computational states, the main debate dividesinternalists from externalists. According to externalists,computational vehicles are symbols individuated by their widecognitive contents — paradigmatically, the things thatthe symbols stand for (Burge 1986, Shapiro 1997, Shagrir 2001). Incontrast, most internalists maintain that computational vehicles aresymbols individuated by narrowcognitive contents (Segal1991). Narrow contents are, roughly speaking, semantic contentsdefined in terms of intrinsic properties of the system.Cognitive contents, in turn, are contents ascribed to asystem by a cognitive psychological theory. For instance, thecognitive contents of the visual system are visual contents, whereasthe cognitive contents of the auditory system are auditorycontents.

To illustrate the dispute, consider two physically identical cognitivesystemsA andB. Among the symbols processed byA is symbolS.A produces instances ofS wheneverA is in front of bodies of water, whenA is thinking of water, and whenA is forming plansto interact with water. In short, symbolS appears to standfor water. Every timeA processesS, systemB processes symbolS′, which is physicallyidentical toS. But systemB lives in an environmentdifferent fromA’s environment. WheneverA issurrounded by water,B is surrounded bytwater.Twater is a substance superficially indistinguishable from water butin fact physically different from it. Thus, symbolS′appears to stand for twater (cf. Putnam 1975b). So, we are assumingthatA andB live in relevantly differentenvironments, such thatS appears to stand for water whileS′ appears to stand for twater. We are also assumingthatA is processingS in the same way thatB is processingS′. There is no intrinsicphysical difference betweenA andB.

According to externalists, whenA is processingSandB is processingS′ they are incomputational states ofdifferent types. According tointernalists,A andB are in computational states ofthesame type. In other words, externalists maintain thatcomputational states are individuated in part by their reference,which is determined at least in part independently of the intrinsicphysical properties of cognitive systems. By contrast, internalistsmaintain that computational states are individuated in a way thatsupervenes solely on the intrinsic physical properties of cognitivesystems.

So far, externalists and internalists agree on one thing:computational states are individuated bycognitive contents.This assumption can be resisted without abandoning the semanticaccount of computation. According to Egan (1999, 2025), computationalvehicles are not individuated by cognitive contents of any kind,whether wide or narrow. Rather, they are individuated by theirmathematical contents — that is, mathematical functionsand objects ascribed as semantic contents to the computationalvehicles by a computational theory of the system. Since mathematicalcontents are the same across physical duplicates, Egan maintains thather mathematical contents are a kind of narrow content — she isa kind of internalist.

Let us now turn to what counts as a representation. This debate isless clearly delineated. According to some authors, only structuresthat have a language-like combinatorial syntax, which supports acompositional semantics, count as computational vehicles, and onlymanipulations that respect the semantic properties of such structurescount as computations (Fodor 1975, Pylyshyn 1984). This suggestionflies in the face of computability theory, which imposes no suchrequirement on what counts as a computational vehicle. Other authorsare more inclusive on what representational manipulations count ascomputations, but they have not been especially successful in drawingthe line between computational and non-computational processes. Fewpeople would include all manipulations of representations —including, say, painting a picture and recording a speech — ascomputations, but there is no consensus on where to draw the boundarybetween representational manipulations that count as computations andrepresentational manipulations that do not.

A third question is what gives representations their semantic content.There are three families of views. Instrumentalists believe thatascribing semantic content to things is just heuristically useful forprediction and explanation; semantic properties are not realproperties of computational states (e.g., Dennett 1987, Egan 2010,2025). Realists who are not naturalists believe semantic propertiesare real properties of computational states, but they are irreducibleto non-semantic properties. Finally, realists who are also naturalistsbelieve semantic properties are both real and reducible tonon-semantic properties, though they disagree on exactly how to reducethem (e.g., Fodor 2008, Harman 1987).

The semantic account of computation is closely related to the commonview that computation is information processing. This idea is lessclear than it may seem, because there are several notions ofinformation. The connection between information processing andcomputation is different depending on which notion of information isat stake. What follows is a brief disambiguation of the view thatcomputation is information processing based on four important notionsof information (cf. Piccinini and Scarantino 2011).

Entropy: Information in the sense of thermodynamics is closely relatedtothermodynamic entropy. Entropy is a property of everyphysical system. Thermodynamic entropy is, roughly, a measure of anobserver’s uncertainty about the microscopic state of a systemafter she considers the observable macroscopic properties of thesystem. The study of the thermodynamics of computation and physicalinformation theory is a lively field with many implications in thefoundations of physics (Leff and Rex 2003, Cuffaro and Fletcher 2018,Lent et al. 2019, Anderson 2022 and other articles in the same issueof the journalEntropy, entry oninformation processing and thermodynamic entropy). In this thermodynamic sense of “information,” anydifference between two distinguishable states of a system may be saidto carry information. Computation may well be said to be informationprocessing in this sense, but this has little to do with semantics inthe senses that matter to philosophers of mind. However, theconnections between thermodynamics, computation, and informationtheory are one possible source of inspiration for the view that everyphysical system is a computing system (see Section 3.4).
Mutual information: Information in one sense of communication theoryis a measure of the average likelihood that a given message istransmitted between a source and a receiver (Shannon and Weaver 1949).It can also be used to derive bounds on physical costs of computation,which pertains to physical information theory (Anderson 2017). Mutualinformation is not a semantic notion per se, but it can be used tohelp articulate accounts of natural semantic information (Isaac 2019,Heemskerk 2025).
Natural semantic information: Information in one semantic sense isinformation carried by signals that have “natural meaning”(Grice 1957). A signal carries information in this sense just in caseit reliably correlates with the state of a source (Dretske 1981). Theview that computation is information processing in this sense is primafacie implausible, because many computations — such asarithmetical calculations carried out on digital computers — donot seem to carry any natural meaning. Nevertheless, this notion ofsemantic information is relevant here because it has been used by sometheorists to ground an account of representation (e.g., Dretske 1981,Fodor 2008).
Nonnatural semantic information: Information in another semantic senseis just ordinary semantic content or “non-natural meaning”(Grice 1957). This is the kind of semantic content that mostphilosophers discuss. The view that computation is informationprocessing in this sense is similar to a generic semantic account ofcomputation.

Although the semantic account of computation appears to fit the needsof philosophers of mind, it appears less suited to make sense of othersciences. Most pertinently, representation does not seem to bepresupposed by the notion of computation employed in computabilitytheory and computer science — the very sciences that gave riseto the notion of computation at the origin of the computational theoryof cognition (Fresco 2010). If this is correct, the semantic accountmay not even be adequate to the needs of philosophers of mind —at least those philosophers of mind who wish to make sense of theanalogy between minds and the systems designed and studied by computerscientists and computability theorists. Another criticism of thesemantic account is that specifying the kind of representation andrepresentational manipulation that is relevant to computation mayrequire a non-semantic way of individuating computations (Piccinini2004). These concerns motivate efforts to account for computation innon-semantic terms.

2.4 The Syntactic Account

As we saw, the semantic account needs to specify which representationsare relevant to computation. One view is that the relevantrepresentations are language-like, that is, they have the kind ofsyntactic structure exhibited by sentences in a language. Computation,then, is the manipulation of language-like representations in a waythat is sensitive to their syntactic structure and preserves theirsemantic properties (Fodor 1975).

As discussed in the previous section, however, using the notion ofrepresentation in an account of computation involves somedifficulties. If computation could be accounted for without appealingto representation, those difficulties would be avoided. One way to doso is to maintain that computation simply is the manipulation oflanguage-like structures in accordance with their syntacticproperties, leaving semantics by the wayside. The structures beingmanipulated are assumed to be language-like only in that they havesyntactic properties — they need not have any semantics. In thissyntactic account of computation, the notion of representation is notused at all.

The syntactic account may be seen as adding a restriction onacceptable mappings that replaces the semantic restriction proposed bythe semantic account. Instead of a semantic restriction, the syntacticaccount imposes a syntactic restriction: only physical states thatqualify as syntactic may be mapped onto computational descriptions,thereby qualifying as computational states. If a state lacks syntacticstructure, it is not computational.

What remains to be seen is what counts as a syntactic state. Animportant account of syntax in the physical world is due to StephenStich (1983, 150–157). Although Stich does not use the term“computation,” his account of syntax is aimed at groundinga syntactic account of mental states and processes. Stich’ssyntactic theory of mind is, in turn, his interpretation of thecomputational theories proposed by some cognitive psychologists— in competition with Fodor’s semantic interpretation.Since Stich’s account of syntax is ultimately aimed at groundingcomputational theories of cognition, Stich’s account of syntaxalso provides an (implicit) syntactic account of computation.

According to Stich, roughly speaking, a physical system containssyntactically structured objects when two conditions are satisfied.First, there is a mapping between the behaviorally relevant physicalstates of the system and a class of syntactic types, which arespecified by a grammar that defines how complex syntactic types can beformed out of (finitely many) primitive syntactic types. Second, thebehavior of the system is explained by a theory whose generalizationsare formulated in terms of formal relations between the syntactictypes that map onto the physical states of the system.

The syntactic account of computation is not very popular. A commonobjection is that it seems difficult to give an account of primitivesyntactic types that does not presuppose a prior semanticindividuation of the types (Crane 1990, Jacquette 1991, Bontly 1998).In fact, it is common to make sense of syntax by construing it as away to combine symbols, that is, semantically interpretedconstituents. If syntax is construed in this way, it presupposessemantics. If so, the syntactic account of computation collapses intothe semantic account.

Another objection is that language-like syntactic structure is notnecessary for computation as it is understood in computer science andcomputability theory. Although computing systems surely can manipulatelanguage-like structures, they don’t have to. They can alsomanipulate simple sequences of letters, without losing their identityas computers. (Computability theorists call any set of words from afinite alphabet a language, but that broad notion of language shouldnot be confused with the narrower notion — inspired by grammarsin logic and linguistics — that Stich employs in his syntacticaccount of computation.)

2.5 The Mechanistic Account

The mechanistic account avoids appealing to both syntax and semantics.Instead, it accounts for concrete computation in terms of themechanistic properties of certain systems. According to themechanistic account, concrete computing systems are functionalmechanisms of a special kind — mechanisms that perform concretecomputations (Piccinini 2007, 2015, 2020; cf. Kaplan 2011, Milkowski2013, Fresco 2014, Duwell 2017, Giunti 2017, Dewhurst 2018, CoelhoMollo 2018, Curtis-Trudel 2021, Lee 2021, Kuokkanen 2022, Fuentes2024, Kersten 2024).

A functional mechanism is a system of organized components, each ofwhich has functions to perform (cf. Craver 2012, Garson 2013). Whenappropriate components and their functions are appropriately organizedand functioning properly, their combined activities constitute thecapacities of the mechanism. Conversely, when we look for anexplanation of the capacities of a mechanism, we decompose themechanism into its components and look for their functions andorganization. The result is a mechanistic explanation of themechanism’s capacities.

This notion of functional mechanism is familiar to biologists andengineers. For example, biologists explain physiological capacities(digestion, respiration, etc.) in terms of the functions performed bysystems of organized components (the digestive system, the respiratorysystem, etc.).

According to the mechanistic account, a computation in the genericsense is the processing of vehicles according to rules that aresensitive to certain vehicle properties, and specifically, todifferences between different portions of the vehicles. The processingis performed by a functional mechanism, that is, a mechanism whosecomponents are functionally organized to perform the computation.Thus, if the mechanism malfunctions, a miscomputation occurs.

Digital computation, analog computation, etc. turn out to be speciesof generic computation. They are differentiated by more specificproperties of the vehicles being processed. If a computing systemprocesses strings of discrete states in ways sensitive to the positionof the states within the string, then it performs a digitalcomputation. If a computing system can process continuous variablesvia integration, among other operations, then it performs an analogcomputation (cf. Papayannopoulos 2020 and Maley 2023 for semanticaccounts of analog computation). If a computing system processesqubits, then it performs a quantum computation.

When we define concrete computations and the vehicles that theymanipulate, we need not consider all of their specific physicalproperties. We may consider only the properties that are relevant tothe computation, according to the rules that define the computation. Aphysical system can be described more or less abstractly. According tothe mechanistic account, an abstract description of a physical systemis not a description of an abstract object but rather a description ofa concrete system that omits certain details. Descriptions of concretecomputations and their vehicles are sufficiently abstract that thecomputations they define may be implemented in different physicalsubstrates, or media. Because of this, concrete computations and theirvehicles are sometimes said to be ‘substrate neutral’,‘medium-independent’, or ‘medium-flexible’(Kirkpatrick 2022, Drayson 2025, Seth 2025).

In other words, a vehicle is medium-flexible just in case the rules(i.e., the input-output maps) that define a computation are functionsof state variables associated with a set of functionally relevantdegrees of freedom, which can be implemented differently in differentphysical media. Thus, a given computation can be implemented inmultiple physical media (e.g., mechanical, electro-mechanical,electronic, magnetic, etc.), provided that the media possess enoughdegrees of freedom that can be appropriately organized, accessed, andmanipulated and that the components of the mechanism are functionallyorganized in the appropriate way.

The mechanistic account avoids pancomputationalism. First, physicalsystems that are not functional mechanisms are ruled out. Functionalmechanisms are complex systems of components that are organized toperform functions. Any system whose components are not organized toperform functions is not a computing system because it is not afunctional mechanism. Second, mechanisms that lack the function ofmanipulating medium-flexible vehicles are ruled out. Finally,medium-flexible vehicle manipulators whose manipulations fail toaccord with appropriate rules are ruled out. The second and thirdconstraints appeal to special functional properties —manipulating medium-flexible vehicles, doing so in accordance withrules defined over the vehicles — that are possessed only byrelatively few physical systems. According to the mechanistic account,those few systems are the genuine computing systems.

Another feature of the mechanistic account is that it accounts for thepossibility of miscomputation — a possibility difficult to makesense of under other accounts. To illustrate the point, consider anordinary computer programmed to compute functionf on inputi. Suppose that the computer malfunctions and produces anoutput different fromf(i). According to the causal(semantic) account, the computer just underwent a causal process (amanipulation of representations), which may be given a computationaldescription and hence counts as computing some functiong(i), whereg≠f. In contrast,according to the mechanistic account, the computer simply failed tocompute, or at least it failed to complete its computation correctly.Given the importance of avoiding miscomputations in the design and useof computers, the ability of the mechanistic account to make sense ofmiscomputation may be an advantage over rival accounts.

A final feature of the mechanistic account is that it distinguishesand characterizes precisely many different kinds of computing systemsbased on the specific vehicles they manipulate and their specificmechanistic properties. The mechanistic account has been used toexplicate digital computation, analog computation, computation byneural networks, and other important distinctions such as hardwiredvs. programmable and serial vs. parallel computation (Piccinini 2015,Wiggershaus 2025).

3. Is Every Physical System Computational?

Which physical systems perform computations? According topancomputationalism, they all do. Even rocks, hurricanes, andplanetary systems — contrary to appearances — arecomputing systems. Pancomputationalism is quite popular among somephilosophers and physicists.

3.1 Varieties of Pancomputationalism

Varieties of pancomputationalism vary with respect tohowmany non-equivalent computations — many, a few, or just one— they attribute to each system.

The strongest version of pancomputationalism is that every physicalsystem performsevery computation — or at least, everysufficiently complex system implements a large number ofnon-equivalent computations (Putnam 1988, Searle 1992). This may becalledunlimited pancomputationalism.

The weakest version of pancomputationalism is that every physicalsystem performssome (as opposed toevery)computation. A slightly stronger version maintains that everythingperformsa few computations, some of which encode the othersin some relatively unproblematic way (Scheutz 2001). These versionsmay be calledlimited pancomputationalism.

Varieties of pancomputationalism also vary with respect towhy everything performs computations — the source ofpancomputationalism.

One alleged source of pancomputationalism is that which computation asystem performs is a matter of relatively free interpretation. Ifwhether a system performs a given computation depends solely orprimarily on how the system is perceived, as opposed to objectivefact, then it seems that everything computes because everything may beseen as computing (Searle 1992). This may be calledinterpretivistpancomputationalism.

Another alleged source of pancomputationalism is that everything hascausal structure. According to the causal account, computation is thecausal structure of physical processes (Chrisley 1995, Chalmers 1995,1996, Scheutz 1999, 2001). Assuming that everything has causalstructure, it follows that everything performs the computationconstituted by its causal structure. This may be calledcausalpancomputationalism.

A third alleged source of pancomputationalism is that every physicalstate carries information, in combination with an information-basedsemantics plus a liberal version of the semantic view of computation.According to the semantic view of computation, computation is themanipulation of representations. According to information-basedsemantics, a representation is anything that carries information.Assuming that every physical state carries information, it followsthat every physical system performs the computations constituted bythe manipulation of its information-carrying states (cf. Shagrir 2006,2022). Both information-based semantics and the assumption that everyphysical state carries information (in the relevant sense) remaincontroversial.

Yet another alleged source of pancomputationalism is that computationis the nature of the physical universe. According to some physicists,the physical world is computational at its most fundamental level.This “it from bit” view (e.g., Wheeler 1989) will bediscussed in Section 3.4.

3.2 Unlimited Pancomputationalism

Arguments for unlimited pancomputationalism go back toHinckfuss’s pail, a putative counterexample to computationalfunctionalism — the view that the mind is the software of thebrain. Hinckfuss’s pail is named after its proponent, IanHinckfuss, but was first discussed in print by William Lycan. A pailof water contains a huge number of microscopic processes:

Now is all this activity not complex enough that, simply by chance, itmight realize a human program for a brief period (given suitablecorrelations between certain micro-events and the requisite input-,output-, and state-symbols of the program)? (Lycan 1981, 39)

Hinckfuss’s implied answer to this question is that yes, a pailof water might implement a human program, and therefore any arbitrarycomputation, at least for a short time.

Other authors developed more detailed arguments along the lines ofHinckfuss’s pail. John Searle (1992) explicitly argues thatwhether a physical system implements a computation depends on how anobserver interprets the system; therefore, for any sufficientlycomplex object and for any computation, the object can be described asimplementing the computation. The first rigorous argument forunlimited pancomputationalism is due to Hilary Putnam (1988), whoargues that every ordinary open system implements every abstractfinite state automaton (without inputs and outputs).

Putnam considers a generalization of the example of the rock fromSection 2.2, which was a simple finite state automaton transitioningthrough a sequence of computational states without inputs or outputs.Any arbitrary physical system that undergoes (possibly continuous)physical transitions is such that at least some of its physical statesmap onto the computational states of an arbitrary finite stateautomaton, thus mapping physical state transitions to computationalstate transitions. Because the physical system and the automaton arearbitrary, every physical system implements every finite stateautomaton without intputs and outputs.

To handle automata with inputs and outputs, Putnam argues, one musttake into account an isomorphic mapping between some physical states(considered as inputs and outputs) and the inputs and outputs of therelevant automaton. This restriction result in a weaker conclusion:instead ofevery physical system implementingeveryfinite state automaton, any given physical system implements acountably infinite number of finite state automata (namely, those thatproduce the correct input/output pairs). This is because, for anyarbitrary input/output pair <i,o>, there area countably infinite number of automata that produce outputowhen given inputi.

If unlimited pancomputationalism is correct, then the claim that asystemS performs a certain computation becomes triviallytrue and vacuous or nearly so; it fails to distinguishS fromanything else (or perhaps from anything else with the same inputs andoutputs). Thus, unlimited pancomputationalism threatens the utility ofthe computational theory of cognition. If cognition is computationsimply because cognitive systems, like everything else, may be seen asperforming more or less arbitrary computations over the relevantinputs, then it appears that the computational theory of cognition isboth trivial and vacuous (though see Schweizer 2019 and Curtis-Trudel2024 for attempts to resist this conclusion). By the same token,unlimited pancomputationalism threatens the foundations of computerscience, where the objective computational power of different systemsis paramount. For examples, finite state automata compute fewerfunctions than TMs, and some algorithms compute the same function moreefficiently than others. If any physical system can implement anycomputing system regardless of its computational power and complexity,those distinctions make no difference to concrete computations. Thisthreat of trivialization is a major motivation behind responses to thearguments for unlimited pancomputationalism.

The first thing to notice is that arguments for unlimitedpancomputationalism rely either implicitly or explicitly on the simplemapping account of computation. They assume that an arbitrary mappingfrom a computational descriptionC to a physical descriptionof a system is sufficient to conclude that the system implementsC. In fact, avoiding unlimited pancomputationalism is a majormotivation for rejecting the simple mapping account of computation. Byimposing restrictions on which mappings are legitimate, other accountsof computation aim to avoid unlimited pancomputationalism.

In one response to unlimited pancomputationalism, Jack Copeland (1996)argues that the mappings it relies on are illegitimate because theyare constructedex post facto — after the computationis already given. If someone wants a genuine computational descriptionof a physical system, she must first identify physical states andstate transitions of the system, then represent them by acomputational description (thereby fixing the mapping relation betweenthe computational description and the system), and finally use acomputer to generate subsequent representations of the state of thesystem, while the mapping relation stays fixed. In contrast, thearguments for unlimited pancomputationalism pick a computation first,then slice and aggregate the physical system to fit the computationaldescription, and finally generate the mapping between the two. Thework of describing the physical system is not done by thecomputational description but by whoever constructs the mapping.Copeland concludes that suchex post facto mappings areillegitimate.

In addition, both Chalmers (1995, 1996) and Copeland (1996) argue thatthe mappings invoked by unlimited pancomputationalism violate thecounterfactual relations between the computational states. Consideragain Putnam’s slice-and-aggregate strategy for generatingmappings. The mappings are constructed based on an arbitrary dynamicalevolution of an arbitrary physical system. No attempt is made toestablish what would happen to the physical system had conditions beendifferent. Chalmers and Copeland argue that this is illegitimate, as agenuine implementation must exhibit the same counterfactual relationsthat obtain between the computational states. This response leads tothe counterfactual account of computation.

Another possible response to unlimited pancomputationalism is that thephysical transitions it relies on are not always causal. ConsiderPutnam’s argument again. The mapping from the computationaldescription to the physical description is chosen with no regard tothe causal relations that obtain between the physical states of thesystem. Thus, the computational description does not describe thecausal structure of the physical system. According to several authors,non-causal mappings are illegitimate (Chrisley 1995, Chalmers 1995,1996, 2011, Scheutz 1999, 2001). Naturally, these authors defend thecausal account of computation, according to which acceptable mappingsmust respect the causal structure of a system.

Yet another response to unlimited pancomputationalism is implicitlygiven by Godfrey-Smith (2009). Although Godfrey-Smith is primarilyconcerned with functionalism as opposed to computation per se, hisargument is still relevant here. Godfrey-Smith argues that for amapping to constitute a genuine implementation, the microscopicphysical states that are clustered together (to correspond to a givencomputational state) must be physicallysimilar to oneanother — there cannot be arbitrary groupings of arbitrarilydifferent physical states, as in the arguments for unlimitedpancomputationalism. Godfrey-Smith suggests that his similarityrestriction on legitimate mappings may be complemented by the kind ofcausal and localizational restrictions proposed by Chalmers(1996).

Anderson and Piccinini (2024, Ch. 6) argue that the aboveconsiderations are subsumed under their robust mapping account.Restricting genuine computational implementation to mappings thatfulfill their three conditions results in computational descriptionsthat are principled (notex post facto), respect the causaland counterfactual relations between physical states, and groupphysical states based on their similarity. Thus, unlimitedpancomputationalism is avoided.

The remaining accounts of computation — the semantic, syntactic,and mechanistic accounts — are often even more restrictive thanrestrictive mapping accounts; they impose further constraints onacceptable mappings. Therefore, like restrictive mapping accounts,they have resources for avoiding unlimited pancomputationalism.

For example, consider the semantic account, according to whichcomputation requires representation. If being a representation ofsomething is an objective property possessed by relatively few things,then unlimited pancomputationalism is ruled out on the grounds thatonly the few items that constitute representations are genuinecomputational states. If, however, everything is representational inthe relevant way, then everything is computational (cf. Churchland andSejnowski 1992, Shagrir 2006). If, in addition, whether somethingrepresents something else is just a matter of free interpretation,then the semantic account of computation gives rise to unlimitedpancomputationalism all over again. Similar considerations apply tothe syntactic and mechanistic accounts. For such accounts to trulyavoid unlimited pancomputationalism, they must not rely on freeinterpretation.

3.3 Limited Pancomputationalism

Limited pancomputationalism is much weaker than its unlimited cousin.It holds that every physical system performs one (or relatively few)computations. Which computations are performed by which system isdeemed to be a matter of fact, depending on objective properties ofthe system. In fact, several authors who have mounted detailedresponses to unlimited pancomputationalism explicitly endorse limitedpancomputationalism (Chalmers 1996, 331, Scheutz 1999, 191).

Unlike unlimited pancomputationalism, limited pancomputationalism doesnot turn the claim that something is computational into a vacuousclaim. Different systems generally have different objectiveproperties; thus, according to limited pancomputationalism, differentsystems generally perform different computations. Nevertheless, it mayseem that limited pancomputationalism still trivializes the claim thata system is computational. For according to limitedpancomputationalism, digital computers perform computations in thesame sense in which rocks, hurricanes, and planetary systems do. Thismay seem to do an injustice to computer science — in computerscience, only relatively few systems count as performing computationsand it takes a lot of difficult technical work to design and buildsystems that perform computations reliably. Or consider the claim thatcognition is computation. This computational theory of cognition wasintroduced to shed new and explanatory light on cognition. But ifevery physical process is a computation, the computational theory ofcognition seems to lose much of its explanatory force.

Another objection to limited pancomputationalism begins with theobservation that any moderately complex system satisfies indefinitelymany objective computational descriptions (Piccinini 2020, 328). Thismay be seen by considering computational modeling. A computationalmodel of a system may be constructed at different levels ofgranularity. For example, cellular automata models of the dynamics ofa galaxy or a brain may use different state transition rules,different time steps, or cells that represent spatial regions ofdifferent sizes. Furthermore, an indefinite number of formalismsdifferent from cellular automata, such as TMs, can be used to computethe same functions computed by cellular automata. Limitedpancomputationalists appear committed to the galaxy or the brainperforming all these computations at once. But that does not appear tobe the sense in which computers (or brains) perform computations.

In the face of these objections, limited pancomputationalists arelikely to maintain that the explanatory force of computationalexplanations does not come from the claim that a system iscomputational simpliciter. Rather, explanatory force comes from thespecific computations that a system is said to perform. Thus, a rockand a digital computer perform computations in the same sense. Butthey perform radically different computations, and it is thedifference between their computations that explains the differencebetween them. As to the objection that there are still too manycomputations performed by each system, limited pancomputationalistshave two main options: either to bite the bullet and accept that everysystem implements indefinitely many computations, or to find a way tosingle out, among the many computational descriptions satisfied byeach system, the one that is ontologically privileged — the onethat capturesthe computation performed by the system. Oneway to do this is to postulate a fundamental physical level, whosemost accurate computational description identifies the (mostfundamental) computation performed by the system. This response isbuilt into the view that the physical world is fundamentallycomputational (next section).

As to those who remain unsatisfied with limited pancomputationalism,their desire to avoid limited pancomputationalism motivates the shiftto more restrictive accounts of computation, analogously to how thedesire to avoid unlimited pancomputationalism motivates the shift fromthe simple mapping account to more restrictive accounts ofcomputation, such as the causal account. The semantic account may beable to restrict genuine computational descriptions to fewer systemsthan the causal account, provided that representations — whichare needed for computation according to the semantic account —are hard to come by. Mutatis mutandis, the same is true of thesyntactic and mechanistic accounts.

A more recent objection to limited pancomputationalism is that theputative mappings between microphysical and computational dynamics itrelies on fail to mirror the causal structure of typical physicalsystems (Anderson and Piccinini 2024, Ch. 7). Even in systemsengineered to implement physical computations, such as computercircuits, much of the causal structure of the system must be ignoredwhen we map (some of) their microphysical states to theircomputational states. A fortiori, a computational description of anordinary system cannot mirror its microphysical causal structure.

3.4 The Universe as a Computing System

Some authors argue that the physical universe is fundamentallycomputational. The universe itself is a computing system, andeverything in it is a computing system too (or part thereof). Unlikethe previous versions of pancomputationalism, which originate inphilosophy, thisontic pancomputationalism originates inphysics. It includes both an empirical claim and a metaphysical one.Although the two claims are logically independent, supporters of onticpancomputationalism tend to make them both.

The empirical claim is that all fundamental physical magnitudes andtheir state transitions are such as to be exactly described by anappropriate computational formalism — without resorting to theapproximations that are a staple of standard computational modeling.This claim takes different forms depending on which computationalformalism is taken to describe the universe exactly. The two mainoptions are cellular automata, which are a classical computationalformalism, and quantum computing, which is non-classical.

The earliest and best known version of ontic pancomputationalism isdue to Konrad Zuse (1970, 1982) and Edward Fredkin, whose unpublishedideas on the subject influenced a number of American physicists (e.g.,Feynman 1982, Toffoli 1982, Wolfram 2002; see also Wheeler 1982,Fredkin 1990). According to some of these physicists, the universe isa giant cellular automaton. A cellular automaton is a lattice ofcells; each cell can take one out of finitely many states and updatesits state in discrete steps depending on the state of its neighboringcells. For the universe to be a cellular automaton, all fundamentalphysical magnitudes must be discrete, i.e., they must take at mostfinitely many values. In addition, time and space must befundamentally discrete or must emerge from the discrete processing ofthe cellular automaton. At a fundamental level, continuity is not areal feature of the world — there are no truly real-valuedphysical quantities. This flies in the face of most mainstreamphysics, but it is not an obviously false hypothesis. The hypothesisis that at a sufficiently small scale, which is currently beyond ourobservational and experimental reach, (apparent) continuity gives wayto discreteness. Thus, all values of all fundamental variables, andall state transitions, can be fully and exactly captured by the statesand state transitions of a cellular automaton.

Although cellular automata have been shown to describe many aspects offundamental physics, it is difficult to see how to simulate thequantum mechanical features of the universe using a classicalformalism such as cellular automata (Feynman 1982). This concernmotivated the development of quantum computing formalisms (Deutsch1985, Nielsen and Chuang 2000). Instead of relying on digits —most commonly, binary digits or bits — quantum computationrelies on qudits — most commonly, binary qudits or qubits. Themain difference between a digit and a qudit is that whereas a digitcan take only one out of finitely many states, such as 0 and 1 (in thecase of a bit), a qudit can also take an uncountable number of statesthat are a superposition of the basis states in varying degrees, suchas superpositions of 0 and 1 (in the case of a qubit). Furthermore,unlike a collection of digits, a collection of qudits can exhibitquantum entanglement. According to the quantum version of onticpancomputationalism, the universe is not a classical computer but aquantum computer, that is, not a computer that manipulates digits buta computer that manipulates qubits (Lloyd 2006) — or, moregenerally, qudits.

The quantum version of ontic pancomputationalism is less radical thanthe classical version. The classical version eliminates continuityfrom the universe, primarily on the grounds that eliminatingcontinuity allows classical computers to describe the universe exactlyrather than approximately. Thus, the classical version appears to bemotivated not by empirical evidence but by epistemological concerns.Although there is no direct evidence for classical onticpancomputationalism, in principle it is a testable hypothesis (Fredkin1990). In contrast, quantum ontic pancomputationalism may be seen as areformulation of quantum mechanics in the language of quantumcomputation and quantum information theory (qubits), without changesin the empirical content of the theory (e.g., Fuchs 2004, Bub2005).

But ontic pancomputationalists do not limit themselves to makingempirical claims. They often make an additional metaphysical claim.They claim that computation (or information, in the first sensedescribed in Section 2.3) is what makes up the physical universe. Thispoint is sometimes made by saying that at the most fundamentalphysical level, there are brute differences between states —nothing more need or can be said about the nature of the states. Thisview reverses the traditional conception of the relation betweencomputation and the physical world.

According to the traditional conception, which is presupposed by allaccounts of computation discussed above, physical computation requiresa physical substrate, or medium. Computation is an aspect of theorganization and behavior of a physical system; there is no softwarewithout hardware. Thus, according to the traditional conception, ifthe universe is a cellular automaton, the ultimate constituents of theuniverse are the physical cells of the cellular automaton. It islegitimate to ask what kind of physical entity such cells are and howthey interact with one another so as to satisfy their cellularautomata rules.

In contrast, according to the metaphysical claim of onticpancomputationalism, a physical system is just a system ofcomputational states. Computation is ontologically prior to physicalprocesses, as it were. “‘Hardware’ [is] made of‘software’” (Kantor 1982, 526, 534), or“it” (the physical) comes from “bit” (thecomputational) (Wheeler 1989). According to this non-traditionalconception, if the universe is a cellular automaton, the cells of theautomaton are not concrete, physical structures that causally interactwith one another. Rather, they are software — purely“computational” entities.

Such a metaphysical claim requires an account of what computation, orsoftware, or physical information, is. If computations are notconfigurations of physical entities in our universe, variousalternatives have been proposed. One is that we live in acomputational simulation: the appearance of our physical universe isthe result of a simulation run on a computer that exists in its ownuniverse, whose physics we have no access to (Fredkin 2003, 193). Asecond alternative is that computations are abstract, mathematicalentities, like numbers and sets. As Wheeler (1982, 570) puts it,“the building element [of the universe] is the elementary‘yes, no’ quantum phenomenon. It is an abstract entity. Itis not localized in space and time” (cf. Tegmark 2014). Underthis account, the ontological claim of ontic pancomputationalism is acomputational version of pythagoreanism. All is computation in thesame sense in which more traditional versions of pythagoreanismmaintain that all is number or that all is sets (Quine 1976). A thirdalternative is a computational version of ontic structural realism.According to ontic structural realism, all is structure, wherestructure is a system or relations represented by a mathematicaltheory. According to computational structuralism, all there is to ouruniverse is a computational structure (cf. Floridi 2008, Chalmers2022).

Ontic pancomputationalism may be attacked on both the empirical andthe ontological fronts. On the empirical front, there is littlepositive evidence to support ontic pancomputationalism. Supportersappear to be motivated by the desire for exact computational models ofthe world rather than empirical evidence that the models are correct.Even someone who shares this desire may well question why we shouldexpect nature to fulfill it. On the metaphysical front, purelycomputational ontologies face the objection that the computations theyput at the fundamental physical level lack the causal and qualitativeproperties that we observe in the physical world — or at least,no plausible account has been given of how purely computationalentities could give rise to physical qualities and their causal powers(e.g., Martin 1997, Anderson and Piccinini 2024, Ch. 8).

4. Physical Computability

According to the Church-Turing thesis (CTT), any function that isintuitively computable is computable by some TM (i.e.,Turing-computable). Alternatively, CTT may be formulated as follows:any function that is “naturally regarded as computable”(Turing 1936–7, 135) is Turing-computable. The phrases“intuitively computable” and “naturally regarded ascomputable” are somewhat ambiguous. When they are disambiguated,CTT takes different forms.

In one sense, “intuitively computable” means computable byfollowing an algorithm or effective procedure. An effective procedureis a finite list of clear instructions for generating new symbolicstructures out of old symbolic structures. When CTT is interpreted interms of effective procedures, it may be calledMathematicalCTT, because the relevant evidence is more logical ormathematical than physical. Mathematical CTT says that any functioncomputable by an effective procedure isTuring-computable.

There is compelling evidence that Mathematical CTT is true (Kleene1952, §62, §67; cf. also Sieg 2006):

There are no known counterexamples.
Diagonalization over TMs, contrary to what may be expected, doesnot yield a function that is not Turing-computable.
Argument from confluence: all the formalisms proposed to capturethe intuitive notion of computability by effective procedure —formalisms such as general recursiveness (Gödel 1934),λ-definability (Church 1932, Kleene 1935), Turing-computability(Turing 1936–7), and reckonability (Gödel 1936) —turn out to capture the same class of functions.
A TM seems capable of reproducing any operation that a human beingcan perform while following an effective procedure (Turing1936–7’s main argument for CTT).

In another sense, “intuitively computable” meanscomputable by physical means. When CTT is so interpreted, it may becalledPhysical CTT (following Pitowsky 1990), because therelevant evidence is more physical than logical or mathematical.

4.1 The Physical Church-Turing Thesis: Bold

Physical CTT is often formulated in very strong forms. To a firstapproximation,Bold Physical CTT holds that any physicalprocess — anythingdoable by a physical system —is computable by some TM.

Bold Physical CTT can be made more precise in a number of ways. Hereis a representative sample, followed by references to where they arediscussed:

Any physical process can be simulated by some TM (e.g., Deutsch1985, Wolfram 1985, Pitowsky 2002).
Any function over denumerable domains (such as natural numbers)that is computable by an idealized computing machine that manipulatesarbitrary real-valued quantities (as defined by Blumet al.1998) is Turing-computable.
Any system of equations describing a physical system gives rise tocomputable solutions (cf. Earman 1986, Pour-El and Richards 1989,Pour-El 1999). A solution is said to be computable just in case, givencomputable real numbers as initial conditions, it returns computablereal numbers as values. A real number is said to be computable just incase there is a TM whose output effectively approximates it.
For any physical systemS and observableW,there is a Turing-computable functionf:N→N such that for all timest∈N,f(t)=W(t) (Pitowsky 1990).

Thesis (A) is ambiguous between two notions of simulation. In onesense, simulation is the process by which a digital computing system(such as a TM) computes the same function as another digital computingsystem. This is the sense in which universal TMs can simulate anyother TM. If (A) is interpreted using this first notion of simulation,it entails that everything in the universe is a digital computingsystem. This is (a variant of) ontic pancomputationalism (Section3.4).

In another sense, simulation is the process by which the output of adigital computing system represents an approximate description of thedynamical evolution of another system. This is the sense in whichcomputational models of the weather simulate the weather. If (A) isinterpreted using this second notion of simulation, then (A) is trueonly if we do not care how close our computational approximations are.If we want close computational approximations — as we usually do— then (A) turns into the claim that any physical process can becomputationally approximated to the degree of accuracy that is desiredin any given case. Whether that is true varies from case to casedepending on the dynamical properties of the system, how much is knownabout them, which idealizations and simplifications are adopted in themodel, which numerical methods are used in the computation, and howmany computational resources (such as time, processing speed, andmemory) are available (Piccinini 2015, Ch. 4).

Thesis (B) is straightforwardly and radically false. Blumetal. (1989) set up a mathematical theory of computation overreal-valued quantities, which they see as a fruitful extension ofordinary computability theory. Within such a theory, Blumetal. define idealized “computing” machines thatperform addition, subtraction, multiplication, division, and equalitytesting as primitive operations on arbitrary real-valued quantities.They easily prove that such machines can compute all sets defined overdenumerable domains by encoding their characteristic function as areal-valued constant (ibid., 405). Although they do not discuss thisresult as a refutation of Physical CTT, their work is often cited indiscussions of physical computability and Physical CTT.

Theses (C) and (D) have interesting counterexamples that areconsistent with some physical theories (cf. below and Pour-El 1999).These theoretical counterexamples may or may not occur in our concretephysical universe.

Each of (A)–(D) raises important questions pertaining to thefoundations of computer science, physics, and mathematics. It is notclear, however, that they bear an interesting analogy to MathematicalCTT. Below are two reasons why.

First, (A)–(D) are falsified by processes that cannot be builtand used as computing devices. The most obvious example is (B). Blumet al.’s result is equivalent to demonstrating that allfunctions over denumerable domains — including the uncountablymany functions that are not Turing-computable — are computableby Blumet al.’s “computing” systems, whichare allowed to manipulate the exact values of arbitrary real numbers.Hence, (B) is radically false. But this result has no direct practicalapplications, as there is no evidence that concrete physical systemscan manipulate arbitrary real-valued quantities in the way that Blumet al.’s systems do.

More generally, formulations (A)–(D) would be falsified by asequence generated by a random (i.e., nondeterministic) physicalprocess. According to quantum mechanics, some physical processes— such as atom decay — contain an objectively randomelement. Hidden variable interpretations dispute this, but thepossibility of genuine randomness is sufficiently plausible that itshould be taken into account.

Consider a random process that produces discrete outputs over aninfinite period of time, e.g., the decay of atoms from a radioactivesample. Its output at regular time intervals is a string of digits— ‘0’ if no atoms decay during a time interval,‘1’ if one or more atoms decay during a time interval. Asimple consideration shows that, with probability one, the sequenceproduced by our random process is not Turing-computable. There areuncountably many infinite strings of digits (even more strongly, thereare uncountably many infinite strings of digits with any givenlimiting frequency of ‘0’s and ‘1’s). Butthere are only countably many Turing-computable infinite strings.Therefore, assuming that each infinite string (or each infinite stringwith a certain limiting frequency) has the same probability ofoccurring as a result of a random process, the probability that arandom process would generate a Turing-computable string of digits iszero, whereas the probability that the string of digits is notTuring-computable is one (for the stronger conclusion that no suchstring of digits is Turing-computable, see Calude & Svozil 2008).Thus, simply by using a random process to generate a string, there isa sense in which we would have physical means that go beyond what isTuring-computable. As Alan Turing (1950, 438–439) pointed out, amachine with a “random element” can do “more”than a TM. Butdoing more is not the same ascomputing more. Contrary to what is sometimes suggested(e.g., Calude 2005, 10), the combination of a TM and a random processdoes not threaten Physical CTT.

Random processes shouldnot count as computations: unlikecomputations properly so called, random processes cannot be used togenerate the desired values of a function or solve the desiredinstances of a general problem. Random processes can beexploited by a computation, of course — there areimportant computational techniques that rely on random orpseudo-random choices at some stages. If some quantum random sequenceswere random in the sense of algorithmic information theory, they mayeven raise the probability of obtaining correct solutions fromcomputational techniques that rely on random choices (Calude 2005,10). But no computational technique can amount to a mere sequence ofrandom choices. So any thesis, such as Bold Physical CTT, that wouldbe falsified by a sequence generated by a random process is too strongto capture the notion ofphysical computability — thephysical analogue of algorithmic computability. Thus, contrary to whatsome authors seem to assume, Bold Physical CTT is too strong to be aphysical analogue of Mathematical CTT.

Another feature that theses (A)–(D) have in common is that theyappeal quite freely to arbitrary real-valued quantities. This isexplicit in (B). To see why they all appeal to arbitrary real-valuedquantities, consider that most physical theories assume that manyphysical magnitudes, including time, can take arbitrary real numbersas values. Hence, systems of physical equations, whose simulations,solutions, or observables are appealed to, respectively, by (A), (C),and (D), involve arbitrary real numbers. Therefore, all formulationsof Bold Physical CTT involve, explicitly or implicitly, arbitrary realnumbers.

The expressive power of real numbers may be used to generate a simplerecipe to obtain the values of a Turing-uncomputable function.Consider that the digital expansion of a real number containscountably many digits. Hence, for any characteristic function (i.e., afunction whose values are ‘0’ or ‘1’) definedover a countable domain, including all Turing-uncomputable suchfunctions, there is a real number whose binary expansion encodes itsvalues. This is because for all values of a characteristic function,then^th value of the function may be defined to bethen^th digit of the binary expansion of a realnumber.

Suppose you wish to know the value of a specific Turing-uncomputablecharacteristic function, such as the halting function for TMs, for itsn^th argument. Take the real numberrwhose digital expansion encodes the values of the halting function.All you need to do is obtain the value of then^thdigit in the binary expansion ofr and you have the resultyou desire. If you can do this, you may obtain any value of anycharacteristic function defined over strings, including allTuring-uncomputable such functions.

The above recipe, if feasible, is a trivial consequence of theexpressive power of real numbers. Yet it is discussed in theliterature as an example of perhaps possible physical computationbeyond the power of TMs (e.g., Copeland 2000) — something thatwould falsify Physical CTT. But there is no reason to believe such arecipe can be implemented, because it requires either the measurementor the preparation of a Turing-uncomputable real-valued quantity withunbounded precision. There is no evidence that either is doable.

By relying on arbitrary real-valued quantities, many versions of BoldPhysical CTT make themselves vulnerable to falsification by relativelytrivial (though presumably unfeasible) recipes such as the one justmentioned. This casts doubt on the assumption — made by some whoseek ways to falsify Bold Physical CTT — that Bold Physical CTTis actually an interesting physical analogue of Mathematical CTT.

(The point just made does not impugn analog computation in thestandard sense of Pour-El (1974). Analog computation doesnotmanipulate exact values of arbitrary real-valued quantities but rathercontinuousvariables. Although a continuous variable may beassumed to take any real value within a relevant interval, asuccessful concrete analog computation requires only the measurementof real variables withsome degree of approximation. No exactvalues of arbitrary real-valued quantities are exploited by an analogcomputation, so analog computation does not falsify Bold Physical CTT(cf. Rubel 1989).)

Similar doubts about the alleged analogy between Mathematical CTT andBold Physical CTT may be generated by a related observation. Manycurrent physical theories assume that nature contains real-valuedquantities that vary along a continuum. These may include the velocityof objects, the coordinates that define the position of their centerof gravity in the spacetime manifold, and more. If these physicaltheories are correct, then many properties of many entities takearbitrary real numbers as their values. And most real numbers in anycontinuous interval are Turing-uncomputable. In fact, there are onlycountably many computable numbers, but any continuous intervalcontains uncountably many real numbers. Thus, the probability that arandomly picked real-valued quantity is computable is zero. Hence, ifour physical theories are correct, most transformations of therelevant physical properties are transformations ofTuring-uncomputable quantities into one another.

For instance, an object’s change of speed, or even its simplechange of spatial location may be transformations of oneTuring-uncomputable real-valued quantity into another. Atransformation of one Turing-uncomputable value into anotherTuring-uncomputable value is a Turing-uncomputable operation. Hence,it would seem that given many of our physical theories, the physicalworld is chock-full of operations that outstrip the power of TMs. Ifthis is correct, it falsifies Bold Physical CTT.

But, as before, there is no reason to believe that we can use theTuring-uncomputable operations just mentioned tocompute inthe epistemological sense that motivates CTT in the first place— to solve problems, to generate the values of desired functionsfor desired arguments. In other words, it is implausible that theoperations in question should count as computations. Bold PhysicalCTT, which is threatened by such operations, is not interestinglyanalogous to Mathematical CTT.

To conclude our discussion of Bold Physical CTT, it may be helpful todistinguish the issue of physical computability proper — theissue that pertains to the physical analogue of Mathematical CTT— from other issues that connect computability and physics. Manyquestions about the relationship between physical processes andcomputability deserve to be asked. What are the physically computablefunctions? This is the question that should motivate Physical CTT.What can be computationally approximated to what degree under whatcircumstances? This is presumably what (A) is after. As important andinteresting as this question is, it is different from the question ofwhat can be physically computed. Yet other questions motivate theses(B)-(D) above as well as other versions of Bold Physical CTT to befound in the literature. Many of these questions are interesting anddeserve to be investigated. Nevertheless, they do not properly belongin discussions of CTT, because they are different from thecomputability question that motivates CTT in the first place.

4.2 The Physical Church-Turing Thesis: Modest

In the literature on computation in physical systems, there is aconcern that a physical analogue of Mathematical CTT should includeonlyusable physical processes (e.g., Gandy 1993 [OtherInternet Resources], Németi and Dávid 2006; Ord 2006,Smith 2006a, Beggs and Tucker 2007). Given this concern, an adequateversion of Physical CTT ought to be more modest than Bold PhysicalCTT.

Thus, Modest Physical CTT is formulated in terms of which functionsover a denumerable domain can be physicallycomputed.Prototypical examples of physical computation are the processes ofordinary digital computers and their components, including digitalcircuits. Such processes can be exhaustively described by effectiveprocedures, which are already covered by Mathematical CTT.Mathematical CTT says that any function computable by an effectiveprocedure is computable by a TM. As TMs can be physically implemented(or replaced by a computing human), any process that follows aneffective procedure is physically computable.

But physical computation in the present sense is a broader notion thancomputation by effective procedure. A process may count as a physicalcomputation even if there is no effective procedure for describing theprocess, perhaps because there are no finite instantaneousdescriptions of the internal states that constitute the process or noway to finitely and exactly specify the transition from oneinstantaneous description to the next. Thus, Modest Physical CTT isstronger than Mathematical CTT.

Gandy (1980) was one of the first to discuss a version of ModestPhysical CTT, arguing that mechanisms with discrete components andreasonable physical limitations (a lower bound on the size ofcomponents, and an upper bound on their speed) can only physicallycompute Turing-computable functions. However, Modest Physical CTT neednot be limited in these ways. In addition to physical processes thatfollow effective procedures, Modest Physical CTT may cover continuousdynamical processes (as in certain kinds of connectionist computing),processes that span large portions of spacetime, and quantum processes(as in quantum computing). But physical computation does not includeall physical processes.

In accordance with this proposal,Modest Physical CTT holdsthat any function (over a denumerable domain) that isphysicallycomputable is Turing-computable.

For a process to count as a physical computation, and hence for it tobe relevant to Modest Physical CTT, it must be usable by an observerto generate the desired values of an independently specified function.This requirement may be spelled out in terms of a number ofconstraints (Piccinini 2015, Chs. 15 and 16). This list is notintended to be exhaustive:

Constraint 1: Readable inputs and outputs. The process must takeinputs and yield outputs that observers can read without error, sothat observers can use the outputs as solutions to problems or valuesof functions defined over the inputs. For that to be possible,presumably the inputs and outputs need to be strings of discretestates, like the inputs and outputs of ordinary digital computers.
Constraint 2: Process-independent rule. There must be a fixed rule ormap — specifiable independently of the physical process —that links the outputs to the inputs. By defining the problem to besolved by the process, this rule tells the user what she is going tolearn by running the process. Since the rule defines a physicalcomputation in general, the rule need not be recursive. For instance,it may be the rule that defines the halting problem for TMs. Like allrecursive rules, the rule must be the same for all inputs that belongin the same problem; it cannot change from one input to the next.
Constraint 3: Repeatability. The process must be repeatable, so as toallow users to obtain the same results multiple times and to check acomputation by repeating it.
Constraint 4: Settability. The system undergoing the process must besettable, so that a user can choose which argument of a function thesystem computes and set the system to compute the relevant value ofthe function.
Constraint 5: Physical constructibility. The system must be physicallyconstructible.
Constraint 6: Reliability. The system must not break down before theprocess is completed.

In summary, Modest Physical CTT asserts that every function that canbe physically computed, i.e., every usable transformation of inputstrings into output strings in accordance with a process-independentrule defined over the strings, is Turing-computable.

Since Modest Physical CTT is restricted by epistemologically relevantcriteria, it doesn’t raise the worries associated with BoldPhysical CTT — namely, that it’s too easy to falsify andirrelevant to the notion of computability that motivates CTT. Andthere are good reasons to believe Modest Physical CTT. All computingmechanisms that have been physically built or are in the process ofbeing built compute only functions that are Turing-computable.

It is important to understand the exact scope of Modest Physical CTT.Modest Physical CTT does not entail that every physical process is acomputation, or that every physical system is a computing system. Itonly says that if something physical computes functions of adenumerable domain, then the functions it computes areTuring-computable.

To fully assess Modest Physical CTT, we should consider whether it ispossible to build a machine that, like an ordinary digital computer,can be used by human observers, but, unlike an ordinary digitalcomputer, generates the values of functions that areTuring-uncomputable. In recent years, several designs forhypercomputation have been proposed. Hypercomputation is thecomputation of Turing-uncomputable functions. If hypercomputationturned out to be physically possible, it would refute Modest PhysicalCTT.

4.3 Hypercomputation

To a first approximation, a hypercomputer is a system that yields thevalues of a function that is not Turing-computable. If what counts asyielding the values of a function is left unspecified, any of thesystems discussed in Section 4.1, such as genuinely random processesand systems that manipulate arbitrary real-valued quantities, wouldcount as hypercomputers. But in discussing Bold Physical CTT, we sawthat yielding the values of a function that is Turing-uncomputable,without further constraints, is not enough for genuine physicalcomputation.

By analogy with the distinction between Bold Physical CTT and ModestPhysical CTT, let us distinguish between a weak and a strong notion ofhypercomputation by distinguishing usable hypercomputers from unusablehypercomputational processes.

Anunusable hypercomputational process is a physical processthat fails to satisfy at least one of the first four constraints onphysical computation. Examples include processes whose inputs oroutputs are arbitrary real-valued quantities (which are not readablewith infinite precision) and genuine random processes (which have norule characterizing the inputs and outputs independently of theprocess, and are neither repeatable nor settable). These processes arenot usable because an observer cannot obtain from them arbitraryvalues of an independently defined function on a chosen input, asordinary computing systems can (given enough time and space). Sincethey are not usable, unusable hypercomputational processes areirrelevant to Modest Physical CTT.

Ausable hypercomputer is a physical system that satisfies atleast the first four constraints on physical computation. It hasreadable inputs and outputs, there is a rule characterizing itsinput-output properties that may be defined independently of theprocess itself, and its processes are repeatable and settable. If asystem does not satisfy one of these conditions, it does not count ascomputing in the sense relevant to Modest Physical CTT.

A system that satisfies these conditions — a usablehypercomputer — may be purely notional. For instance, infinitelyaccelerating TMs (Copeland 2002) are TMs that perform eachcomputational operation in half the time as their previous operation.As a consequence, infinitely accelerating TMs complete an infinitenumber of operations (asupertask) within twice the time ittakes them to perform their first operation. This allows infinitelyaccelerating TMs to compute functions, such as the halting function,that are Turing-uncomputable. But infinitely accelerating TMs areusually discussed as notional entities, without evidence that they canbe constructed. Purely notional systems, of course, do not falsifyModest Physical CTT. To do that, a system must satisfy at least thefifth and sixth constraints on physical computation: it must bephysically constructible and it must operate reliably.

One way to construct something like an infinitely accelerating TMwould be to make a computing machine that, after performing somecomputational operations, builds a smaller and faster copy of itself(Davies 2001). The smaller and faster copy will also perform someoperations and then build a faster and smaller copy, and so on. Givenappropriate assumptions, the resulting series of infinitely shrinkingmachines will be able to complete an infinite number of computationaloperations within a finite time, thereby surpassing the power of TMs.While infinitely shrinking machines appear to be consistent withNewtonian mechanics, Davies (2001, 672) points out that the atomic andquantum mechanical nature of matter in our universe makes infinitelyshrinking machines physically impossible.

Neural networks have sometimes been discussed as computing systemsthat may go beyond Turing-computability (e.g., Smolensky 1988, 3). Ifwe restrict our attention to classes of neural networks that containall systems with current or foreseeable practical applications, thisopinion is unwarranted. There is now a considerable literature on thecomputational and complexity properties of large classes of neuralnetworks. The most relevant systems have digital inputs and outputs(so as to satisfy our first constraint on physical computation) butmay have, and typically do have, non-digital internal processes (i.e.,their internal processes are not discrete step-by-step manipulationsof strings of digits). The main results are the following: (i)feedforward networks with finitely many processing units arecomputationally equivalent to Boolean circuits with finitely manygates; (ii) recurrent networks with finitely many units are equivalentto finite state automata; (iii) networks with unbounded tapes or anunbounded number of units are equivalent to TMs (Šíma& Orponen 2003).

Neural networks more powerful than TMs may be defined, however, byexploiting once again the expressive power of real numbers. The bestknown networks of this kind are Analog Recurrent Neural Networks(ARNNs) (Siegelmann 1999). ARNNs should not be confused with analogcomputers in the traditional sense (Pour-El 1974, Rubel 1993, Mills2008). Whereas analog computers manipulate real variables withoutrelying on the exact value of arbitrary real-valued quantities, ARNNsmanipulate strings of digits by (possibly) relying on the exact valueof arbitrary real-valued quantities. Specifically, the weightsconnecting individual processing units within ARNNs can take exactvalues of arbitrary real numbers, including values that areTuring-uncomputable. When their weights are Turing-uncomputable, ARNNscan go beyond the power of Turing-machines: they compute any functionover binary strings. ARNNs more powerful than TMs cannot be operatedreliably, because they require unboundedly precise weights. Inaddition, the required weights are Turing-uncomputable, soconstructing ARRNs more powerful than TMs requires already possessingthe ability to perform hypercomputations (Davis 2004, Schonbein 2005,Siegelmann 1999, 148).

Perhaps the best known proposal for a hypercomputer is due to MarkHogarth (1994, 2004), who developed an idea of Itamar Pitowsky (1990).Relativistic hypercomputers exploit the properties of a special kindof spacetime called Malament-Hogarth spacetime, which is physicallypossible in the sense of constituting a solution to Einstein’sfield equations for General Relativity. Malament-Hogarth spacetimescontain regions with an infinite time-like trajectory λ thatcan be circumvented by a finite time-like trajectory γ. In otherwords, λ and γ have a common origin, and there is aspacetime pointp on γ such that λ, even thoughit is infinite, lies entirely inp’s chronologicalpast. If an observer launches a TM along λ and then travelsalong γ she may, within finite time, find herself in the futureof an infinitely long computation performed by the TM. If the TM isable to send signals to the observer, the observer would be able toknow the outcome of a potentially infinitely long computation, therebyhaving computational means more powerful than (ordinary) TMs. Forinstance, an observer may be able to obtain the results of anarbitrary instance of the halting function for TMs.

Constructing and using a relativistic hypercomputer is a nontrivialaffair. The first question is whether our spacetime isMalament-Hogarth. The answer is currently unknown. Even if ourspacetime is not Malament-Hogarth globally, it might still containregions that have the Malament-Hogarth property locally. An example ofsuch a region is a huge, rotating black hole; there is evidence thatour universe contains such black holes (Etesi and Németi 2002).But even if there are Malament-Hogarth regions in our universe, thereremain considerable obstacles. For starters, (i) a machine thatrequires an unbounded amount of matter running for an infinite amountof time will malfunction with probability 1, rendering it useless(Button, 2009, 779), and (ii) the huge, rotating black hole that isclosest to us is probably out of our reach as well as ourdescendants’ reach (see also Németi and Dávid2006, Andréka, Németi, and Németi 2009,Andréka et al. 2018).

Quantum computing has also been invoked as a possible source ofhypercomputation. Quantum computing is the manipulation of qubits (andmore generally, qudits) in accordance with the laws of quantummechanics. Qubits are variables that, like bits, can be prepared ormeasured in one or two states, 0 and 1. Unlike bits, qubits can (i)take states that are a superposition of 0 and 1 and (ii) becomeentangled with each other during a computation. A surprising featureof quantum computing is that it allows computing certain functionsmuch faster than any known classical computation (Shor 1994). Butwhile mainstream quantum computing may be more efficient thanclassical computing, it does not allow computing any functions beyondthose computable by TMs.

Some authors have questioned whether the mainstream quantum computingparadigm is general enough and, if not, whether some aspects ofquantum mechanics may be exploited to design a quantum hypercomputer(Nielsen 1997, Calude and Pavlov 2002). The most prominent proposalfor a quantum hypercomputer is due to Tien Kieu (2002, 2003, 2004,2005). He argues that an appropriately constructed quantum system candecide whether an arbitrary Diophantine equation has an integralsolution — a problem which is known to be unsolvable by TMs.Kieu’s method involves encoding a specific instance of theproblem in an appropriate Hamiltonian, which represents the totalenergy of a quantum system. Kieu shows that such a system candynamically evolve over time into an energy ground state that encodesthe desired solution. Unfortunately, Kieu’s scheme does notappear to be workable. For one thing, it requires infinite precisionin setting up and maintaining the system (Hodges 2005). For anotherthing, Kieu does not provide a successful criterion for knowingwhen the system has evolved into the solution state, and theproblem of determining when the solution state is reached isunsolvable by TMs (Smith 2006b, Hagar and Korolev 2007). Thus,operating Kieu’s proposed hypercomputer would require alreadypossessing hypercomputational powers.

In conclusion, the candidate hypercomputers proposed so far have notbeen shown to be physically constructible and reliable. For the timebeing, Modest Physical CTT remains plausible. It may well be that forall practical purposes, any function that is physically computable isTuring-computable.

Bibliography

Anderson, N. G., 2017, “Information as a PhysicalQuantity,”Information Sciences, 415–416:397–413.
–––, 2022, “Generalized Landauer Bound forInformation Processing: Proof and Applications,”Entropy, 24(11): 1568. doi:10.3390/e24111568
Anderson, N. G., and G. Piccinini, 2024,The PhysicalSignature of Computation: A Robust Mapping Account, Oxford:Oxford University Press.
Andréka, H., Németi, I., and P. Németi, 2009,“General Relativistic Hypercomputing and Foundation ofMathematics,”Natural Computing, 8(3):499–516.
Andréka, H., Madarász, J. X., Németi, I., P.Németi, and G. Székely, 2018, “RelativisticComputation,” in Cuffaro and Fletcher 2018, pp.195–216.
Beggs, E. J., and J.V. Tucker, 2007, “Can Newtonian Systems,Bounded in Space, Time, Mass and Energy Compute all Functions?”Theoretical Computer Science, 371(1–2):4–19.
Block, N., 1978, “Troubles with Functionalism,” inPerception and Cognition: Issues in the Foundations ofPsychology, C. W. Savage (ed.), Minneapolis, University ofMinnesota Press, pp. 261–325.
Blum, L., Cucker F., Shub M., and S. Smale, 1998,Complexityand Real Computation, New York: Springer.
Bontly, T., 1998, “Individualism and the Nature of SyntacticStates,”British Journal for the Philosophy of Science,49(4): 557–574.
Bub, J., 2005, “Quantum Mechanics is About QuantumInformation,”Foundations of Physics, 35(4):541–560.
Burge, T., 1986, “Individualism and Psychology,”Philosophical Review, 45: 3–45.
Button, T., 2009, “SAD Computers and Two Versions of theChurch-Turing Thesis,”British Journal for the Philosophy ofScience, 60(4): 765–792.
Calude, C. S., 2005, “Algorithmic Randomness, QuantumPhysics, and Incompleteness,” inProceedings of theConference “Machines, Computations and Universality” (MCU2004), M. Margenstern (ed.), Berlin: Springer, pp.1–17.
Calude, C. S., and B. Pavlov, 2002, “Coins, QuantumMeasurements, and Turing’s Barrier,”QuantumInformation Processing, 1(1–2): 107–127.
Calude, C. S., and K. Svozil, 2008, “Quantum Randomness andValue Indefiniteness,”Advanced Science Letters, 1(2):165–168.
Campbell, D. I., and Yang, Y., 2021, “Does the solar systemcompute the laws of motion?”Synthese, 198:3203–3220.
Chalmers, D. J., 1995, “On Implementing aComputation,”Minds and Machines, 4:391–402.
–––, 1996, “Does a Rock Implement EveryFinite-State Automaton?”Synthese, 108:310–333.
–––, 2011, “A Computational Foundation forthe Study of Cognition,”Journal of Cognitive Science,12(4): 323–57.
–––, 2022, Reality+, New York: Norton.
Chrisley, R. L., 1995, “Why Everything Doesn’t RealizeEvery Computation,”Minds and Machines, 4:403–430.
Church, A., 1932, “A Set of Postulates for the Foundation ofLogic,”Annals of Mathematics, 33: 346–366.
–––, 1936, “An Unsolvable Problem inElementary Number Theory,”The American Journal ofMathematics, 58: 345–363.
Churchland, P. S., and T. J. Sejnowski, 1992,TheComputational Brain, Cambridge, MA: MIT Press.
Coelho Mollo, D., 2018, “Functional Individuation,Mechanistic Implementation: The Proper Way of Seeing the MechanisticView of Concrete Computation,” Synthese, 195(8):3477–97.
Copeland, B. J., 1996, “What is Computation?”Synthese, 108(3): 335–359.
–––, 2000, “Narrow Versus Wide Mechanism:Including a Re-Examination of Turing’s Views on the Mind-MachineIssue.”The Journal of Philosophy, XCVI(1):5–33.
–––, 2002, “Accelerating TuringMachines,”Minds and Machines, 12(2):281–301.
Crane, T., 1990, “The Language of Thought: No Syntax WithoutSemantics,”Mind and Language, 5(3):187–212.
Craver, C. F., 2012, “Functions and Mechanisms: APerspectivalist Account,” in P. Huneman (ed.),Functions, Dordrecht: Springer.
Cuffaro, M. E., and S. C. Fletcher, 2018,PhysicalPerspectives on Computation, Computational Perspectives onPhysics, Cambridge: Cambridge University Press.
Cummins, R., 1983,The Nature of PsychologicalExplanation, Cambridge, MA: MIT Press.
Curtis-Trudel, A., 2021, “Implementation asResemblance,”Philosophy of Science 88(5):1021–1032.
–––, 2022, “Why Do We Need A Theory ofImplementation?”The British Journal for the Philosophy ofScience, 73(4): 1067–1091.
–––, 2024, “Computation in Context”Erkenntnis, doi:10.1007/s10670-024-00851-2
Davies, E. B., 2001, “Building Infinite Machines,”British Journal for the Philosophy of Science, 52(4):671–682.
Davis, M., 2004a, “The Myth of Hypercomputation,” inAlan Turing: Life and Legacy of a Great Thinker, C. Teuscher(ed.), Berlin: Springer, pp. 195–211.
––– (ed.), 2004b,The Undecidable: BasicPapers on Undecidable Propositions, Unsolvable Problems and ComputableFunctions, Dover: Mineola.
Dennett, D. C., 1987,The Intentional Stance, Cambridge,MA: MIT Press.
Deutsch, D., 1985, “Quantum Theory, the Church-TuringPrinciple and the Universal Quantum Computer,”Proceedingsof the Royal Society of London A, 400: 97–117.
Dewhurst, J., 2018, “Computing Mechanisms Without ProperFunctions,”Minds and Machines 28(3): 569–588.
Drayson, Z., 2024, “Defending the Medium-independence ofComputation,”Mind & Language, first online 22 June2025. doi:10.1111/mila.12536
Dretske, F. I., 1981,Knowledge and the Flow ofInformation, Cambridge, MA: MIT Press.
Duwell, A., 2017, “Exploring the Frontiers of Computation:Measurement Based Quantum Computers and the Mechanistic View ofComputation,” in A. Bokulich and J. Floyd (eds.), Turing 100:Philosophical Explorations of the Legacy of Alan Turing (BostonStudies in the Philosophy and History of Science: Volume 324), NewYork: Springer, 219–32.
Earman, J., 1986,A Primer on Determinism, Dordrecht: D.Reidel.
Earman, J., and J. Norton, 1993, “Forever is a Day:Supertasks in Pitowsky and Malament-Hogarth Spacetimes,”Philosophy of Science, 60: 22–42.
Egan, F., 1999, “In Defence of Narrow Mindedness.”Mind and Language, 14(2): 177–194.
–––, 2010, “Computational Models: A ModestRole For Content,”Studies in the History and Philosophy ofScience, 41(3): 253–259.
–––, 2025,Deflating MentalRepresentation, Cambridge, MA: MIT Press.
Etesi, G., and I. Németi, 2002, “Non-TuringComputations via Malament-Hogarth Spacetimes,”InternationalJournal of Theoretical Physics, 41: 342–370.
Feynman, R. P., 1982, “Simulating Physics withComputers,”International Journal of TheoreticalPhysics, 21(6–7): 467–488.
Fletcher, S. C., 2018, “Computers inAbstraction/Representation Theory,”Minds and Machines,28(3): 445–63.
Floridi, L., 2008, “A Defence of Informational StructuralRealism,”Synthese, 161(2): 219–53.
Fodor, J. A., 1975,The Language of Thought, Cambridge,MA: Harvard University Press.
–––, 1981, “The Mind-Body Problem,”Scientific American, 244: 114–125.
–––, 2008,LOT 2: The Language of ThoughtRevisited, Oxford: Oxford University Press.
Fredkin, E., 1990, “Digital Mechanics: An InformationProcess Based on Reversible Universal Cellular Automata,”Physica D, 45: 254–270.
–––, 2003, “An Introduction to DigitalPhilosophy.”International Journal of TheoreticalPhysics, 42(2): 189–247.
Fresco, N., 2010, “Explaining Computation Without Semantics:Keeping It Simple,”Minds and Machines, 20:165–181.
–––, 2014,Physical Computation andCognitive Science, New York: Springer.
Fuentes, J. I., 2024, “Computational Systems as Higher-orderMechanisms,”Synthese, 203(2), first online 02 February2024. doi:10.1007/s11229-023-04482-y
Fuchs, C. A., 2004, “Quantum Mechanics as QuantumInformation (and only a little more),” inQuantum Theory:Reconsiderations of Foundations, A. Khrennikov (ed.),Växjö, Sweden: Växjö University Press, pp.463–543.
Gandy, R., 1980, “Church’s Thesis and Principles forMechanism,” in J. Barwise, H. J. Keisler, K. Kunen (eds.),The Kleene Symposium: Studies in Logic and the Foundations ofMathematics, Amsterdam: North-Holland Publishing.
Garson, J., 2013, “The Functional Sense of Mechanism,”Philosophy of Science, 80: 317–333.
Giunti, M., 2017, “What is a Physical Realization of aComputational System?”Isonomia, 9: 177–192.
Gödel, K., 1934, “On Undecidable Propositions of FormalMathematical Systemsm,” inThe Undecidable, M. Davis(ed.), Ewlett, NY: Raven, pp. 41–71.
–––, 1936. “Über die Lange vonBeweisen,”Ergebnisse eines mathematischen Kolloquiums,7: 23–24.
–––, 1946, “Remarks Before the PrincetonBicentennial Conference on Problems in Mathematics,” reprintedin Davis 2004b, pp. 84–88.
Godfrey-Smith, P., 2009, “Triviality Arguments AgainstFunctionalism,”Philosophical Studies, 145(2):273–295.
Grice, H. P., 1957, “Meaning,”The PhilosophicalReview, 66(3): 377–388.
Hagar, A., and A. Korolev, 2007, “QuantumHypercomputation--Hyper or Computation?,”Philosophy ofScience, 74(3): 347–363.
Hamkins, J. D., 2002, “Infinite Time Turing Machines,”Minds and Machines, 12: 521–539.
Heemskerk, J., 2025,How Informational Teleosemantics Works:Towards a Realist Theory of Content, Ph.D. Dissertation,University of Warwick.
Harman, G., 1987, “(Nonsolipsistic) Conceptual RoleSemantics,” inNew Directions in Semantics, E. Lepore(ed.), London: Academic Press, pp. 55–81.
Hogarth, M. L., 1994, “Non-Turing Computers and Non-TuringComputability,”PSA 1994(1): 126–138.
–––, 2004, “Deciding Arithmetic Using SADComputers,”British Journal for the Philosophy ofScience, 55: 681–691.
Horsman, D., V. Kendon, and S. Stepney, 2018,“Abstraction/Representation Theory and the Natural Science ofComputation,” inPhysical Perspectives on Computation,Computational Perspectives on Physics, M. E. Cuffaro and S. C.Fletcher (eds.), Cambridge: Cambridge University Press, pp.127–49.
Horsman, D., S. Stepney, R. C. Wagner, and V. Kendon, 2014,“When Does a Physical System Compute?” inProceedingsof the Royal Society of London A, 470(2169).doi:10.1098/rspa.2014.0182
Isaac, A. M. C., 2019, “The Semantics Latent in ShannonInformation,”The British Journal for the Philosophy ofScience 70(1): 103–125.
Jacquette, D., 1991, “The Myth of Pure Syntax,” inTopics in Philosophy and Artificial Intelligence, L.Albertazzi and R. Rolli (eds.), Bozen: Istituto Mitteleuropeo diCultura, pp. 1–14.
Kantor, F. W., 1982, “An Informal Partial Overview ofInformation Mechanics,”International Journal of TheoreticalPhysics, 21(6–7): 525–35.
Kaplan, D. M., 2011, “Explanation and Description inComputational Neuroscience,”Synthese, 183(3):339–373.
Kersten, L., 2024, “An Idealised Account of MechanisticComputation,”Synthese, 203(99), first online 14 March2024. doi:10.1007/s11229-024-04526-x
Kieu, T. D., 2002, “Quantum Hypercomputation,”Minds and Machines, 12(4): 541–561.
–––, 2003, “Computing theNoncomputable,”Contemporary Physics, 44:51–71.
–––, 2004, “A Reformulation ofHilbert’s Tenth Problem through Quantum Mechanics,”Proceedings of the Royal Society A, 460(2045):1535–1545.
–––, 2005, “An Anatomy of a QuantumAdiabatic Algorithm that Transcends the Turing Computability,”International Journal of Quantum Information, 3(1):177–183.
Kirkpatrick, K. L., 2022, “Biological Computation: Heartsand Flytraps,”Journal of Biological Physics, 48(1):55–78.
Kleene, S. C., 1935, “A Theory of Positive Integers inFormal Logic,”American Journal of Mathematics, 57:153–173 and 219–244.
–––, 1952,Introduction toMetamathematics, Princeton: Van Nostrand.
Klein, C., 2008, “Dispositional Implementation Solves theSuperfluous Structure Problem,”Synthese, 165:141–153.
Kuokkanen, J., 2022, “Vertical-horizontal Distinction inResolving the Abstraction, Hierarchy, and Generality Problems of theMechanistic Account of Physical Computation,”Synthese,200(3), 247. doi:10.1007/s11229-022-03725-8
Ladyman, J., S. Presnell, A. J. Short, and B. Groisman, 2007,“The Connection between Logical and ThermodynamicIrreversibility,”Studies in History and Philosophy ofScience Part B: Studies In History and Philosophy of ModernPhysics, 38(1): 58–79.
Lee, J., 2021, “Mechanisms, Wide Functions, and Content:Towards a Computational Pluralism,”The British Journal forthe Philosophy of Science, 72(1): 221–244.
Leff, H. S. and A.F. Rex, (eds.), 2003,Maxwell’s Demon2: Entropy, Classical and Quantum Information, Computing.Bristol: Institute of Physics Publishing.
Lent, C. S., Orlov, A. O., Porod, W., and G. L. Snider, (eds.),2019,Energy Limits in Computation: A Review of Landauer’sPrinciple, Theory and Experiments, Berlin: Springer.
Lloyd, S., 2006,Programming the Universe: A Quantum ComputerScientist Takes on the Cosmos. New York: Knopf.
Lycan, W., 1981, “Form, Function, and Feel,”Journal of Philosophy, 78(1): 24–50.
Machamer, P. K., Darden, L., and C. Craver, 2000, “ThinkingAbout Mechanisms,”Philosophy of Science, 67:1–25.
Maley, C. J., 2023, “Analogue Computation andRepresentation,”The British Journal for the Philosophy ofScience,74(3): 739–769.
Martin, C. B., 1997, “On the Need for Properties: The Roadto Pythagoreanism and Back,”Synthese, 112(2):193–231.
Maudlin, T., 1989, “Computation and Consciousness,”Journal of Philosophy, 86(8): 407–432.
Milkowski, M., 2013,Explaining the Computational Mind,Cambridge, MA: MIT Press.
Millhouse, T., 2019, “A Simplicity Criterion for PhysicalComputation,”The British Journal for the Philosophy ofScience, 70(1): 153–78.
Mills, J. W., 2008, “The Nature of the Extended AnalogComputer,”Physica D: Nonlinear Phenomena, 237(9):1235–1256.
Németi, I., and G. Dávid, 2006, “RelativisticComputers and the Turing Barrier,”Journal of AppliedMathematics and Computation, 178(1): 118–142.
Nielsen, M. A., 1997, “Computable Functions, QuantumMeasurements, and Quantum Dynamics,”Physical ReviewLetters, 79(15): 2915–2918.
Nielsen, M. A., and I. L. Chuang, 2000,Quantum Computationand Quantum Information. New York: Cambridge UniversityPress.
Norton, J. D., 2003, “Causation as Folk Science,”Philosophers’ Imprint, 3(4): 1–22.
Ord, T., 2006, “The Many Forms of Hypercomputation,”Applied Mathematics and Computation, 178(1):143–153.
Papayannopoulos, P., 2020, “Computing and modelling: Analogvs. Analogue,”Studies in History and Philosophy of SciencePart A, 83: 103–120.
Piccinini, G., 2004, “Functionalism, Computationalism, andMental Contents,”Canadian Journal of Philosophy,34(3): 375–410.
–––, 2007, “Computing Mechanisms,”Philosophy of Science, 74(4): 501–526.
–––, 2015,Physical Computation: AMechanistic Account, Oxford: Oxford University Press.
–––, 2020,Neurocognitive Mechanisms:Explaining Biological Cognition, Oxford: Oxford UniversityPress.
Piccinini, G. and A. Scarantino, 2011, “InformationProcessing, Computation, and Cognition,”Journal ofBiological Physics 37(1): 1–38.
Pitowsky, I., 1990, “The Physical Church Thesis and PhysicalComputational Complexity,”Iyyun, 39: 81–99.
–––, 2002, “Quantum Speed-Up ofComputations,”Philosophy of Science, 69:S168–S177.
Pour-El, M. B., 1974, “Abstract Computability and ItsRelation to the General Purpose Analog Computer (Some ConnectionsBetween Logic, Differential Equations and Analog Computers),”Transactions of the American Mathematical Society, 199:1–28.
–––, 1999, The Structure of Computability inAnalysis and Physical Theory: An Extension of Church’s Thesis.InHandbooks of Computability Theory, E.R. Griffor (ed.), NewYork: Elsevier, pp. 449–471.
Pour-El, M. and I. Richards, 1989,Computability in Analysisand Physics, Perspectives in Mathematical Logic, Berlin:Springer-Verlag.
Putnam, H., 1960, “Minds and Machines,” inDimensions of Mind: A Symposium, S. Hook (ed.), New York:Collier, pp. 138–164; Reprinted in Putnam 1975a, pp.362–386.
–––, 1967, “PsychologicalPredicates,” inArt, Mind, and Religion, W.H. Capitan& D.D. Merrill (eds.), Pittsburgh, PA: University of PittsburghPress, pp. 37–48. Reprinted in Putnam 1975a as “The Natureof Mental States,” pp. 150–161.
–––, 1975a,Philosophical Papers: Volume 2,Mind, Language and Reality, Cambridge: Cambridge UniversityPress.
–––, 1975b, “The Meaning of‘Meaning’,” inLanguage, Mind and Knowledge.Minnesota Studies in the Philosophy of Science, vol. 7, K.Gunderson (ed.), Minneapolis: University of Minnesota Press, pp.131–193. Reprinted in Putnam 1975a, pp. 215–271.
–––, 1988,Representation and Reality,Cambridge, MA: MIT Press.
Pylyshyn, Z. W., 1984,Computation and Cognition,Cambridge, MA: MIT Press.
Quine, W. V. O., 1976, “Whither Physical Objects?” inEssays in Memory of Imre Lakatos, (Series: Boston Studies inthe Philosophy of Science), R.S. Cohen, P.K. Feyerabend, & M.W.Wartofsky (eds.), Dordrecht: Reidel, pp. 497–504.
Rescorla, M., 2014, “A Theory of ComputationalImplementation,”Synthese, 191: 1277–1307.
Rubel, L. A., 1989, “Digital Simulation of AnalogComputation and Church’s Thesis,”Journal of SymbolicLogic, 54(3): 1011–1017.
–––, 1993, “The Extended AnalogComputer,”Advances in Applied Mathematics, 14(1):39–50.
Scheutz, M., 1999, “When Physical Systems Realize Functions…,”Minds and Machines, 9(2):161–196.
–––, 2001, “Causal versus ComputationalComplexity,”Minds and Machines, 11(4):534–566.
Schonbein, W., 2005, “Cognition and the Power of ContinuousDynamical Systems,”Minds and Machines, 15(1):57–71.
Searle, J. R., 1992,The Rediscovery of the Mind,Cambridge, MA: MIT Press.
Segal, G., 1991, “Defence of a ReasonableIndividualism,”Mind, 100(400): 485–493.
Seth, A. K., 2025, “Conscious Artificial Intelligence andBiological Naturalism,”Behavioral and Brain Sciences,first online 21 April 2025. doi:10.1017/S0140525X25000032
Shagrir, O., 2001, “Content, Computation andExternalism,”Mind, 110(438): 369–400.
–––, 2006, “Why We View the Brain as aComputer,”Synthese, 153(3): 393–416.
–––, 2022,The Nature of PhysicalComputation, Oxford: Oxford University Press.
Shagrir, O., and I. Pitowsky, 2003, “PhysicalHypercomputation and the Church-Turing Thesis,”Minds andMachines, 13(1): 87–101.
Shannon, C. E., and W. Weaver, 1949,The Mathematical Theoryof Communication, Urbana: University of Illinois Press.
Shapiro, L. A., 1997, “A Clearer Vision,”Philosophy of Science, 64(1): 131–153.
Shor, P. W., 1994, “Algorithms for Quantum Computation:Discrete Logarithms and Factoring,” inProceedings of the357th Annual Symposium on Foundations of Computer Science, LosAlamitos, CA: IEEE Computer Society Press, pp. 124–134.
Sieg, W., 2006, “On Computability,” inPhilosophyof Mathematics (Handbook of the Philosophy of Science), A. Irvine(ed.) Amsterdam: Elsevier, pp. 535–630.
Siegelmann, H. T., 1999,Neural Networks and AnalogComputation: Beyond the Turing Limit, Boston:Birkhäuser.
Smith, B. C., 2002, “The Foundations of Computing,” inComputationalism: New Directions, M. Scheutz (ed.),Cambridge, MA: MIT Press, pp. 23–58.
Smith, W. D., 2006a, “Church’s Thesis Meets theN-body Problem,”Applied Mathematics andComputation, 178(1): 154–183.
–––, 2006b, “Three CounterexamplesRefuting Kieu’s Plan for Quantum Adiabatic Hypercomputation; andSome Uncomputable Quantum Mechanical Tasks,”AppliedMathematics and Computation, 178(1): 184–193.
Sprevak, M., 2010, “Computation, Individuation, and theReceived view on Representation,”Studies in History andPhilosophy of Science Part A, 41(3): 260–270.
Stabler, E. P., Jr., 1987, “Kripke on Functionalism andAutomata,”Synthese, 70: 1–22.
Stannett, M., 1990, “X-Machines and the Halting Problem:Building a Super-Turing Machine,”Formal Aspects ofComputing, 2(1): 331–341.
Stich, S., 1983,From Folk Psychology to CognitiveScience, Cambridge, MA: MIT Press.
Tegmark, M., 2014,Our Mathematical Universe: My Quest for theUltimate Nature of Reality, New York: Random House.
Toffoli, T., 1982, “Physics and Computation,”International Journal of Theoretical Physics, 21(3–4):165–175.
Turing, A. M., 1936–7, “On Computable Numbers, with anApplication to the Entscheidungsproblem,”Proceeding of theLondon Mathematical Society, 42(1): 230–265, reprinted inDavis 2004b, pp. 116–154.
–––, 1950, “Computing Machinery andIntelligence,”Mind, LIX(236): 433–460.
Wheeler, J. A., 1982, “The Computer and the Universe,”International Journal of Theoretical Physics, 21(6–7):557–572.
Wiggershaus, N., 2025, “Physical Programmability,”Minds and Machines, 35(2): 1–29.
Wolfram, S., 2002,A New Kind of Science, Champaign, IL:Wolfram Media.
Zuse, K., 1970,Calculating Space. Cambridge, MA: MITPress.
–––, 1982, “The Computing Universe,”International Journal of Theoretical Physics, 21(6–7):589–600.

Academic Tools

How to cite this entry.
Preview the PDF version of this entry at theFriends of the SEP Society.
Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

Gandy, R., 1993, “>On the Impossibility of Using Analogue Machines to Calculate Non-computable Functions,” manuscript at arXiv.org.
Hodges, A., 2005, “Can quantum computing solve classically unsolvable problems?” [PDF].
Bibliography on Computation and Physical Systems, at thePhilPapers website.
special issue of the journalEntropy, published by MDPI (aka Multidisciplinary Digital PublishingInstitute).

Acknowledgments

Many thanks to Neal Anderson, David Chalmers, Nir Fresco, Corey Maley,Mark Sprevak, Fred Kroon, Ray Turner, and several anonymous refereesfor helpful comments on previous drafts. Thanks to James Virtel foreditorial assistance. This material is based in part upon worksupported by the National Science Foundation under Grant No.SES-0924527.

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free

Browse

About

Support SEP

Mirror Sites

View this site from another server:

USA (Main Site)Philosophy, Stanford University

Info about mirror sites

Library of Congress Catalog Data: ISSN 1095-5054

Movatterモバイル変換