The University of Sheffield
Department of Computer Science

Mariam Kiran MSc Dissertation 2005/06

"Comparative Analysis of Hypercomputational Systems"

Supervised by Dr MP Stannett

Abstract

In the 1930s, Turing suggested his abstract model for a practical computer, hypothetically visualizing thedigital programmable computer long before it was actually invented. His model formed the foundation for every computer made today. The past few years have seen a change in ideas where philosophers and scientists are suggesting models of hypothetical computing devices which can outperform the Turing machine, performing some calculations the latter is unable to. The Church-Turing Thesis, which the Turing machine model embodies, has raised discussions on whether it could be possible to solve undecidable problems which Turing's model is unable to. Models which could solve these problems, have gone further to claim abilities relating to quantum computing, relativity theory, even the modeling of natural biological laws themselves. These so called 'hypermachines' use hypercomputational abilities to make the impossible possible. Various models belonging to different disciplines of physics, mathematics and philosophy, have been suggested for these theories. My (primarily research-oriented) project is based on the study and review of these different hypercomputational models and attempts to compare the different models in terms of computational power.

The project focuses on the ability to compare these models of different disciplines on similar grounds and goes further to give a few new ideas pertaining to the field. Because these models cannot currently be implemented, forming a comparison technique is again practically difficult to achieve. Despite of these practical issues, attempts have been made to compare computational power based on factors like functionality, time and more. Existing comparison techniques have also been discussed in able to achieve results that are as reliable as possible. Therefore this project largely focuses on the analysis of various models suggested over the years, and attempts to compare them on issues of theory and practicality as well.