One scientific/philosophical point that all three of my favourite authors loved to delve into was Computational Theory and, in particular, something called “The Church-Turing Thesis” and it’s related thesis: The Turing Principle [1]
I remember, back when I was working on my computer science degree, studying about Turing machines and the Church-Turing Thesis in my Intro to Computational Theory class. Back then I thought it was a big waste of time. I just wanted to program computers and I could care less about this long dead Turing-guy (or this Church-guy) nor his stupid theoretical machines.
Now that I understand the philosophical ramifications of the Church-Turing Thesis, I wish I had paid attention in class! Because the Church-Turing Thesis, if true, has some profound philosophical ramifications and it might also tell us something about the deep — and special — nature of reality.
In a series of posts I will attempt to do a short summary of Computational Theory. This serves as the basis for many other topics to come, so it will be nice to have a series of posts I can easily reference back to. (I’ll also do a summary at the end if I get that far.) I’ll do my best to make it as easy as possible and as interesting as possible. But if this just isn’t your cup of tea, you may need to move on or just skim it for general ideas or wait for the quick summary. [2]
Finite Automata
All texts and classes on the Theory of Computation start out with something called “Finite Automata.” The basic idea behind them is pretty easy. You just imagine a simple ‘machine’ that is able to make choices and move between states. Here is an example of a very simple one that represents the “logic” of a coin-operated turnstile.
A Finite Automata for a coin-operated turnstile.
In plain English, this says that if you try to push through a turnstile that is locked, you can’t if you haven’t first put in a coin. If you have put in a coin but haven’t pushed through yet, it will accept no more coins. If you have put in a coin, then you can push through. It then locks again for the next person. It was probably easier to understand from the diagram than from the description.
Finite Automata are capable of performing far more complicated logic than this. But this should give you a basic feel for how a finite automata works.
One thing to note is that a finite automata, like the one above, is purely theoretical because it only exists as a bunch of bubbles and lines on a piece of paper. It’s not like there is some little “finite automata machine” inside the turnstile that makes these decisions. Or perhaps I should instead say that the turnstile itself is the finite automata machine.
If we really wanted to, we could probably build a machine in real life that would be a Finite Automata. So there is nothing stopping someone from building it as a real machine in real life and then installing it into the turnstile. That just isn’t the cheapest way to do it. Finite automata are easy to instantiate either electronically or mechanically. So any ‘program’ you make as a drawing of a finite automata can be turned into a real life “computation” that really works. The importance of the difference between a computational machine that can actually exist (like a Finite Automata) and one that is only hypothetical and violates the laws of physics becomes important in a moment.
There are actually two types of Finite Automata. There are Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA). As it turns out, it’s possible to prove that both of these types of machines can actually run all the same sorts of programs. That is to say, it’s possible to prove that DFAs and NFAs are equivalent in terms of what “programs” then can run. So why do we have both? Well, for one thing, an NFA allows for parallel processing (i.e. multiple computations at the same time), so it would – if it existed in real life – run a heck of a lot faster than an equivalently fast DFA. The problem with NFAs is, of course, that NFAs can’t exist in real life. [3] They are purely hypothetical.
More Powerful Machines
As a class in computational theory progresses, the students are introduced to increasingly complex ‘machines’ that are more powerful than Finite Automata — such as the Pushdown Automata (PDA). I’m not going to show these other types of machines, as the key point is only that there are certain types of “programs” that can be written for a PDA that can’t be written on a Deterministic Finite Automata (DFA). In other words PDAs are ‘more powerful’ than DFAs because they can express classes of “programs” that DFAs can’t.
So there is a relationship between DFAs and PDAs in terms of “computational power.” Namely it’s possible to prove that any program written on a DFA can also be written on a PDA, but that the reverse isn’t true.
The Proof is in the Proof
The proof that a PDA can run anything that a DFA can is done by coming up with a scheme by which the logic of an DFA can be mapped to a PDA. In fact this is easy to do because a PDA is really just an DFA with the addition of a sort of “memory”. So any program you can write for an DFA can, by default, also run on a PDA by just not utilizing the “memory feature.”
But what about the reverse? Can we prove that it’s impossible to take certain types of “programs” written for a PDA and translate them to an DFA? That is to say, is there a proof that a Pushdown Automata can’t be mapped to a Finite Automata? Or are we just assuming a Finite Automata is less powerful than a Pushdown Automata because we don’t currently know of a way to map a PDA back to an FDA? Maybe there is a way to map PDAs to FDAs and maybe no one has discovered how to do that yet? Isn’t that at least a possibility?
As it turns out, it is possible to prove that a PDA can run certain types of programs that an DFA cannot. The way you’d do it is you’d find a computation (i.e. a program) that you can prove an DFA can’t compute and then demonstrate that a PDA can compute it.
Computational Power of a Machine
This fact – that there are more powerful (PDA) and less powerful (DFA) logic machines – is interesting in and of itself. And, as well see, there are even more powerful machines than PDAs.
But it leads to some philosophical questions: is there such a thing as a “most powerful computing machine?” If there was such a “most powerful machine”, how would we know any specific proposed machine happens to be “the most powerful?” Or are there just different types of computing machines available and you have to pick the right one for the job?
Turing Machines
So what machine is more powerful than a PDA?
As history would have it, at about the same time two very different types of “machines” were proposed that were both provably more powerful than PDAs. One was Alan Turing’s Turing Machine. The other wasn’t so much a machine as a clever set of notations developed by Alonzo Church that served the same purpose as developing a machine. So we’ll count it as a computational machine. Of these two “machines” the Turing machine is conceptually easier to teach, so usually that’s the machine that is taught in a Computational Theory course.
Turing Machines are funny little theoretical machines that have a read/write head and a (hypothetical) paper tape that it can read from or write to. Based on what the Turing Machine reads it puts the Turing Machine into an action state that performs some sort of combination of tasks consisting of either moving the read/write head forward or backward, reading from a new position on the tape, or writing so a new position on the tape. Try to visualize what a Turing Machine looks like via this drawing:
Conceptual Drawing of a Turing Machine
Turing Machines and Modern Computers
One thing of interest is that a Turing Machine is, despite surface appearances, actually somewhat similar to a modern computer. In a modern computer the Central Processing Unit (CPU) is equivalent to the read/write head of a Turing Machine. The memory chips (RAM or ROM) is very similar to the cells of the long paper tape that the turning machine can read from or write to. So modern computers are (roughly) equivalent to a Turing Machine.
A modern computer does have one advantage over the Turing Machine. A modern computer does not have to move from one cell of its “memory” in sequential order like a Turing Machine does.
The fact that a Turing machine can only move one cell at a time seems like a significant limitation, doesn’t it? We just saw how some machines are logically ‘more powerful’ than others. A PDA can perform computational tasks that an FDA can’t. So perhaps there are machines that are more powerful than Turing machines that can perform tasks that Turing Machines can’t? And maybe modern computer – due to their ability to jump around memory rather than have to move from cell to cell sequentially – can run some programs that a Turing Machine can’t?
In fact modern computer actually have less expressive power than a Turing Machine by virtue of the fact that Turing Machines were conceived as having an infinitely long paper tape (i.e. infinite memory) where as a real life computer will always have finite memory. However, in general this makes very little difference in what types of computations one can perform since human beings are not generally all that interested in infinitely long computations that give out infinitely long results. That is why I say modern computers and Turing Machines are “roughly” equivalent. In fact, so long as you assume any arbitrary but finite size of memory, they are exactly equivalent in terms of what types of programs they can run.
The Church Turing Thesis: Turing Machine = Max Logical Power
But what about poor Alonzo Church? His poor little “machine” forgotten because Turing Machines are easier to teach. Is his machine maybe able to express some computations /programs that a Turing Machine can’t, or vice versa?
Wouldn’t it be a stellar coincidence if it just so happened that Alan Turing and Alonzo Church just so happened to create two entirely different types of theoretical computation machines and it just so happened that they were exactly identical in terms of what types of computations they could perform?
So imagine everyone’s surprise when Alan Turing was able to produce a proof that any program written for a Turing Machine could also be written for a Church machine and also a proof that any program written for a Church machine could also be written for a Turing machine.
In fact, there are a number of proposed types of theoretical computational machines. For example, theoreticians tried allowing a Turing Machine to have multiple tapes to read/write with. They even tried allowing a Turing Machine a 2-dimensional ‘sheet’ to read and write with. Theoreticians tried all sorts of improvements to Turing Machines (and Church machines). And so far it’s been possible to produce a proof for every single one of them that they are equivalent to a simple Turing Machine.
That does seem like a wild coincidence, doesn’t it? And it would be a wild coincidence unless there is an upper limited to what types of computation can be performed. If there is such an upper limit, then it would be no coincidence at all that the Turing Machine and Church Machine and all other computational machines proposed all just happen to have the same computational power, since in fact the reason why they are all equivalent is because we’ve reached the upper limit of computational power.
But can we prove that there is not some computational machine out there – one that we just haven’t discovered yet – that has the ability to perform computations that a Turing Machine can’t?
How, exactly, would we produce such a proof? The fact is that we cannot prove that there is nothing more powerful than a Turing Machine. So, who knows, maybe there is.
But the fact is that we can’t find any such machines. So after considerable effort trying to come up with, and failing, to find a way to improve on the power of Turing Machines, finally the Church-Turing Thesis was accepted even though it was not proven to be true. The Church-Turing Thesis essentially says something like this:
It’s not possible to come up with any sort of computational machine that can perform a logic program that a plain old Turing Machine can’t.
Or in other words:
Turing Machines and their equivalents are the most powerful possible types of computational machines and there are no more powerful ones out there that we just don’t know about.
After years and years of research on this Thesis, this Thesis still basically holds. We’ll see later that there has been somewhat of a modification to the Thesis with the introduction of theoretical quantum computers. But, basically, the Thesis still holds true today. No one has ever come up with a way to outperform Turing machines when it comes to logical expressiveness. Turing Machines are still the reigning champion.
So now you understand the Church-Turing Thesis. However, the Church-Turing Thesis is not really quite equivalent to the Turing Principle. So in a future post I’ll develop what the difference is and what it’s philosophical ramifications are.
Notes
[1] The Turing Principle. So named by Roger Penrose, who does not believe in it (at least not in current form). It was developed into the Turing-Deutsch principle by David Deutsch, who does believe in it, at least in his form of it.) (See article in Wikipedia for more details)
[2] the quick summary. Remember Bruce’s Rule of Summaries. The summary is never equivalent to the details.
[3] NFAs can’t exist in real life. At least under classical physics and classical computation. But it might be possible to create them, or something similar to them anyhow, under quantum physics and quantum computation. But so far we can’t even do so with theoretical quantum computations except in very rare types of computations. But as research continues into theoretical quantum computing, who knows for sure what the future holds.
New Post: An Introduction to the Theory of Computation: The Church-Turing Thesis: One scientific/… http://t.co/fv6jj9cyhc #LDS #Mormon
TheMillennialStar: An Introduction to the Theory of Computation: The Church-Turing Thesis http://t.co/wdO2B8vWXS #lds #mormon
An Introduction to the Theory of Computation: The Church-Turing Thesis http://t.co/fOApzI9vXF
So, what kind of machine would a human brain be?
Hi Bruce,
You assert that this matters, and I believe you. But before I devote time to your series recapitulating computational theory, could you assert why it matters?
Meg, first of all, I accept it as a given that few people are interested in the subjects I’m interested in, so I will not be offended if you don’t bother to follow.
That being said, I’m going to attempt to prove that the signficance of it is that our science is fundamentally built on the assumption of computationalism rather than (as many think) materialism. I’m not sure how much that changes science other than it seems to me to ground it more in the non-material world than might first be obvious. But this is more about exploring ideas and seeing what we can come up with rather than me making any ultimate point or drawing any ultimate conclusions.
Silver Rain,
Bear in mind that I like to explore ideas. I do not claim to know how to make all of them ‘match up.’ So in fact ‘I have no idea’ would be the most honest answer to your question.
However, I can at least think to ask a lot of interesting questions around your question, even if I can’t possibly ever know for sure (as per my epistemology post a few weeks ago) what the correct answers are.
For example, you specifically ask:
“what kind of machine would a human brain be?”
So here would be the questions I’d ask to explore your question:
Is a ‘brain’ the same as a ‘mind’ or are they not the same? How are they related? If they are not the same, are minds something our computationally based science can even examine in the first place? If it can’t, then can it be comprehended at all?
(Religious question) What role does a spirit play in forming a mind and how does it relate to a brain? If it is physically connected to the brain, doesn’t that imply it’s physical too? (And of course the D&C says it is… but gives us so little to go on.) Or is it more like an ‘external hard drive’ to the brain?
Are brains / minds Turing machines? Or are they some sort of Super Turing Machine that has yet to be discovered? Might this ‘Super Turing Machine’ include something like what Mormons call “intelligences?” Or are “intelligences” more like a specific ‘form’ of a person that then gets instantiated into a brain (or spirit or mind…)?
And is there such a thing as an “Infinite Computations?” Currently we know of nothing so specific, but Quantum Computing at least hints at the possiblity. (Though far more vaguely than many try to make it out.)
The reason this last question becomes significant is because it’s really hard to see how there could be Somthing-Like-God out there without the existence of ‘infinite computation’ which implies a lot of very interesting things that aren’t immediately obvious. Infinite computations in theory blow away limits that are hard and fast with Turing machines.
I do not expect that an exploration of science (and comptuation as its foundation) will currently, under our current science, match up to our religious beliefs. So I don’t even try. I just ask interesting questions and encourage discussion and speculations. And most of the time, no one cares because only people like me find this interesting, which is to say, very few people indeed.
But I’m going to do my best to make it accessible to whoever wants to try to discuss it.
Oh, I didn’t expect you to have an answer. I posited the question because it was something that occurred to me as I read your post that has interesting philosophical ramifications. And because I thought you might have some idea whether or not that question has been broached by those who know better than I how to answer it.
Setting aside the religious aspect for now, it seems that the human brain might blow the Church-Turing theory out of the water. It indicates that there is very likely a more powerful computational machine than a Turing out there: a biological one.
On the religious front, we could see our brains as such machines with infinite potential and the ability to self-modify. Machines that somehow have the ability to interface with spiritual matter: to bridge the gap between spirit and physicality. Machines that are capable of being manipulated by another force capable of reason and deduction, which would indicate that there is, in fact, a machine even greater than it is.
But if, Mormon-religiously speaking, that is the case, than the difference between our machine of the mind/spirit and that of God’s is that his has reached the fullest potential of the most powerful machine, and so His glory is creating other machines with the potential to self-modify until they reach that potential as well.
At any rate, it is an interesting way to frame Joseph Smith’s theology in terms unavailable to him at the time.
Scientist Roger Penrose’s books, “The Emperor’s New Mind” and… another one I can’t recall at the moment… are written to make the very case you just did. That the brain is NOT a Turing machine. He goes even further than merely claiming it to be a Quantum Computer (which actually does exceed a Turing Machine in a limited way) but instead believes it’s “doing something” unlike anything we currently know at some quantum level based on some future Quantum Theory yet to be discovered.
Unfortunately, as much as I wanted to believe him and agree with him, I didn’t personally find his arguments very convincing and was disappointed. But a lot of people like his arguments, though.
I’m a few chapters into Penrose’s “The Emporer’s New Mind” and it seems like Penrose’s basic argument so far is that as there are logical proofs that we know cannot be calculated algorithmically in the classical sense, yet we have discovered the content of some of these proofs, therefore we must be utilising some other (and I assume higher) form of computation to do so.
In any case, even though Penrose simply doesn’t write well to the layman, I’m finding Penrose’s thoughts much more interesting and useful than Deutsch’s (I read The Fabric of Reality a few years back, and was *not* particularly impressed).
Fraggle, you properly summarize Penrose’s main argument.
Actually, I read Fabric of Reality too and loved it, but really didn’t want to agree with a lot of it (i.e. Many Worlds Quantum Physics). In that book, Deutsch specifically mentions Penrose’s views that are at odds with his own and summarizes them. That is how I discovered Penrose and then read his books.
I’m torn to be honest. Having now read both, my heart is all Penrose and my brain is all Deutsch. Deutsch absolutely is the more rationally sound of the two. It’s not even close.
The one thing I really like about Deutsch is that he is so dang hopeful. He is really, if you will, coming up with a sort of Theology of Nature that goes so far beyond the incredibly lame stuff that most scientists try to cite for their reasons for finding important morality in nature.
But Deutsch has one significant issue that unfortunately undermines his thesis almost all together. It is all based on Eternal Progress. But the 2nd law of thermodynamics is a pretty hard fast rule against that. In his first book he had a very clever way of getting around the problem via the Omega Point. He was forced to abandon it by his second book and does not have an alternative theory yet. (He mentions in passing an idea that is, upon inspection, not that good an idea and I’m amazed he mentioned it at all.)
The simple truth is that Deutsch’s theories *require* that the universe be so special that we can have Eternal Progress. But he can’t seem to come up with a way to actually show physics allows for it under our current understanding. So his theories are really more of a faith-based religion at this point, unfortunately. But then so are Penrose’s since he basically requires that we throw all of science and mathematics out and start with something else other than those, but has no idea whatsoever that would look like.
Bruce N, you are awesome, but there is not enough awesomeness in the world to tempt me to read this post. But I love you anyway.
Geoff,
Ah man! I finally produced a rock solid argument that proved once and for all that Libertarianism was false and I can’t even get you to read the post? (j/k)
Of course my predictable response is even if we can model the mind or all of science in terms of computationalism, I need no compelling reason for why we ought to – especially to the exclusion of other time honored ways of modeling such things.
Actually, Jeff, tell me about non-mathematical models. I’m not sure I have believed they exist. I’ve wracked my brain and it seems that what I’ve normally thought of as a non-mathematical model — say natural selection for evolution — in fact is really a mathematical model. So I’ve been wondering about other types of non-mathematical models.
Well, I was mostly thinking of good old fashioned folk psychology, which is the most time honored model of human behavior that there ever was.
Oh, okay, I’m with you.
I guess it depends on what you mean by “computational.” Probably most people would consider that equivalent to mathematical and plenty of folk psychology has no mathematical basis at this time comparable to say, physics. And probably never will.
I suppose more modern psychology is pretty rooted in the branch of mathematics known as statistics, however. And even folk psychology with no stats is still “computational” in the broad sense that you can encode the model of, say, believed causes and effects, into a computational model that is very specific. (Not sure why you would other than to ,say, make a simulation to teach students.)
When I think of something truly being non-computational I had in mind something that was utterly impossible to encode into logical statements, or math, or any sort of computation. I am not sure such a thing exists, but I’m not sure such a thing doesn’t exist. If I had one candidate, I’d say “how qualia works.” But I can think of no other candidate at all. And I’m not entirely sure on that one precisely because it is so completely not understood.
The idea of something that is truly non-computational is at once refreshing and scary. It proves there is more than the world of science can detect which is refreshing, but places it utterly outside the bounds of our comprehension also, which is kind of scary. So I always have mixed feelings no matter which way the wind ends up blowing on this.
I guess my comment was more aimed at undermining the idea that folk psychology needs or ever could have a mathematical basis. I see no reason for why math or computation should be the base for FP rather than the other way around since the latter came first and would certainly be the structure around which the former was be built.
My position is that there is nothing about computation or mathematics that is more fundamental or basic that FP in any sense whatsoever. FP is already a perfectly acceptable model of human behavior and always was, even before mankind knew anything at all about math or computation. I’m nots aging that we shouldn’t seek to improve whatever models we have (such as FP), only that we have no reason to think that unless we can garnish these models with math and computation then they aren’t good enough.
I think math is like science. It’s descriptive, not definitional. Isn’t the point not that reality fits into math, but math adapts itself to describe reality?
So the question of something being non-computational would be more one of a limit to our understanding of math. Just like even miracles and magic can be explained with science. Any lack of ability to explain through science is a lack in the science, not a lack in the capacity to explain.
It’s like trying to find a drawing that doesn’t use light and dark. Light and dark are just a tool. Oh…I don’t know if I’m making any sense.
Thanks for the further explanation, Jeff G. Where do you live? We so need to sit down for a couple of hours and have a few beers with undergrowth and chat and you can explain all your ideas to me better. 🙂
SR, no, actually make make good points all around. Yes, mathematics is descriptive when used in science. From what I understand, most mathematicians do math that has no connection to reality at all, however. It’s often done for its own sake. And sometimes that ‘useless math’ is later found to match reality in some way after the fact. So there is some sort of interesting relationship between math and science and reality, though maybe it’s not so obvious what it is. But once we do use math for science, it is entirely descriptive. Reality does something, we model it out using math.
“So the question of something being non-computational would be more one of a limit to our understanding of math.”
This is the question I find the most interesting. Go back to my qualia example (email me if you want me to explain further about qualia. It’s probably easiest explained as ‘what we experience’ including sensations, pain, etc.) It’s really hard right now to imagine that math could ever define qualia at all. Sure it could explain the firing of synapses or even damage to cells. But the sensations themselves… what’s the mathematical formula for pain? So is there some sort of “God math” that we don’t know yet that is used to define pain? Maybe.
@BN: I think some future revolution in computing will be a computer that departs from the Turing Machine model. I think it will be more of a “neural net” that bears some resemblance to the human brain.
I have occasionally read stuff about research into “neural net” computers, but if I remember correctly, the machines that have been so built were merely traditional (Turing-style) computers that attempted to _emulate_ a neural net. Therefore the programmers still had to (attempt to) break down the funcitons and abilities of a neural net into Turing-machine style instructions.
Is one of your articles going to be on a “non-Turing” type of computer?
It may be that each “neuron”, or unit that is emulating a neuron, may be reducible to a Turing-machine. And brain-pathways might be emulated by virtual pathways in a machine. But the functionality of a mammalian brain has never been fully duplicated by any set of Turing-machine programs (again, if I remember correctly.) Some things like “fuzzy logic” and very rudimentary learning have been emulated in Turing-machine style computers, but have essentially been emulations wherein the machine just remembers which of a series of pre-programmed options gives the desired result.
The recent development of putting hundreds of GPUs (graphics processing units, which in effect are also CPUs), on a chip, and thousands of GPUs on a board, leads me to believe that millions and perhaps billions of artificial neurons will eventually be networked together. It is then, when we can have billions of “units” as intimately connected as neurons in a brain, with each unit truely emulating a neuron, that it can be ‘turned loose’ to see if it will respond to environmental inputs.
However, at that point we may discover that intelligence actually lies in the _spirit_, that is the spirit body, or “soul” (tradtional definition, not LDS definition of soul). And that the physical organic brain is merely a vehicle for the core “thinking part” of us, and is not really an originator of thoughts itself.
And I have a suspicion that the ‘thinking part’ of us might be the _intelligence_ that was clothed upon with a spirit body at spiritual birth, ie., two levels removed from the physical body.
I’m out in beautiful San Diego, Bruce. It’s a little out of the way, but we take our root, ginger and (coming soon) butter beers pretty seriously.