Selim Akl, Queens University

 

Selim Akl, Queens University

Sage 4101

October 17, 2012 12:00 PM - 1:30 PM

 

Absract:

There are three parts to this talk.

 

Part 1 offers an overview of unconventional computing, with its two components, namely, unconventional computers (such as quantum computers, relativistic computers, and so on), and unconventional computational problems (such as those involving entities in the physical universe, those under the control of natural laws, including Homeostasis, and the Principles of Heisenberg and Le Châtelier, and so on).

 

Part 2 explores the role of space and time in unconventional computational problems. Computable functions requiring computational ubiquity challenge the limits of conventional models. Even unconventional computers with bounded ubiquity can cope up to a point, and then they too surrender. This leads to the conclusion that the widely accepted assumption underlying the Church-Turing Thesis, whereby anything that can be computed can be simulated on a Universal Computer, is in error. Here, science and philosophy intermingle as some established, and some postulated physical phenomena (such as entropy, decoherence, and time travel) are brought to bear on the "Principle of Simulation". The inevitable conclusion is that the Universal Computer cannot be realized.

 

Part 3 assumes that all objections to time travel have been set aside, or dealt with appropriately. It is shown that a computational system with closed timelike curves is a powerful hypercomputational tool. Specifically, such a system allows us to solve four of five problems advanced in Part 2 as counterexamples to the fundamental principle of universality in computation. The fifth counterexample, however, remains unassailable, indicating that universality in computation cannot be achieved, even with the help of such an extraordinary ally as time travel.

 

 Paper at: Time Travel: A New Hypercomputational Paradigm

akl@cs.queensu.ca

http://research.cs.queensu.ca/home/akl

Add to calendar
Share|