14

It has always puzzled me when people casually make comments like "Since the brain is a Turing Machine...". Just to clarify: I'm talking about generic discussions, not philosophical journals here.

What would lead someone to even speculate about that, much less accept it as dogma? Here are the reasons I find the comparison puzzling:

  1. Brains are finite; Turing Machines are infinite. If you want to compare the brain to a computational model, you should compare it to a finite state machine, not a Turing machine.
  2. Why would you compare the brain to any state machine, whether Turing or finite? Computation is something people don't do particularly well, and certainly not perfectly like a state machine.
  3. On the other hand, people do lots of things that state machines don't do at all, such as refer, love, lie, and seek.
  4. A Turing Machine executes a fixed set of state transitions. Nothing like that is observed in the brain (beyond certain tiny areas of neuron firing). If the brain is a state machine, it is one where the state transitions are constantly in flux, changing based on sensory input and body chemistry. It's hard to believe any set of state transitions could encode that behavior, because it is likely neither consistent nor discrete (that is, there is a continuous range of changes).

I know that people think computers will one day be able to simulate human behavior (I myself believe that is likely), and that they think the mind somehow supervenes on this behavior, but a computer is not a Turing Machine; it is a finite state machine. So the claim is really that one day a finite state machine will be able to simulate human behavior, once again, where does the Turing Machine come in--even given the implausible speculation that the mind somehow supervenes on behavior?

1

6 Answers 6

18

