[eas_cs_seminars] 9th May 2017

[Luca Rossi]

Dear all,

Next week our CS seminar series will host Florian Steinberg (
http://www.mathematik.tu-darmstadt.de/~steinberg/) who will give a talk
titled "Introduction to second order complexity theory". The talk will be
held in MB108 from 11am to 12.30am. *Please note the unusual place and time*
.

Best,
Luca

Abstract:
Classical computability and complexity theory use Turing machines as a
foundation for consideration of effectivity (computability) and efficiency
(polynomial-time computability) of operations on countable discrete
structures. For many applications in engineering it would be desirable to
not only compute on countable discrete structures but also to compute on
continuous structures like the real numbers. The most common model for
computation on the real numbers by digital computers are floating point
computations. Modeling real numbers by machine numbers is unsatisfactory
from a mathematical point of view as the content of a proof of correctness
of a mathematical algorithm is usually completely lost during an
implementation. A mathematical rigorous and realistic model for computation
on continuous structures is provided by computable analysis. The finite
strings as codes for elements of a structure are replaced by total string
functions that provide on demand information about the element they encode.
Functions between encoded spaces can then be computed by operating on Baire
space: The space of all total string functions. Computation on Baire space
is done using oracle Turing machines. Intuitively, oracle Turing machines
correspond to programs with function calls. It is not a priory clear which
of these programs should be considered fast. We introduce the accepted
class of polynomial-time computable operators on Baire space, i.e. we
specify what programs with function calls should be considered efficient.
The definition resembles classical polynomial-time computability very
closely (due to work by Kapron and Cook). However, there are some important
differences that we investigate in some detail.

-- 
Luca Rossi

Lecturer in Computer Science
School of Engineering and Applied Science
Aston University
Web: http://www.cs.aston.ac.uk/~rossil/ <http://www.cs.bham.ac.uk/~rossil/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.aston.ac.uk/pipermail/eas_cs_seminars/attachments/20170504/c44426ad/attachment.html