According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing machine."

If we made a complete simulation of the human brain, that would imply that a Turing machine can do everything that a human brain can do. Wouldn't that prove the thesis?

  • 7
    $\begingroup$ How would you know that the simulation is "complete"? What does that even mean? $\endgroup$ – Raphael Mar 3 '16 at 21:38
  • 2
    $\begingroup$ I would state that most computer scientists view the Church-Turing thesis as a statement of what is physically possible, not (just) humanly possible. The wording with humans was an artifact of the time and context in which the statement was originally made. If we somehow decided that human behavior was implementable with a finite state machine, few computer scientists would consider that a "proof" of the Church-Turing thesis as they view it. $\endgroup$ – Derek Elkins left SE Mar 4 '16 at 19:27
  • $\begingroup$ my hunch (and this is strictly a hunch) is that a (digital) computer simulation of the human brain would require the efficient church-turing thesis to hold in all cases. the ECT holds that any analog computation that runs in O(t) time can be coded into a turing machine that runs in <= O(t**m) time. Dershowitz & Falkovich claim to have proven ECT but my understanding is that this has not been accepted as an actual proof of ECT. conversely, however, if someone eventually does manage to code a human brain into a turing machine then that would ncssly prove $\endgroup$ – Libby Chang Jan 5 '20 at 23:59

How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain?

Church–Turing isn't something that can be proven. It's essentially just the statement that Turing machines correspond to the intuitive notion of algorithm and that just isn't a statement of mathematics. The Turing machine is the definition of computability; Church–Turing is essentially the claim that we picked the right definition, in the sense that choosing any of the reasonable alternative definitions would give exactly the same notion of computability.


Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any model of computation that could feasibly be constructed is either equal in power to a Turing machine or weaker than a Turing machine.

If we were to try to formalize the Church-Turing thesis into a rigorous mathematical statement, we'd have to somehow give definitions to terms like "model of computation" or "feasibly constructed" that are, by design, very vague. After all, the whole point of the Church-Turing thesis is to claim that working with Turing machines really captures what computation is because any other model we could have picked would end up equal in power to Turing machines. We can precisely pin down particular rules for what a model of computation is and what it means for it to be feasible to construct, but by doing so we'd limit the resulting theorem to only talking about those classes of machines. If someone later on devises some new model of computation that is wildly different than everything we've ever thought about so far and ends up being more powerful than Turing machines, then the intuitive Church-Turing thesis would be false (Turing machines don't actually capture computation!) but the rigorous Church-Turing thesis would still be true (because this new model of computation wouldn't fit into the framework developed so far).

Here's another way to see this. There are formal proofs that Turing machines can simulate computers and that computers with unbounded memory can simulate TMs. We have similar results from certain types of cellular automata (Conway's Game of Life, for example), string rewriting systems (unrestricted grammars), crystal structures (see this amazing link), etc. All of these specific cases lend support to the Church-Turing thesis, but none of these statements, in isolation, is the Church-Turing thesis.

So suppose that we prove that a TM can simulate the human brain. This would be a huge result! But that by itself doesn't prove the Church-Turing thesis because, by nature, the Church-Turing thesis is unprovable. In a sense, the answer to the more general question of "can the Church-Turing thesis be proven?" is "no," so your question falls out as a special case.

That said, it is potentially possible to disprove the Church-Turing thesis by finding some model of computation that can solve a number of problems that TMs cannot but at the same time is still something that can be feasibly constructed in the universe. In that sense, the Church-Turing thesis is more of a falsifiable scientific hypothesis than a mathematical theorem.

  • $\begingroup$ Thanks for the really in-depth response! So, if physicists were ever to discover a "theory of everything", a complete set of physical rules that describe our universe, and we were to show that those rules could be simulated with a Turing machine, would that in a way prove the thesis? Because any process that could theoretically happen in our universe could be described by that. It wouldn't really be a mathematical certainty I guess, since physical laws are experimentally determined. And I get that this is total speculation. It's just fascinating. $\endgroup$ – Raiden Worley Mar 4 '16 at 13:46
  • $\begingroup$ Even that wouldn't do it. :-) Keep in mind that physics produces hypotheses about how the universe works and that no matter how good our theories are, there's always a chance that they're wrong. You could prove in that case that if the physical theories are correct then Church-Turing is true, but if we later discover that the physical laws aren't actually correct then that theory isn't useful. $\endgroup$ – templatetypedef Mar 4 '16 at 17:11

No, that wouldn't prove the thesis. Human beings are allowed to use machines. For example, an important consequence of the Church-Turing thesis is that computers can only compute Turing-computable functions. It is a statement about the physical universe and its capacity for computation.

  • $\begingroup$ I've heard the Church-Turing thesis as "Turing machines can do anything humans can do." That's the definition on Wikipedia. But I've also heard it as "Turing machines can compute anything computable." Those seem to be very different claims. A computer simulation of the human brain seems like it could prove the former, but not the latter. $\endgroup$ – Raiden Worley Mar 3 '16 at 17:07
  • $\begingroup$ @RaidenWorley Maybe you should look into reputable sources such as textbooks. Wikipedia is notoriously bad for TCS matters. $\endgroup$ – Raphael Mar 3 '16 at 21:38
  • $\begingroup$ It seems there are several different Church–Turing theses, so the answer depends on which one you choose. I used what is probably the most common definition in my circles. $\endgroup$ – Yuval Filmus Mar 3 '16 at 21:43
  • 2
    $\begingroup$ @Raphael I'd say that Wikipedia is usually very good for TCS. But where it goes wrong is for TCS concepts that feel like they're accessible to non-experts, and Church-Turing is definitely a case of that. (I guess we should head over to chat if you want to talk about that.) $\endgroup$ – David Richerby Mar 3 '16 at 21:57

Your Answer

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

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