A little background: there's a funny fact about computers that a very crude system with a primitive programming language can solve every computable problem (given enough memory). As we write better languages, make better CPU's, add parallelism and so on, we're just adding speed and comfort. A Turing machine is the crudest system which does this. For this purpose we don't care about how it works -- using states or the infinite tape simplification -- we care about it being a member of the "can solve every computer problem" club (which finite state machines aren't a member of).

Because of that, the name for being in the club is "Turing Complete". It's such a weird concept that it gets over-simplified and tossed about in a joke-y way. For example when there's a new way to program with some terrific features, you can show your sophistication by saying "but it's still just Turing Complete". Or it's fun to show that the way you program robots in some game is Turing Complete -- it's also the most powerful system in the world, ha-ha.

So it sounds to me as if that remark is mixing up being a Turing machine with being Turing Complete, and is saying "as we know, all thinking machines are identical; the brain is a thinking machine; therefore it must also be Turing Complete. Like a Turing Machine it may work differently, but the brain still solves the same problems, which is the important thing". Or simplified, it's the absolutely banal remark "the brain is just another computer".

19
  • 1
    So 'It's still Turing complete' is a functional equivalent of 'That's just syntactical sugar'? :D
    – J D
    May 1 at 16:34
  • 4
    BTW, this is a fantastic reduction to a comprehensible idea emphasizing Turing completeness as a property of the human mind.
    – J D
    May 1 at 16:35
  • 2
    One quibble: you write "can solve every problem you can ever think of", which is not correct. The Church/Turing hypothesis is not that Turing machines/lambda calculus can solve every problem, but that they can solve every problem that any system system based on mechanical steps can solve. That is, there is no possible system that meets the restrictions and can solve problems these systems can't solve. May 1 at 20:43
  • 4
    by the way, unless a system has particularly limited amounts of memory, usually we ignore the fact that it's not infinite. As long as it's got enough memory to solve real problems we still tend to call it Turing-complete.
    – user253751
    May 2 at 9:11
  • 1
    "the crudest system which does this" - this is similar to how AI is not really smart, it is actually very dumb, it is just dumb very very fast, so it can iterate through lots of dumb solutions until it stumbles upon a good one. A chess program configured to be an equal opponent to a given human player is not actually as smart as that player, it can just calculate through much more stupid moves (because it's so fast) until it finds one which works.
    – vsz
    May 3 at 7:16
9

The Church-Turing thesis suggests that any machine we can build is no more powerful than a Turing machine.

It is possible to run an approximate numerical simulation of physics, on a computer. A computer is no more powerful than a Turing machine.

The brain is nothing more than physics. So, it is possible in theory to run a numerical simulation of the brain, on a Turing machine.

Furthermore, Turing machines are a concrete and well-understood model, which is simple to describe, and about which many theorems are known. That's the advantage to modeling the brain as a Turing machine running a particular physics simulation program.

Brains are finite; Turing Machines are infinite. If you want to compare the brain to a computational model, you should compare it to a finite state machine, not a Turing machine.

You are correct that the brain lacks an infinite tape like a Turing machine has. The brain can't store unlimited memories. So this is a way in which the brain might not be as powerful as a Turing machine. However, in practice, humans can augment their natural memory artificially, such as by writing things down on paper. And we can keep making more paper. So while the brain (plus pen and paper) might technically be less powerful than a Turing machine, we can usefully approximate it as a Turing machine.

Theoretical computer scientists don't usually model computers as finite state machines, although technically they could do so. They model computers as Turing machines, because that model captures more of the structure of the computer. The Turing machine model of a computer emphasizes the distinction between the general rules of operation of the computer (which are fixed), and the specific data the computer is operating on at a given time. The fact that computers have finite memories doesn't matter too much, because in practice usually computers do not run out of storage, and if they do, more storage can be added.

It's useful to model the brain as a Turing machine, rather than a state machine, for similar reasons. As above, Turing machines have the advantage that they can have a short "program" (state machine) that describes general rules of behavior, and a large amount of "data" (tape configuration) to which the rules are applied. This is similar to how a physics simulation of the brain would have a relatively short set of rules describing the physics, applied to a very large amount of data describing the brain state.

Why would you compare the brain to any state machine, whether Turing or finite? Computation is something people don't do particularly well, and certainly not perfectly like a state machine.

When you say people don't do "computation" particularly well, you're making a very broad and strong claim. People who believe the brain should be modeled as a Turing machine would object to that, on the basis that the neural activity involved in throwing a baseball is a very large amount of computation, which humans are very good at! In other words, these people have a broader notion of the word "computation" than the one you are familiar with.

So let's assume you're instead talking more specifically about symbolic manipulations, such as arithmetic. It doesn't matter that humans are bad at this; most artificial neural networks aren't good at arithmetic, either, but they do run on computers. Remember analog computers? These don't do symbolic computation at all, but they are still "computers" that perform "computations."

On the other hand, people do lots of things that state machines don't do at all, such as refer, love, lie, and seek.

Machines do "refer"; what is a pointer? What is a hyperlink? What is a filename? These things are data that refers to other data. And certainly machines can seek; all sorts of intelligent agents seek goals. Machines can also "lie" in the sense of giving false information for selfish benefit. Can they love? Perhaps not yet. What is love?

A Turing Machine executes a fixed set of state transitions. Nothing like that is observed in the brain (beyond certain tiny areas of neuron firing). If the brain is a state machine, it is one where the state transitions are constantly in flux, changing based on sensory input and body chemistry. It's hard to believe any set of state transitions could encode that behavior, because it is likely neither consistent nor discrete (that is, there is a continuous range of changes).

As mentioned earlier, the state machine for a Turing machine simulating the brain would have only the laws of physics, which are indeed fixed. Everything else - all the contents of the brain - would be data on the tape. So there is no need for the state transitions of the Turing machine to change over time.

1
5

Short Answer

It's not correct to say that AI researchers model the brain with Turing Machines (TMs), rather it's more accurate to say that AI researchers understand that the grammars of human language can be approximated with TMs. There is a logical equivalence between grammars and state machines and the thinking largely follows along the line that whatever it is about intelligence that allows people to use language allows us to trace back language and its mechanisms to intelligence. A militant belief in this is much less common these days with alternative connectionist models (models that mimic neuronal complexity and computation) being much more philosophically interesting; in fact, some researchers are trying to extend connectionism into the affective domain of human thought in ways that symbolic models cannot. Thus, while TMs are not models of brains, they share important properties of brains and can be used to create functional equivalences of the brain, so it is useful to compare and contrast them or use them to build connectionist and symbolic systems.

Long Answer

The Properties Brains and Embodied TMs Share

Philosophically, what AI/AGI researchers have been and currently are engaged in is an attempt to explain and characterize increasingly generalized forms of intelligence. I'm not aware of any assertions that TMs model the brain, but they can:

  1. Handle grammars like people can (uniquely in the animal kingdom)
  2. Are general purpose computers that can execute generalized action because they embody the same information processing cycle as people do; probably a derivative property of how grammars model the world

Thus, an embodied TM (the TM is an abstraction) represents two very important capacities, language and flexibility of action, that other animal do not possess. Thus, it is not a coincidence that computers like ENIAC which embody the von Neumann architecture have gone from doing simple arithmetic to classifying images of plants and driving cars sometimes better than people. The capacity for grammars, and therefore true language (as opposed to a system of signals) is fundamentally characterized by expressivity and that expressivity is fundamentally linked to generalized processing of information and action predicated upon that information. Now, in the early days, this was a good start, but fundamental challenges haven't been overcome. The dominant, or at least the vocal consensus, has been from the beginning that somehow language is not only essential, but is a pathway to the notion of generalized intelligence, a notion that has a number of competing theoretical models such as MI on the pluralistic front and the g-factor in the traditional psychometrics communities. But the question of what intelligence is is itself still very controversial among philosophers. The scientific approach is to establish a definition of intelligence through epistemic methodologies. That is the essence of an IQ test which indirectly purports that the measurement conducted by the test is de facto proof of the existence of the thing called 'intelligence'. Thus, a TM can do things that not even Koko the Gorilla can do. (Of course, Koko's lack of grammatical capacity is one of many intelligences that have yet to be built on a TM.)

Language, Intelligence, and Computation

In fact, Alan Turing's leap in his paper of universal renown was to establish an operational definition that measures language skills to make a pronouncement about intelligence, and if you read the paper carefully, what Turing claims is that given the electronic computers which might even need to learn in the same way as children, there's a functional equivalency between all agents that can handle a grammar equally well. When a person, under a game-like condition, can't really tell who the person is and who the computer is (yes, who), then computer is evincing human-level intelligence. To be explicit, no system to this day has done that, so there's a very solid theory in place regarding grammars, agency, and intelligence.

The earliest AI community was very optimistic that if symbols could just be entered and produced with enough quality and quantity, human-level intelligence would emerge in the technical sense. And some of the most famous pioneers in electronic computation put forth the physical symbol system hypothesis

A physical symbol system has the necessary and sufficient means for general intelligent action.
— Allen Newell and Herbert A. Simon

From this perspective, then, the question is how to do we make TMs manipulate symbols in a fashion to reproduce what humans can do. There have always been those who question this perspective, and certainly Hubert Dreyfus is one of the most famous of those upsetting many AI researchers with his view starting with a paper published at RAND and then moving on to expand those ideas with What Computers Can't Do. He raised obviously many of the same objections you have with enough academic reputation to deflate optimism, cancel funding, and discourage thinkers. There are still thinkers who believe in GOFAI, but these days, younger thinkers are encouraged that a long-standing thread in AI, that of connectionism, will add to the philosophical body of knowledge of AI to bring AI closer inline with the dream of developing AGI stemming from an artificial machine that somehow produces information LIKE the brain. And among those who know robotics, the claims have drawn light to the question of the inter-relation between the software and the hardware architecture which has deep philosophical implications. Today, such views are philosophically known as embodied cognition which says that symbols systems are fine, but they need to be tethered to some body in the physical world so that transduction can play a role in machine learning. The result has been that over the last 20 years, AI researchers have focused on methods for supervised and unsupervised learning which, instead of attempt to instruct a computer like a child is instructed using rule sets and language (think expert systems for instance), exposure of connectionist models to raw input condition the machine to develop a sense of normativity. Thus, a computer can now read your cursive, decide if your pet is a dog, decide the fastest way to ship a package to you, and drive you to work, none of which require explicitly encoding domain-centric rules (though a synergy is superior) resp., handwritten allographs, image recognition, logistics, and transportation; these connectionist and hybrid models instead rely on being exposed to similar contexts and then abstract what can only be describe as intuitions. Honestly, it's not unfair to characterize machine learning systems as possessing intentionality in a primitive sense, though many thinkers bridle at the suggestion. But whether one leans towards symbols or connectionis as a model for imbuing intelligence, both can be implemented on an embodied TM. Thus, brains and TMs can be shown to have some very powerful properties in common.

Today, TMs are tremendously important for understanding how to model the functions of the brain, but for reasons as you have discussed, many researchers believe that the TM is only part of the necessary design of a system to manifest greater and greater levels of intelligence and are not sufficient. TMs are algorithmic and human minds often are not. Most AI people I've known or read think that there's a symbol-connectionist synergy at work, and that new generations of AI technology will continue to employ both strategies. The brain, after all, is not a von Neumann or Harvard machine, but is this object conjoined in a fantastically complicated way with a body, and that both are connectionist in ways that simply that we can't hope to deliberately articulate with grammar. You could use a TM to encode rules to recognize faces, for instance, but that's very difficult. Instead, facial recognition uses the TM indirectly and builds up an abstraction to allow for machine learning from physical inputs in a way that our intuitions about people's faces might inform our conversations about them.

9
  • +1 Regarding your first sentence, I wish AI researchers were more careful with their language in the popularization of their work – treat it as informing rather than marketing. I agree researchers are more careful in what they actually think, and they understand Turing machines are an oversimplification. However, the language they use is often misleadingly ambitious. May 1 at 0:07
  • 3
    I don't understand your point about GOFAI vs. connectionism and how that relates to the idea that a "TM is only part of the necessary design"--a Turing machine can just as easily simulate a connectionist network as a GOFAI system, no? I don't think many AI researchers including Turing himself claimed that the architecture of a Turing machine was a good model for the architecture of the brain, just that if the brain can be modeled by any of the very broad class of computable functions, a Turing machine could simulate it, since it can simulate all functions in that class.
    – Hypnosifl
    May 1 at 2:30
  • @Hypnosifl The functional equivalence between symbolic systems and connectionist ones adds a layer of complexity to the discussion that is unwarranted by the nature of the question. One can use a set of op codes to build an ANN to simulate a TM or an equivalent model, but doing so muddies the philosophical waters. To appeal to the intuition of a thinker means partitioning the concepts to reflect the conceptual model of the thinker...
    – J D
    May 1 at 16:28
  • So, while an RNN and a TM may be reduced or shown to be equivalent in some fashion, they inherently appeal to different conceptual metaphors and that's the core of philosophical disourse, IMNSHO: to craft linguistic categories to resonate with each other, since the fundamental unit of semantics is morpheme. Thus, the choice to use the distinction between connectionist models that emulate neural computation and TMs to model human language and action is to appeal to our respective intuitions of each. To do so is pedagogical not logical...
    – J D
    May 1 at 16:31
  • 1
    Note in particular that in Turing's original paper he first has an extended discussion of computational universality (also known as Turing completeness) starting on p. 439, then on p. 442 says that in light of universality, the general question of whether any type of discrete state machine can emulate human thinking can be replaced with the question of whether a digital computer (a Turing machine) can do so.
    – Hypnosifl
    May 1 at 16:56
4

A world-view describing question. If you ask whether the Turing machine is a model of the brain, the answer tells more about the answerer than one might guess at first glance.

Neither classical physics nor non-relativistic Quantum Mechanics admit a more powerful computing device than a Turing machine, and nobody believes the human brain has relativisticly significant components. Therefore, if you believe that this world is all there is, you must inherently believe the brain is no more powerful than a Turing machine.

Or a more interesting thesis: If you believe that brain upload and duplication is possible then you therefore believe that this world is all there is. Note that the converse is not true. If you believe that brain upload is not possible for one of a myriad of reasons than I don't know if you believe whether or not this world is all there is. On the other hand, if you believe brain upload is possible but duplication is not, then I know either you do not know how computers work or you believe this world is not all there is.

And now for the details

Classical mechanics does not and never did admit a more powerful computing device than a Turing machine. In theory it was proposed that an oracle machine could exist but there is no way to construct one, and it doesn't matter because Quantum Mechanics.

Non-relativistic Quantum Mechanics prohibits any oracle machine and any arbitrary reals calculation machine that someone may have from the classical mechanics calculation. The Heisenberg uncertainty principle puts a hard limit on computing complexity per unit size. Certain physicists cast about looking for a way of escape that they might bend the rules (say maybe, the intermediate calculations don't need to be within the Heisenberg limits) but no mechanism was ever found and all who found traction did so using General Relativistic tricks. And that we can convince ourselves the brain does not do with an MRI.

4
  • There is one function that human brain may or may not have that would be outside Turing machines: ability to provide different random numbers from exactly same starting condition. We do not know whether quantum uncertainty affects brain function at this level, but it certainly could. And a correctly functioning Turing machine would never be affected by quantum uncertainty, though in any real world implementation there is always a chance of rare tunneling effects.
    – jpa
    May 2 at 10:26
  • @jpa: 1) The brain is bad at random numbers. 2) Even if true, that is not physically interesting. Real computers can produce random numbers and adding this to the model is a trivial tweak to a Turing machine to add the capacity and tells us nothing of physics or computation or human cognition for that matter.
    – Joshua
    May 2 at 13:58
  • "If you believe that brain upload and duplication is possible then you therefore believe that this world is all there is." I don't think that's necessarily true. I can imagine both a non-physical consciousness duplicating to split over both (virtual) brains, as well as one connecting to both. But I do agree it's a hypothetical that can't simply get a free pass.
    – towr
    May 3 at 6:50
  • @towr: I would expect rather connecting to both or connecting to neither, both of which would be detectable rather fast.
    – Joshua
    May 3 at 14:00
