[eas_cs_seminars] 9th May 2017
Luca Rossi l.rossi at aston.ac.ukTue May 9 10:28:22 BST 2017
- Previous message: [eas_cs_seminars] 9th May 2017
- Next message: [eas_cs_seminars] 9th May 2017
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Hi all, This is just a reminder of today's seminar "Introduction to second order complexity theory" by Florian Steinberg (http://www.mathematik.tu- darmstadt.de/~steinberg/). The talk will be in MB108 from *11am* to 12.30am. Best, Luca On 4 May 2017 at 21:11, Luca Rossi <l.rossi at aston.ac.uk> wrote: > 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/> > -- 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/20170509/9f9dfd6c/attachment.html
- Previous message: [eas_cs_seminars] 9th May 2017
- Next message: [eas_cs_seminars] 9th May 2017
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the eas_cs_seminars mailing list