Did you ever see one of those auto-generated random “academic papers” like this one? When I first saw the following title, my first thought was that it is a randomly-generated “paper”:
Implications of the Turing completeness of reaction-diffusion models, informed by GPGPU simulations on an XBox 360: Cardiac arrhythmias, re-entry and the Halting problem [PDF]
Turing completeness, cardiac arrhythmias, XBox 360… those things don’t seem to have much in common. But, I had my interest piqued. I looked up the paper and read through it. And, it turns out that not only is the paper serious, what it has to say is also quite interesting.
Heart and logic circuits
I had to take author’s word on the medical aspects of the article, since I know nothing about cardiology. Apparently, understanding of electrical signals between cells in a human heart is important for research into heart arrhythmias. Makes sense.
The important insight of the article is that a logic NOR gate can be simulated using electrical signals between heart cells. Constructing a NOR gate is a powerful result, because similarly to NAND, NOR is a universal logic gate. That means that all other logic gates like AND, OR and NOT can be built out of NORs:
NOT(A) = NOR(A, A)
OR(A, B) = NOR(NOR(A, B), NOR(A, B))
AND(A, B) = NOR(NOR(A, A), NOR(B, B))
So, since you can simulate a NOR gate using cardiac cells, you can simulate an arbitrary logic circuit in heart tissue.
Heart and Turing machines
But, there has to be more to the story. The paper title mentioned Turing machines, and logic circuits are not Turing-complete. Halting problem doesn’t even make sense when applied to boolean expressions!
The missing part is the passage of time. See, a logic circuit is not Turing-complete. But, if you take a logic circuit with multiple inputs, the same number of outputs as inputs, and repeatedly apply the circuit over the results of the previous iteration, you get a Turing-complete system. This type of a system can be modeled with behavior of a heart tissue over a period of time.
The most intuitive explanation that I can think of is via Game of Life. In the Game of Life, each cell dies, becomes alive or stays alive depending on how many live neighbors it had in the previous generation. Here is one example of a Game of Life board in action:
Now, the important observation is that the Game of Life rules can be encoded using a logic circuit. For example, if the eight neighbors of a particular cell are represented as A, B … H, then the rule that the cell becomes alive if it has exactly three neighbors can be encoded as ((A and B and C and not(D) and … and not(H)) or (A and B and not(C) and D and not(E) … and not(H)) or …). This expression will be combined with an OR together with the situations under which the cell remains alive, rather than becoming alive. This will be a pretty ugly logic circuit, but it should be clear that it can be constructed.
Since Game of Life is known to be Turing-complete, then an “iterated logic circuit” is also Turing-complete, and the behavior of cardiac tissue is … Turing-complete.
Why is this useful?
Proving that a particular behavior of cardiac tissue is Turing-complete is a useful result because it shows that the cardiac tissue is in a certain sense “unpredictable”.
For example, since Game of Life is Turing-complete, the Halting problem applies. So, it is a proven fact that there is no general algorithm that can look at a particular Game of Life board and decide whether the movement will eventually stop or continue forever.
Similarly, there is no algorithm that can decide any of these properties for all Game-of-Life boards:
- Whether the board will ever reach a particular configuration
- Whether the number of live cells will ever exceed X
- Whether the game will ever enter a cycle
- etc.
Since the studied behavior of cardiac tissue is also Turing-complete, there is no general algorithm that can look at the state of cardiac tissue and decide whether the activity will ever stop, enter a regular pattern, achieve a particular configuration, etc. That is certainly a worthwhile result!
What about the XBox?
Constructing a NOR gate out of cardiac cells is computationally intensive, and the researcher used a GPU in an XBox 360 for that task.
However, the paper doesn’t conclusively show that using an XBox was a real benefit. The paper says that a C++ implementation that was originally “designed more for ease of expansion […] than for speed” ran slower on an XBox 360 CPU than an “unoptimized” shader-based implementation on an XBox 360 GPU. Comparing implementations not designed for speed is unconvincing. If the goal was to speed up the computation, why not first try to optimize the original code instead of porting it to shaders, which is undoubtedly a much more difficult task?
Also, the article doesn’t say how did XBox 360 CPU compare against an ordinary x86 machine, or against say a CUDA-based implementation on a common NVidia card. So, the paper doesn’t come close to showing that the researchers gained much by coding against the XBox 360 GPU, rather than following the current state-of-the-art approaches.
But, it is still a cool paper, and adding XBox 360 into the picture certainly attracted attention. The paper was reported in press, with titles such as these:
- How Xbox Can Help Fight Heart Disease [time.com].
- Parallel processor computing of XBox chip could save thousands [techshout.com].
And, if it weren’t for the sensational articles, I wouldn’t have found out about the paper at all, so I guess I shouldn’t complain.
Heads up.. 3rd paragraph: “..interest peeked…” should be “…interest piqued…”
I think you are wrong about this:
Similarly, there is no algorithm that can decide any of these properties for all Game-of-Life boards:
* Whether the board will ever reach a particular configuration
* Whether the number of live cells will ever exceed X
* Whether the game will ever enter a cycle
As far as I know, all games of life eventually reach one of 3 states:
Static unchanging
infinite repeat of the same pattern
infinite creation of new pieces in a fixed pattern
Given that, you most certainly can tell if a game of life will “ever reach a particular configuration”, and all the other ones you listed.
Basically: you run the program, until it repeats a previous state, or you detect that all pieces moving away from it will not collide, and the rest of the pieces have repeated a state.
Ariel, running the program to determine if it reaches a particular configuration is not an algorithm to determine if the game reaches that state.
The Game of Life is determinate, yes, but unpredictable. You are confusing chaos with randomness.
The word is “piqued”, not “peeked”.
I thought the game of life had a finite number of states.
Ah, nevermind, the grid is infinite.
Your NOR expression for AND is needlessly complicated. AND is just NOR(NOT A, NOT B) so NOR(NOR(A, A), NOR(B, B)).
@Ariel,
Suppose you want to design a program to look for loops in a game of life. If the number of iterations between loops is 0, the test is easy. Just compare two boards.
Well, what if you have 10 loops between states? OK, save 10 boards and compare them all.
What if you have n loops between states? You now need infinite memory to accomodate the list of past states, and infinite processing power to compare all of the boards in a timely manner.
Congratulations. You have discovered the halting problem. Crudely stated, it is impossible to write a program to determine if another program will terminate. (Where “program” is a string accepted by a universal turing machine)
Cheers.
Your piquing use of “peeked” piqued my attention — you might want to have a peek at it.
Funny that 3 out of 9 comments are on the topic of “piqued” vs. “peeked”. I fixed the mistake, but hopefully that doesn’t make the post too boring.
@Andrew: Duh! You are right… thanks.
Wow, way cool dude I like it
RT
http://www.privacy-web.pro.tc
I have a question. You state:
“The missing part is the passage of time. See, a logic circuit is not Turing-complete. But, if you take a logic circuit with multiple inputs, the same number of outputs as inputs, and repeatedly apply the circuit over the results of the previous iteration, you get a Turing-complete system. This type of a system can be modeled with behavior of a heart tissue over a period of time.”
The paragraph implies that heart tissue can model a Turing-complete system. It does not imply that the heart actually does this. But the rest of your post sort-of suggests that’s what you meant. Did you mean that this type of system can be used to model the heart?
… I should probably read the actual article, huh? Thanks for pointing this out, though, it’s neat.
[…] Sifeldeen sent me a link which raises the question, Is the heart a Turing machine? I think what the author shows is that the […]
@Confused: Very good question!
“Heart tissue can model a Turing-complete system” means that you can do this:
1. Encode *any* program by initializing the state of the heart tissue (e.g., the program is to compute Pi to 1,000 decimal places)
2. Wait until the activity in the heart tissue stops
3. “Read” Pi from the heart tissue
So, heart tissue *does* behave like a Turing-complete system. But, you have to “look” at it the right way (i.e., steps 1. and 3. above).
This is not necessarily a practical way to compute Pi, but the fact that you *can* do this implies some interesting things about this particular mathematical model of heart tissue.
Two questions:
1. Is heart tissue actually arranged in such a way that it models a turing machine, or is it just possible to arange in such a way.
2. Does anyone have a heart with an infinite number of cells?
A finite heart is of course not truly turing complete, as it can at best emulate a turing machine with a finite state space (ie, finite tape), which is of course not a turing machine. (In much the same way as a finite game of life game is not a turing machine.)
I think Confused and Ivan are both onto something. Just because it is possible to construct a universal Turing machine out of heart tissue doesn’t mean that anyone’s heart tissue actually has this configuration. Just because it’s theoretically impossible to predict the limiting behaviour of hearts in general doesn’t mean that it’s impossible to predict the limiting behaviour of all the existing human hearts.
Also, the heart is finite in size, and you are thinking of it as a collection of digital logic gates, which means that the amount of information that it can store is bounded by a constant. This makes it a deterministic finite automaton, and those are not Turing-complete by a long shot.
Ivan & Abednego:
1. The tissue is uniform according to this model. It is only the signals – chemical concentrations – that change (at least as far as I understand the model). So, to construct a particular Turing machine, you only have to change the initial concentrations, but you don’t have to rearrange any tissue.
2. When the number of states is on the order of 2^large_number, you can treat it as infinite for most purposes. Nothing physical can really be Turing-complete, since the number of particles is finite (at least according to the physics known so far).
Does the heart function in a TC way? I say, no. It’s a pump and does not require the remembering of anything from “state” to “state” during operation. If it is shown that the heart cells can function as random access memory and the heart’s function might adjust accordingly, then you might have a case – but it really depends on how it responds.
The question one must ask is, does said machine remember and act on this information of the past? One part of our body, other than our brain, that “remembers” is our immune system. I would contend that our brain is not the only TC, or at least “memory sensitive,” mechanism in the body – but I am pretty sure the heart is not one any more than our kidneys are.
Cheers
I want a C to heart compiler!
Again, another brilliant article…
[…] but I imagine it could allow for interesting medical applications. You can read a blog about it here, and get the scientific paper […]
@Eric
Ariel is right,
Game-of-Life is in finite space.
In finite space everything is decidable
by another machine with more space.
[…] Human heart is a Turing machine, research on XBox 360 shows. Wait, what? […]
This leaves me with two questions: what is my heart calculating, and when will it halt?
Jeo: My guess is, it’s calculating the number of heartbeats that occur during your lifetime, and will halt when that calculation is done. This is only a guess though. ;p
Excellent news it is actually. My teacher has been looking for this information.
Brilliant article, thanks. Came looking for processor caches, got NOR heart tissue. Currently heart cells just say 100010001000… to each other but this could be useful for my cybernetic implants in 40 years.
Maybe he will write a follow-up article entitled:
“Trolling news outlets for fun and profit: how mentioning popular video-game consoles can boost your article visibility.”
Not all Turing-complete systems are Turing-machines! In fact, there are no Turing machines. The Universe might be analogous to one, but a Turing machine is a processor that operates on an infinite number of tape allocations.
Logic systems are said to be Turing-complete when they would be able to, given enough space for state keeping, compute anything a Turing machine would be able to compute.
Note also that while a true Turing machine could consume an infinite amount of tape, that amount is defined to be countable.
Reasoning about computation given uncountable space might cause cephalic explosions. On the bright side, it’s a fair excuse for using lisp