2

Integers

It's all about the integers. Turing machines are capable of computing any computable function. Therefore, the only way the brain cannot be mathematically described by a Turing machine is if it is capable of computing a non-computable function. Now, "computable function" has a very precise definition in mathematics/computer science, and has almost nothing to do with pop-sci ideas of giving a robot AI a riddle so hard its CPU explodes.

Pretty much any function that takes a finite list of integers as input and produces a finite list of integers as output is computable, and therefore, one can build a Turing machine which implements the function. Some functions involving real numbers are also computable. But the important point to understand is that all uncomputable functions involve an uncomputable number somewhere. An uncomputable number is, roughly speaking, a number so complex that there is no finite process to write it down in its entirety. Since you can always write down an integer in finite time, all integers are, by definition, computable.

Bit-Brain?

The question, then, is: "Can brains represent uncomputable numbers?" Well, they can only do so if they either have:

  1. infinite memory, then they can just store uncomputable numbers raw
  2. infinitely fast compute, which allows them to perform at least aleph_0 computations in finite time

Needless to say, the known storage and compute bounds of human brains are nowhere near these "transfinite compute" bounds. You could say: "Well, maybe brains are capable of this, but we just don't have the tools to notice!" But it's much worse than that. We can't even check whether a brain contains an uncomputable number, because it would take an infinite amount of time for us to verify even one of them! And that's how we know that brains don't contain any uncomputable numbers: the body which hosts them is physically incapable of doing anything which would exploit their properties.

