The Library

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

Tools

Scarle, Simon. (2009) 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. Computational Biology and Chemistry, Vol.33 (No.4). pp. 253-260. ISSN 1476-9271

PDF
WRAP_Scarle_Turing.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (2289Kb)

Official URL: http://dx.doi.org/10.1016/j.compbiolchem.2009.05.0...

Abstract

In the arsenal of tools that a computational modeller can bring to bare on the study of cardiac arrhythmias, the most widely used and arguably the most successful is that of an excitable medium, a special case of a reaction-diffusion model. These are used to simulate the internal chemical reactions of a cardiac cell and the diffusion of their membrane voltages. Via a number of different methodologies it has previously been shown that reaction-diffusion systems are at multiple levels Turing complete. That is, they are capable of computation in the same manner as a universal Turing machine. However, all such computational systems are subject to a limitation known as the Halting problem. By constructing a universal logic gate using a cardiac cell model, we highlight how the Halting problem therefore could limit what it is possible to predict about cardiac tissue, arrhythmias and re-entry.

All simulations for this work were carried out on the GPU of an XBox 360 development console, and we also highlight the great gains in computational power and efficiency produced by such general purpose processing on a GPU for cardiac simulations.

Item Type:

Journal Article

Subjects:

R Medicine > RC Internal medicine

Divisions:

Faculty of Science > Engineering

Library of Congress Subject Headings (LCSH):

Arrhythmia -- Research, Xbox 360 (Video game console) -- Research, Turing (Computer program language), Heart -- Abnormalities -- Research

Journal or Publication Title:

Computational Biology and Chemistry

Publisher:

Elsevier Ltd

ISSN:

1476-9271

Official Date:

August 2009

Dates:

Date	Event
August 2009	Published

Volume:

Vol.33

Number:

No.4

Page Range:

pp. 253-260

Identification Number:

10.1016/j.compbiolchem.2009.05.001

Status:

Peer Reviewed

Access rights to Published version:

Open Access

References:

Adamatzky and Costello, 2002 A. Adamatzky and B.P.J.D.L. Costello, Collision-free path planning in the Belousov–Zhabotinsky medium assisted by a cellular automaton, Naturwissenschaften 89 (2002), pp. 474–478. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (11)

Adamatzky et al., 2004a A. Adamatzky, P. Arena, A. Basile, R. Carmona-Galan, B.D.L. Costello and L. Fortuna et al., Reaction-diffusion navigation robot control: from chemical to VLSI analogic processors, IEEE Trans. Circuits Syst. I 51 (2004), pp. 926–938. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (35)

Adamatzky et al., 2004b A. Adamatzky, B.D.L. Costello, C. Mehuish and N. Ratcliffe, Experimental implementation of mobile robot taxis with on board Belousov–Zhabotinsky chemical medium, Mater. Sci. Eng. C 24 (2004), pp. 541–548. Article | PDF (537 K) | View Record in Scopus | Cited By in Scopus (14)

Adamatzky, 2001 A. Adamatzky, Computing in Nonlinear Media and Automata Collectives, IoP, London (2001).

Adamatzky, 2004a A. Adamatzky, Collision-based computing in Belousov–Zhabotinsky medium, Chaos Soliton Fract. 21 (2004), pp. 1259–1264. Article | PDF (306 K) | View Record in Scopus | Cited By in Scopus (21)

Adamatzky, 2004b A. Adamatzky, Computing with waves in chemical media: massively parallel reaction-diffusion processors, IEICE Trans. 11 (2004), pp. 1748–1756. View Record in Scopus | Cited By in Scopus (8)

Adamatzky, 2005 A. Adamatzky, Programming reaction-diffusion processors, Lect. Notes Comput. Sci. 356 (2005), pp. 33–46. View Record in Scopus | Cited By in Scopus (2)

Agladze et al., 1996 T.Y.K. Agladze, R. Aliev and K. Yoshikawa, Chemical diode, J. Phys. Chem. 100 (1996), pp. 13895–13897.

Agladze et al., 1997 K. Agladze, N. Magome, R. Aliev, T. Yamaguchi and K. Yoshikawa, Finding the optimal path with the aid of chemical wave, Physica D 106 (1997), pp. 247–254. Abstract | PDF (826 K) | View Record in Scopus | Cited By in Scopus (39)

