From CSclasswiki
Jump to: navigation, search

Thesis Project Proposal

  • Angela Tosca
  • Adviser: Joseph O’Rourke
  • Computer Science Department

The Limits of Computation Under the Turing Machine Model

The Turing machine model of computation, while powerful enough to have served as the theoretical foundation for several generations of computing machinery, is nevertheless subject to strict limitations upon what types of problems it can effectively solve. On the one hand, there are insurmountable computational limitations woven into the very structure of the model. For even a Turing machine equipped with unlimited time and memory resource cannot solve the Halting Problem, which implies that although it can compute one class of functions (the recursive or computable functions), it cannot compute a wider class (the noncomputable or undecidable functions). On the other hand, any realization of the Turing machine model is also subject to the physical limitations of time and space. That is, even though a Turing machine can solve an NP-complete problem such as the Travelling salesperson problem, without a resolution of the P=?NP question, no one knows how to construct a machine that could solve instances of the problem within a practical span of time (even within the age of the universe). Given these limits, particularly the first set pertaining to computability, it is natural to ask if the Turing machine model accurately captures all effectively calculable functions. The widely held belief now known as the Church-Turing thesis maintains that it does. Because the thesis has yet to be proven true nor false, however, the question remains open. There are proponents of “hypercomputation” who argue that the Church-Turing thesis sets an as-yet unjustified limit upon what can be computed [1, 2]. The hypercomputational models that follow from such a claim are intriguing to say the least, and to compare them with the classical Turing machine model provides illuminating insight into the mathematical foundations of computer science. However, as Cockshott and Michaelson point out, for one of these models to contend with the Turing machine model it must not only be theoretically intriguing, but also physically realizable:

Above all, we require that the new system actually encompasses effective computation: that is, that it can be physically realised in some concrete machine, be it an analytic engine or a human with a slate and chalk. While we are not unduly troubled by systems that require unbounded resources such as an unlimited TM [Turing Machine] tape, we reject systems whose material realisations conflict with the laws of physics, or which require actualised infinities as steps in the calculation process. [3]

The limits of time and space, therefore, impose a significant boundary upon which models of hypercomputation, if any, are physically realizable. By examining these limits in relation to what is computable under the current model, however, we can approach the issue of the limits of computation from a different direction. For instance, we can model computation in natural systems in comparison with the Turing machine. The results of Spiegelmann [1] and Calude et. al. [4] in this area point to the possibility of computable phenomena in physical reality that fall outside of the domain of the Church-Turing thesis. We can also compare elaborations of the Turing machine model based on non-classical physics, such as quantum Turing machines (QTMs) and probabilistic Turing machines (PTMs) with their classical counterpart. While neither model appears to be able to compute classes of functions beyond those which are computable under the classic Turing machine model, they do appear capable of dramatically faster computation, which may serve to revise our conception of what problems are practically solvable within the bounds of physical time. Over the course of the next year, through an examination of the alternative models of computing discussed above, including various models of hypercomputation, natural computation, and non-classical Turing machine computation such as the PTM and QTM, I intend to test the limits of the Turing machine model. My two foci will be exploring the limits of various theoretical models (hypercomputation), and assessing whether physical realizations of the various models are consistent with known physics, and if so, might they render intractible problems tractible. While I do not expect or intend to displace the Turing Machine model, I do expect to come to a thorough understanding of its limitations, and to make a meaningful contribution to the debate over whether or not it is an accurate encapsulation of all that can be computed.


[1] Copeland, B.J. (2002) Hypercomputation. Minds and Machines 12, 461-502.

[2] Syropoulos, A. (2008) Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer-Verlag, Berlin, Heidelberg, New York

[3] Cockshott, P. and Michaelson G. (2007) Are there new models of compuation? Reply to Wegner and Eberbach. The Computer Journal 50(2), 232-247.

[4] Calude, C.S., Calude, E., and Svozil, K. The complexity of proving chaoticity and the Church-Turing thesis, arXiv:1006.2951v2 [nlin.CD] (2010)