SuperBrain

Now, if brains as we know them are just the 3/4D projection of a 5D brain that has access to infinite compute in some kind of holographic extended universe, then it is possible that brains really can perform "uncomputable functions", because "uncomputable" really just means "uncomputable for a basic Turing machine". If you introduce a black box which can do everything a Turing machine can, as well as solve the Halting Problem for that TM, then you create a higher-order Turing Machine which can solve a strictly greater set of problems (but which, unfortunately, requires infinitely more resources). Functions which are uncomputable for a TM_0 are computable for a TM_1, and Turing machines form an infinite hierarchy of computability when you introduce the solution to the Halting Problem as an axiomatic feature.

However, none of that matters. It doesn't matter, because nothing that human brains do today requires such a 5D holographic super-Turing capability. Brains in our universe are utterly indistinguishable from finite, TM_0 brains. So claiming that brains can perform uncomputable computations is as useful as claiming that brains are giant robots controlled by unicorn homunculi under the influence of pixie dust: the claim cannot be disproved, so it thus cannot be falsified, so it's worthless.

Mathematically speaking, any machine operating in the observable portion of our universe can be adequately modeled by a Turing machine. You'll need infinitely precise observations to prove otherwise. Given the Planck scale, you're in for a rough ride. Good luck.

1
  • I like your answer, though I disagree with a 5thD as source of 'infinite computation'. Consider an ant bound to a 2D sheet of paper, this is like a TM vulnerable to the Halting Problem. Humans can 'jump' across the sheet. Universal Constructor theory can be pictured as an 'additional dimension' of counterfactuals, that allows a kind of feeling around for computational vortexes, & a jumping from point to point in the 'computational surface' - that embodies/requires/implies it be in a higher dimensional space. Humans do solve the Halting Problem, & Turing Incompleteness. That's a given.
    – CriglCragl
    May 2 at 14:26