Bandini and Simone, 2004 S. Bandini and C. Simone, Integrating form of interaction in a distributed model, Fundam. Inform. 61 (2004), pp. 1–17. View Record in Scopus | Cited By in Scopus (2)

Bandini et al., 2005 S. Bandini, G. Mauri, G. Pavesi and C. Simone, Computing with a distributed reaction-diffusion model, Lec. Notes Comput. Sci. 3354 (2005), pp. 93–103. View Record in Scopus | Cited By in Scopus (1)

Clayton, 2001 R.H. Clayton, Computational models of normal and abnormal action potential propagation in cardiac tissue: linking experimental and clinical cardiology, Physiol. Meas. 22 (2001), pp. R15–R34. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (25)

Crackdown, 2007 Crackdown, 2007. Realtime Worlds, Microsoft Game Studios.

Davies, 1981 M.J. Davies, Pathological view of sudden cardiac death, Br. Heart J. 45 (1981), pp. 88–96. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (26)

Fenton and Karma, 1998 F. Fenton and A. Karma, Vortex dynamics in three-dimensional continuous myocardium with fibre rotation: filament instability and fibrillation, Chaos 8 (1998), pp. 20–47. OJPS full text | Full Text via CrossRef

FitzHugh, 2008 R. FitzHugh, Biophys. J. 1 (2008), p. 1961.

Freudenberg et al., 2004 B. Freudenberg, M. Masuch and T. Strothotte, Real-time Halftoning: fast and simple stylized shading, Game Programm. Gems 4 (2004), pp. 443–449.

Goldstein et al., 1981 S. Goldstein, J.R. Londis, R. Leighton, G. Ritter, C.M. Vasu and A. Lantis, Characteristics of the resuscitated out-of-hospital cardiac arrest victim with coronary heart disease, Circulation 64 (1981), pp. 977–984. View Record in Scopus | Cited By in Scopus (50)

Górecki et al., 2003 J. Górecki, K. Yoshikawa and Y. Igarashi, On chemical reactors that count, J. Phys. Chem. A 107 (2003), pp. 1664–1669. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (35)

Harris, 2005 M. Harris, Mapping computational concepts to GPUs, GPU Gems 2 (2005) (Chapter 31).

GPGPU, 2009 http://www.gpgpu.org.

Ichino et al., 2003 T. Ichino, Y. Igarashi, I.N. Motoike and K. Yoshikawa, Different operations on a single circuit: field computation on an excitable chemical system, J. Chem. Phys. 118 (2003), pp. 8185–8190. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (15)

Kuhnert et al., 1989 L. Kuhnert, K.L. Agladze and V.I. Krinsky, Image processing using light-sensitive chemical waves, Nature 337 (1989), pp. 244–247. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (154)

Kuhnert, 1986 L. Kuhnert, Photochemische Manipulation von chemischen Wellen, Naturwissenschaften 76 (1986), pp. 96–97. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (33)

Lake, 2001 A. Lake, Cartoon rendering using texture mapping and programmable vertex shaders, Game Programm. Gems 2 (2001), pp. 444–451.

Liu et al., 2008 W. Liu, B. Schmidt, G. Voss and W. Muller-Wittig, Accelerating molecular dynamics simulations using graphics processing units with CUDA, Comput. Phys. Commun. 179 (2008), pp. 634–641. Article | PDF (462 K) | View Record in Scopus | Cited By in Scopus (7)

Motoike and Yoshikawa, 1999 I. Motoike and K. Yoshikawa, Information operations with an excitable field, Phys. Rev. E 59 (1999), pp. 5354–5360. APS full text | Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (47)

Motoike and Yoshikawa, 2003 I.N. Motoike and K. Yoshikawa, Information operations with multiple pulses on an excitable field, Chaos Solitons Fract. 17 (2003), pp. 455–461. Article | PDF (238 K) | View Record in Scopus | Cited By in Scopus (17)

Motoike et al., 2001 I.N. Motoike, K. Yoshikawa, Y. Iguchi and S. Nakata, Real-time memory on an excitable field, Phys. Rev. E 63 (2001), p. 036220. Full Text via CrossRef

