The Church-Turing thesis is that every function that would naturally be regarded as computable can be computed by a Turing machine. This thesis cannot be proven rigorously, because it relates an informal notion (naturally be regarded as computable) to a formal notion (Turing machine). However, there is very strong evidence for the Church-Turing thesis, since every proposed formal treatment of computation (Church’s Lambda calculus, Post’s machine, Markov algorithms, the Game of Life, and even quantum computers) has been shown to be equivalent to Turing machines.
There seems to be increasing support for an expanded form of the Church-Turing thesis, which might be stated as “everything that is real can be computed by a Turing machine”. What is reality, in this context? That question is what I want to explore here.
Turing developed the idea of Turing machines while working on Hilbert’s Entscheidungsproblem (decision problem). Informally, Hilbert wondered whether it was possible to automate mathematics. Could there be an automatic procedure that could take any mathematical theorem as input and produce as output a proof that the theorem is true or that it is false? Turning showed that there could be no such procedure. More precisely, he showed that there are mathematical questions that Turing machines cannot answer. A Turing machine is essentially a very abstract model of a mathematician. It consists of an abstract person with a pencil, an eraser, and an infinite supply of sheets of paper. The core assumption is that the behaviour of the abstract person is constrained by a finite set of purely deterministic rules. It seems to me that this assumption is very closely related to the notion of “reality”.
Several people have argued that the physical universe may be a Turing machine (Wolfram, Poundstone, Deutsch). Others have argued that the human mind may be a Turing machine (Turing, Dennet, Putnam). Bostrom argues that we may all be simulations in a Turing machine. Why does everything seem to converge on Turing machines?
I am very sympathetic to the expanded Church-Turing thesis, but I suspect that the thesis may be a consequence of our assumptions, rather than an empirical observation. That is, scientific method has certain assumptions built into it. Observations must be repeatable and scientific theories must be computable and communicable to other scientists. Perhaps the core assumption of Turing machines, that the behaviour of an abstract person is constrained by a finite set of purely deterministic rules, necessarily follows from the assumptions of scientific method. Therefore, as soon as we agree to follow scientific method, we necessarily agree to the expanded Church-Turing thesis. But the chain of reasoning that leads from one to the other is complicated, so we are only now starting to see it.
What are the practical implications of the expanded Church-Turing thesis? I suspect there are none. So what if we are all simulations in a Turing machine? Does this hypothesis lead to any testable predictions? As a researcher in Artificial Intelligence, I believe that minds can run on Turing machines, but this doesn’t really help me with my daily research. It is about as useful to me as string theory is to a biologist. However, it’s still fun to think about these things.
Filed under: Computer Science, Philosophy of Mind, Philosophy of Science | Tagged: Church-Turing, computation, reality
Is there any evidence that the brain is a Turing machine? Is there any evidence that the brain can run on a Turing machine? Penrose (see, I believe, “Shadows of the Mind” ) argued against it. I must have read this book 10 years ago, so my recollection is weak, but I think that he made a case that “intelligence” would exceed a Turing machine. He might have used Gödel’s theorem in the process. Surely, he is not the only one to have argued about the fact that the Mind can run on a Turing machine. Why did you choose not to cite any opponent to this strong AI hypothesis?
Now, if you do accept this strong AI hypothesis, why aren’t you drawing up the consequences? If I work with nuclear fission and I think it can lead to a devastating weapon, I’m compelled to come out in the open and teach others about the downsides of my research. By assuming that you can turn PCs into intelligent being, I claim that you are working on something that has a terrible potential. Doesn’t the strong AI hypothesis throw Free Will out the window? And if you discard Free Will, don’t you have to change our entire legal system? And doesn’t it call for the immediate draft of a AI ethic? Wouldn’t playing close to intelligence and consciousness require ethical considerations? Suppose you make your PC intelligent tomorrow. Can you turn it off? What if your PC manages to take over the world in minutes through the Internet and turns all of us into slaves? Shouldn’t AI researchers be confined to bunkers? I’m only half kidding: can you measure how close you are to succeeding? If you can’t measure how close you are, how do you know someone won’t succeed tomorrow? Isn’t this terribly dangerous research?
To me, it is quite clear that saying that intelligence and consciousness fits in a Turing machine is an hypothesis, nothing more. And the reason why I’m not worried about ethical considerations is that I treat it as any other “possibility” out there (like the existence of God). Unless you can make a case to convince me? And the only way to verify this hypothesis is to actually come up with an intelligence Turing machine… naturally, even defining precisely the problem is hard… but I honestly think that if you did succeed to create an intelligent PC, I could tell (maybe this is presumptuous).
Well, I’m ready to take as a viable hypothesis that a silicon-based (non-Quantum) computer given lots of bandwidth (maybe terabytes per seconds) and lots of memory (several terabytes) and enough processors could become “intelligent”. I call this the “Google hypothesis” and it has some appeal. But empirical evidence, and my rather good knowledge of Machine Learning, tells me that we are not getting closer to intelligence. We are still pretty much fitting curves on some data. Some people say that Google is a “smart search engine”, but all I see is an amazing (ok: unbelievable) number crunching architecture.
You say that we are blinded by the scientific method and can only think in terms of Church-Turing, and then you go on to write “I believe that minds can run on Turing machines”. Where does this belief comes from? Wouldn’t it be a side-effect of this blindness deriving from the scientific method you speak of?
If you are not blinded, where do you draw your belief from?
The hypothesis that the universe is a UTM can have testable predictions.
An example is given by Jürgen Schmidhuber http://www.idsia.ch/%7Ejuergen/ of Dalle Molle Institute for Artificial Intelligence http://www.idsia.ch/ in “The New AI: General & Sound & Relevant for Physics” http://www.idsia.ch/%7Ejuergen/newai/newai.htm“:
“Systematically create and execute all programs for a universal computer, such as a Turing machine or a CA; the first program is run for one instruction every second step on average, the next for one instruction every second of the remaining steps on average, and so on.” This actually computes all parallel universes — not just ours. Among the consequences of this hypothesis is: “Large scale quantum computation will not work well, essentially because it would require too many exponentially growing computational resources in interfering ‘parallel universes’”
http://www.idsia.ch/%7Ejuergen/newai/node6.html#universe
“Large scale quantum computation will not work well, essentially because it would require too many exponentially growing computational resources in interfering ‘parallel universes’”
If there is an exponential growth in demand for computational resources, the universe can run exponentially slower, and we who are inside the universe would never know it. Only an outside observer (if there could be such a thing) would know.
We might exploit the fact that a Turing machine can only produce pseudorandom numbers, by looking for nonrandom behaviour in supposedly random events, such as atomic decay. But the many-worlds interpretation of quantum mechanics suggests that randomness is an illusion, in that all possible outcomes of a random event actually occur, each occurring in a different world. If atomic decay appears truly random, we might still be a Turning machine computation, if the computation includes the entire multiverse.
We might look for roundoff errors, since Turing machines can only approximate real numbers. But the fundamental laws of physics (whatever they might be) could be based on rational numbers or integers.
There is an even stronger version of the Church-Turing thesis – that the achievable computation machines are equivalent not only in what they can compute, but that they can simulate each other with a polynomial time speed difference. As far as I remember it is possible that quantum computing will be expotentially faster than a TM. The Penrose argument against AI was basically about that – i.e. it was based on the prediction that the quantum computing in our brains makes them expotentially faster than a TM like machine – I think in his later works he admitted that this does not mean than there cannot be any quantum computing based AI.
As far as I remember it is possible that quantum computing will be expotentially faster than a TM.
http://arstechnica.com/journals/science.ars/2007/2/12/7012
“While it is not proven that quantum computers cannot solve NP-complete problems in polynomial time, it is generally accepted that they cannot.”
http://tinyurl.com/3yublg
“There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.”
Update:
http://en.wikipedia.org/wiki/Church-Turing-Deutsch_principle
http://www.qinfo.org/people/nielsen/blog/archive/000071.html
http://www.scottaaronson.com/blog/