1

I think this is just the case of software being more practical than hardware since the 1930s. They are essentially equivalent as Turing claimed. But not completely, since to have consciousness is to physically interact with the world. At the end of the day there does need to be a physical mechanism generating consciousness, but maybe we can get that mechanism as small, simple, and cheap as possible-with the right software augmentation.

The finite state machine clearly makes sense to a physicalist and is broad enough to include brains and consciousness.

But what generates the machines so they do as we want? Algorithms. And bar none the most efficient way to design and implement one is a program/software.

The idea is then optimize the software to save on the hardware. Turing acknowledged this by saying a city sized computer could mimic a human during his time, but improvements will come from software to make it more practical.

So between all hardware and software formal systems, we want those which are easiest to design, adapt, understand, and implement into hardware.

I believe this all culminates in a focus on software and thus Turing’s conception of formal systems.

Software alone won’t get us there, but it is the most efficient use of time and money. Significant work on the hardware side (biochemistry, electrical engineering, mechanical engineering, etc) will need to provide the physical mechanism for generating consciousness with the aid of software. But that is much less understood. What is perfectly understood is formal systems which don’t rely on complex hardware. We know in-principle we can implement the software, we just want to wait to do so until we have the most promising software. And then build the hardware.

So I don’t see it as a mistake unless the physicalist claims there doesn’t need to be any focus on the hardware at some point.

Your #3 bullet is worrying to me as machines do do those things in physicalism as we are machines.

Your #4 is worrying to me because quantum computation can do this, continuous change instead of 0 or 1. And yet the TM can simulate the qTM given long enough time. Remember computation is a tool here, we could specify the brain-machine by writing on paper or quantum computers. What matters is the physical mechanism, which is designed and augmented by computation. Computation alone is not mind unless you are misunderstanding formal systems.

The summary is: use the most efficient tool toward generating the right physical mechanism for consciousness. It’s possible to reduce the difficulty in engineering the physical mechanism greatly with a focus on software.

The only figure I know who says consciousness is computation is Kurzweil. And I’m not even sure he’s a physicalist. The physically unrealized formalism (TMs) is the most powerful tool (but not the whole story) because we don’t have to specify the hardware while writing it, while knowing it is in-principle able to be implemented (as long as it doesn’t get so big it creates a black hole)

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