Nagle, 2008 M. Nagle, Games consoles reveal their hidden power, New Sci. 2643 (2008), pp. 26–27. Abstract | Article | PDF (288 K) | View Record in Scopus | Cited By in Scopus (0)

Nakagaki and Tóth, 2000 H.Y.T. Nakagaki and A. Tóth, Intelligence: maze solving by an amoeboid organism, Nature 407 (2000), p. 470.

Nakagaki, 2001 T. Nakagaki, Smart behaviour of true slime mould in a labyrinth, Res. Microbiol. 152 (2001), pp. 767–770. Abstract | PDF (144 K) | View Record in Scopus | Cited By in Scopus (29)

Owens et al., 2005 Owens J.D., Luebke D., Govindaraju N., Harris M., Krüger J., Lefohn A.E., Purcell T.J., 2005. A Survey of General-Purpose Computation on Graphics Hardware. Europhysics 2005 State of the Art Reports, pp. 21–51.

Okami, 2006 Okami, 2006, Capcom.

Prince of Persia, 2009 Prince of Persia, 2009. Ubisoft.

Rambidi and Rakovenchuck, 1999 N.G. Rambidi and D. Rakovenchuck, Finding path in a labyrinth based on reaction-diffusion media, Adv. Mater. Opt. Electron. 7 (1999), pp. 67–72. Article | PDF (695 K) | View Record in Scopus | Cited By in Scopus (6)

Rambidi, 2003 N.G. Rambidi, Chemical-based computing and problems of high computational complexity: the reaction-diffusion paradigm, Molecular Computing, The MIT Press, USA (2003).

Richmond and Coakley, 2009 Richmond, P., Coakley, S., 2009. A high performance agent based modelling framework on graphics card hardware with CUDA. In: Proceedings of the of 8th International Conference on Autonomous Agents and Multi-agent Systems.

Robson, 2008 D. Robson, From CPU to GPU, HPC Sci. 1 (2008), pp. 8–10.

Scarle and Clayton, 2006 S. Scarle and R.H. Clayton, Initiation of re-entry in an excitable medium: a structural investigation of cardiac tissue using a genetic algorithm, Chaos 16 (2006), p. 03315.

Sielewiesiuk and Górecki, 2002 J. Sielewiesiuk and J. Górecki, On the response of simple reactors to regular trains of impulses, Phys. Chem. Chem. Phys. 4 (2002), pp. 1326–1333. Full Text via CrossRef

Simone and Bandini, 1998 C. Simone and S. Bandini, The reaction-diffusion metaphor for modelling cooperative work, Prestige J. Manage. Res. 2 (1998), pp. 1–21.

Steinbock et al., 1995 O. Steinbock, A. Tóth and K. Showalter, Navigating complex labyrinths: optimal paths from chemical waves, Science 267 (1995), pp. 868–871. View Record in Scopus | Cited By in Scopus (91)

Tan et al., 2004 Tan J.L., Raghavan S., Liu W., Chen C.S., Nelson C.W., 2004. Simple approach to micro-pattern cells on common culture substrates by tuning wettability. Tissue Eng. 10, 865–872.

Tóth and Showalter, 1995 A. Tóth and K. Showalter, Logic gates in excitable media, J. Chem. Phys. 103 (1995), pp. 2058–2066. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (63)

Turing, 1936 A. Turing, On computable numbers, with an application to the entscheidungsproblem, Proc. Lond. Math. Soc. 42 (1936), pp. 230–265.

Turing, 1952 A. Turing, The chemical basis of morphogenesis, Philos. Trans. R. Soc. Lond. Ser. B 237 (1952), p. 631.

Yamaguchi et al., 1998 Yamaguchi T., Kusumi T., Aliev R.R., Amemiya T., Ohmori T., Nakaiwa M., Urabe K., Kinugasa S., Hashimoto H., Yoshikawa K., 1998. Unidirectionality of chemical diodes. ACH-Models Chem. 135, 401–408.

Zipes and Wellers, 1998 D.P. Zipes and H.J. Wellers, Sudden cardiac death, Circulation 98 (1998), pp. 2334–2351. View Record in Scopus | Cited By in Scopus (653)

URI:

http://wrap.warwick.ac.uk/id/eprint/2514

Request changes or add full text files to a record